OpenEuphoria

1. Get all combinations of n digits among m digits

• Posted by jmduro 3 weeks ago
• 340 views

For the last version of my Sudoku Trainer, I needed a function to test all combinations of n digits among m digits (m > n) on all combinations of x cells among y cells (y > x) to find digits restricted to some cells.

Here is the function I wrote to do the job.

include std/convert.e 
 
-- remove a digit from a sequence 
function remove_int(sequence s, integer digit) 
  sequence result = {} 
  for i = 1 to length(s) do 
    if s[i] != digit then result = append(result, s[i]) end if 
  end for 
  return result 
end function 
 
function count_ones(sequence s) 
  integer n = 0 
  for i = 1 to length(s) do 
    if s[i] = 1 then n += 1 end if 
  end for 
  return n 
end function 
 
function get_combinations(sequence digits, integer n) 
  integer m = length(digits) 
  sequence result= {} 
  for i = 2 to power(2, m) - 1 do 
    sequence s = int_to_bits(i, m) 
    if n = count_ones(s) then 
      result = append(result, remove_int(digits * s, 0)) 
    end if 
  end for 
  return result 
end function 

Here is the test code:

constant TEST_SEQUENCE = {1,2,4,6,7,9} 
 
puts(1, "Get all pairs\n") 
print(1, get_combinations(TEST_SEQUENCE, 2)) 
puts(1, "\nGet all triplets\n") 
print(1, get_combinations(TEST_SEQUENCE, 3)) 

And here is the result:

Get all pairs 
{{1,2},{1,4},{2,4},{1,6},{2,6},{4,6},{1,7},{2,7},{4,7},{6,7},{1,9},{2,9},{4,9},{6,9},{7,9}} 
Get all triplets 
{{1,2,4},{1,2,6},{1,4,6},{2,4,6},{1,2,7},{1,4,7},{2,4,7},{1,6,7},{2,6,7},{4,6,7},{1,2,9},{1,4,9},{2,4,9},{1,6,9},{2,6,9},{4,6,9},{1,7,9},{2,7,9},{4,7,9},{6,7,9}} 

Jean-Marc

3. Re: Get all combinations of n digits among m digits

• Posted by jmduro 2 weeks ago
• 310 views

Thank you Pete,

On the following test, the time difference between both methods is high:

atom t0 = time() 
constant test = {1,2,3,4,5,6,7,8,9}  
for i = 1 to 10000 do 
  s = combinations(test,2) 
  s = combinations(test,3) 
  s = combinations(test,4) 
end for  
printf(1, "duration: %f\n", time() - t0) 
t0 = time() 
for i = 1 to 10000 do 
  s = get_combinations(test,2) 
  s = get_combinations(test,3) 
  s = get_combinations(test,4) 
end for  
printf(1, "duration: %f\n", time() - t0) 
 
maybe_any_key() 

duration: 1.741000 
duration: 7.538000 
Press Any Key to continue... 

Here is the OpenEuphoria version:

sequence res = {} 
 
-- Phix function 
public function combinations(sequence s, integer k, integer at=1, sequence res={}, sequence part="")  
  if k=0 then -- got a full set  
    res = append(res,part)  
  elsif at+k-1<=length(s) then  
    -- get all combinations with and without the next item:  
    res = combinations(s,k-1,at+1,res,append(part,s[at]))  
    res = combinations(s,k,at+1,res,part)  
  end if  
  return res  
end function   

Jean-Marc

5. Re: Get all combinations of n digits among m digits

• Posted by jmduro 2 weeks ago
• 206 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

7. Re: Get all combinations of n digits among m digits

• Posted by jmduro 2 weeks ago
• 185 views

Thank you Pete,

I wanted to change my OpenEuphoria tasks on RosettaCode to Euphoria as you suggested but you have been more quick than me. I had just the opportunity to change the last existing one.

Jean-Marc

9. Re: Get all combinations of n digits among m digits

• Posted by jmduro 2 weeks ago
• 187 views

Some minor tweaks let save some time:

Euphoria:recurse, duration: 8.850000 s 

    remaining = remove(remaining, 1)  

Euphoria:recurse, duration: 8.700000 s 

    recurse(remaining, ne, append(selected, r1))   

Euphoria:recurse, duration: 8.689000 s 

However using built-in functions instead of slicing or operators is not always the best choice: using head(remaining) instead of remaining[1] makes lose time.

Jean-Marc

11. Re: Get all combinations of n digits among m digits

• Posted by jmduro 2 weeks ago
• 162 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

13. Re: Get all combinations of n digits among m digits

• Posted by jmduro 1 week ago
• 147 views

Damned, there was still an error, always due to the position of this test "if nr=1 then":

sequence combis = {} 
 
procedure recurse(sequence remaining,               /* digits remaining to compute */ 
                  integer needed,                   /* number of digits needed 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 = needed then 
    combis = append(combis, selected & remaining) 
    return 
  end if 
  if ns = needed then 
    combis = append(combis, selected) 
    return 
  end if 
  if nr = 1 then return end if 
  -- select next 
  recurse(remove(remaining, 1), needed, selected & remaining[1]) 
  -- skip next 
  recurse(remove(remaining, 1), needed, selected) 
end procedure 
 
function combinations(sequence s, integer lg) 
  combis = {} 
  recurse(s, lg) 
  return combis  
end function   

Jean-Marc

15. Re: Get all combinations of n digits among m digits

• Posted by jmduro 1 week ago
• 68 views

I have tested your modifications on some hard to resolve grids.

It fails on this one:

{ 
 {{1,3,6,7},{1,6},{1,3,5,6,7,8},{1,3,4,5,6,8},9,{1,3,4,5,8},2,{5,6,8},{4,5,6,8}}, 
 {{2,3,6},4,{2,3,5,6,8,9},{3,5,6,8},{3,6},{3,5,8},1,7,{5,6,8,9}}, 
 {{1,6},{1,6,9},{1,5,6,8,9},2,{1,4,6},7,3,{5,6,8,9},{4,5,6,8,9}}, 
 {{1,2,4,6},3,{1,2,4,6},{1,4,6,8},5,{1,4,8},{6,7,8,9},{1,2,6,8,9},{2,6,7,8,9}}, 
 {9,7,{1,2,4,6},{1,3,4,6,8},{1,2,3,4,6},{1,3,4,8},{6,8},{1,2,3,5,6,8},{2,3,5,6,8}}, 
 {5,8,{1,2,6},9,{1,2,3,6,7},{1,3},{6,7},4,{2,3,6,7}}, 
 {8,{1,6,9},{1,3,4,6,9},7,{1,3,4},2,5,{3,6,9},{3,4,6,9}}, 
 {{1,2,3,4,7},{1,2,9},{1,2,3,4,7,9},{1,3,4,5},{1,3,4},6,{4,7,8,9},{2,3,8,9},{2,3,4,7,8,9}}, 
 {{2,3,4,6,7},5,{2,3,4,6,7,9},{3,4},8,{3,4,9},{4,6,7,9},{2,3,6,9},1} 
} 

At the end of the game, some cells have no valid candidate at all because of bad tips. I did not check much more because I already had such kind of problems before. I suppose it is due to combinations such as {4,6,6} with repeated candidates that I do not manage. It does not happen with my proposal.

Jean-Marc