OpenEuphoria

Re: Get all combinations of n digits among m digits

• Posted by jmduro 2 weeks ago
• 160 views

After trying different optimizations, the best one is this one:

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 
  elsif ns = ne then   
    combis = append(combis, selected)   
    return 
  else  
    integer r1 = remaining[1]  
    remaining = remove(remaining, 1)  
    -- select next   
    recurse(remaining, ne, append(selected, r1))   
    -- skip next   
    recurse(remaining, ne, selected)   
  end if   
end procedure   

I even tried to symplify your second proposal as below, but it is not a time saver:

procedure recurse(sequence remaining,               /* digits remaining to compute ... */   
                  integer needed,                   /* number of digits expected for a valid combination */   
                  integer done=1,                   /* ... but do not use remaining[1..done] */   
                  sequence selected = {})           /* digits already selected for a potential combination */   
  integer nr = length(remaining)-done+1   -- number of digits remaining to compute   
  integer ns = length(selected)    -- number of digits already selected for a potential combination   
  if ns+nr = needed then   
    combis = append(combis, selected & remaining[done..$]) 
  elsif ns = needed then  
    combis = append(combis, selected)   
  else  
    -- select next   
    recurse(remaining, needed, done+1, selected & remaining[done])   
    -- skip next   
    recurse(remaining, needed, done+1, selected)   
  end if  
end procedure   

Jean-Marc