OpenEuphoria

Re: Get all combinations of n digits among m digits

• Posted by petelomax 2 weeks ago
• 205 views

Very good, my 15.1s -> your 8.9s -> next's 5.3s -> hopefully last one's 4.9s, not a bad day week's work!
I couldn't understand why you were testing nr=1, if nr=1 and ns!=ne then ?9/0 end if never triggered, so I took it out...

Slicing just the once for both recursive calls saves a fair chunk

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

Not slicing at all, except for when "all the rest", saves another 10%

sequence combis = {}  
  
procedure recurse(sequence remaining,               /* digits remaining to compute ... */  
                  integer needed,                   /* number of digits expected for a valid combination */  
                  integer done=0,                   /* ... but do not use remaining[1..done] */  
                  sequence selected = {})           /* digits already selected for a potential combination */  
  if done=0 then combis = {} end if /* you can and probably will thank me later for that! */ 
  integer nr = length(remaining)-done   -- 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+1..$]) 
  elsif ns = needed then 
    combis = append(combis, selected)  
  else 
--  elsif ns+nr>needed then 
    done += 1 
    -- select next  
    recurse(remaining, needed, done, selected & remaining[done])  
    -- skip next  
    recurse(remaining, needed, done, selected)  
  end if 
end procedure  

Slightly miffed that final commented-out test doesn't help and actually slows it down a smidge, but oh well.
Then again, that's the main point here: "all the rest" is not only slightly faster but cuts out a whole heap of pointless "not enough" recursions, I think.