OpenEuphoria

Re: Get all combinations of n digits among m digits

• Posted by jmduro 2 weeks ago
• 204 views

I wrote another procedure which is more understandable for me and quite faster.

sequence combis = {} 
 
procedure recurse(sequence remaining,               /* digits remaining to compute */ 
                  integer ne,                       /* number of digits expected for a valid combination */ 
                  sequence selected = {})           /* digits already selected for a potential combination */ 
  integer nr = length(remaining)   -- number of digits remaining to compute 
  integer ns = length(selected)    -- number of digits already selected for a potential combination 
  if ns+nr = ne then 
    combis = append(combis, selected & remaining) 
    return 
  end if 
  if nr = 1 or ns = ne then 
    combis = append(combis, selected) 
    return 
  end if 
  -- select next 
  recurse(remove(remaining, 1), ne, selected & remaining[1]) 
  -- skip next 
  recurse(remove(remaining, 1), ne, selected) 
end procedure 

Here are the test results:

Test Speed of all combinations of n digits among m 
 m = 9 
 n = 2 then 3 then 4 
 100,000 times 
Phix:combinations(), duration: 17.857000 s 
Euphoria:get_combinations, duration: 75.010000 s 
Euphoria:recurse, duration: 9.478000 s 

Jean-Marc