OpenEuphoria

Get all combinations of n digits among m digits

• Posted by jmduro 3 weeks ago
• 338 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