OpenEuphoria

1. Get combinations of digits in a sequence

• Posted by jmduro Aug 17, 2017
• 1571 views

Here are 2 recursive functions that give all combinations of digits in a sequence.

sequence combinations 
 
procedure get_all_combinations(sequence s, sequence used, integer n) 
  integer lg 
   
  lg = length(s) 
  if n = lg then 
    combinations = append(combinations, used) 
    return 
  end if 
  n += 1 
  for d = 1 to length(s[n]) do 
    get_all_combinations(s, used&s[n][d], n) 
  end for 
end procedure 
 
------------------------------------------------------------------------------ 
 
procedure get_unique_combinations(sequence s, sequence used, integer n) 
  integer lg 
   
  lg = length(s) 
  if n = lg then 
    combinations = append(combinations, used) 
    return 
  end if 
  n += 1 
  for d = 1 to length(s[n]) do 
    if not find(s[n][d], used) then 
      get_unique_combinations(s, used&s[n][d], n) 
    end if 
  end for 
end procedure 
 

And here is an example of usage:

constant 
  SEQ = {{4,8,9}, {1,2,4}, {1,4,5,6}} 
 
combinations = {} 
get_all_combinations(SEQ, {}, 0) 
pretty_print(1, combinations, {}) 
puts(1, "\n") 
 
combinations = {} 
get_unique_combinations(SEQ, {}, 0) 
pretty_print(1, combinations, {}) 
puts(1, "\n") 

Here is the result: get_all_combinations allows duplicate digits, get_unique_combinations does not.

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

Jean-Marc

3. Re: Get combinations of digits in a sequence

• Posted by jmduro Aug 18, 2017
• 1477 views

I try to understand how to use permute with my sequence which has sub-items of different lengths. It s too much for my old brain. Could you provide an example using my SEQ constant as an input?

Jean-Marc

5. Re: Get combinations of digits in a sequence

• Posted by petelomax Aug 18, 2017
• 1450 views

Sorry, I didn't mean permute, I meant the comb function (also on that page), modified for your specific requirements something like this:

constant SEQ = {{4,8,9}, {1,2,4}, {1,4,5,6}}  
  
function comb(sequence pool, integer unique=0, sequence res={}, integer i=1, sequence chosen={}) 
    if i>length(pool) then  -- got a full set 
        res = append(res,chosen) 
    else 
        -- get all combinations with something from pool[i] 
        for j=1 to length(pool[i]) do 
            object pij = pool[i][j] 
            if not unique or not find(pij,chosen) then 
                res = comb(pool,unique,res,i+1,append(chosen,pij)) 
            end if 
        end for 
    end if 
    return res 
end function          
?comb(SEQ) 
?comb(SEQ,1) 

Same results as your code, but with the initialisation to {} now automated, and an accidental reset by a second task/thread mid-way through now completely impossible.

Lengthy searches through some huge number of combinations are precisely the sort of thing that gets shunted off to a background task/thread, and therefore it is important to ensure they cannot tread on each others toes.

Otherwise, this code is very similar to what you posted.

An alternative that allows early termination:

constant SEQ = {{4,8,9}, {1,2,4}, {1,4,5,6}}  
  
function comb(sequence pool, integer rid, integer unique=0, integer i=1, sequence chosen={}) 
    if i>length(pool) then  -- got a full set 
        if not call_func(rid,{chosen}) then return 0 end if 
    else 
        -- get all combinations with something from pool[i] 
        for j=1 to length(pool[i]) do 
            object pij = pool[i][j] 
            if not unique or not find(pij,chosen) then 
                if not comb(pool,rid,unique,i+1,append(chosen,pij)) then return 0 end if 
            end if 
        end for 
    end if 
    return 1    -- carry on 
end function          
 
function test(sequence s) 
    ?s 
    if equal(s,{4,1,6}) then return 0 end if 
    return 1    -- carry on 
end function 
 
?comb(SEQ,routine_id("test"))   -- {4,1,1} {4,1,4} {4,1,5} {4,1,6} 
?comb(SEQ,routine_id("test"),1) -- {4,1,5} {4,1,6} 

Pete