OpenEuphoria

1. Creating all combinations of a dynamic sequence

• Posted by cp Jul 02, 2010
• 1126 views

I have a sequence that looks like

sMySeq = {{a1,a2},{b1,b2},{c1,c2}} 

I need to create a sequence of all possible combinations of the elements that looks like

sCombos = {{a1,b1,c1},{a1,b1,c2},{a1,b2,c1},{a1,b2,c2},{a2,b1,c1},{a2,b1,c2}..... 

I know I can do this with nested for loops but sMySeq may contain 2 sequences or 20 or any number. Is there a way to do this dynamically regardless of how many sequences sMySeq contains.

Thanks

3. Re: Creating all combinations of a dynamic sequence

• Posted by cp Jul 02, 2010
• 1072 views

If I have something like

for a = 1 to length(sMySeq[1]) do 
    for b = 1 to length(sMySeq[2]) do 
        for c = 1 to length(sMySeq[3]) do 
        .... 

It seems this will only handle the 3 sequences in sMySeq. What if sMySeq now looks like

sMySeq = {{a1,a2},{b1,b2},{c1,c2},{d1,d2,d3}} 

I'm thinking this needs some sort of recursive function but just not sure how to go about it. thanks

5. Re: Creating all combinations of a dynamic sequence

• Posted by PeteE Jul 02, 2010
• 1103 views

As long as sMySeq remains two-dimensional, you could use a sequence to keep track of which index you are in for each combination. After building a combo, increment the rightmost index, and carry into the left index if rolls over, just like addition. When you can't carry past index 1, you're finished.

integer finished 
sequence sCombos, indices, tmp 
 
finished = 0 
sCombos = {} 
indices = repeat(1, length(sMySeq)) 
tmp = indices 
 
while not finished do 
	? indices 
	for i = 1 to length(indices) do 
		tmp[i] = sMySeq[i][indices[i]] 
	end for 
	sCombos = append(sCombos, tmp) 
 
	for i = length(indices) to 1 by -1 do 
		if indices[i] < length(sMySeq[i]) then 
			indices[i] += 1 
			exit 
		end if 
		indices[i] = 1 
		if i = 1 then 
			finished = 1 
		end if 
	end for 
end while 

7. Re: Creating all combinations of a dynamic sequence

• Posted by jimcbrown (admin) Jul 02, 2010
• 1062 views

If you are using the translator (euc) then loops might be better, as recursion uses the regular stack and has a limit.

With the interpreter (eui or euiw) it does not matter, as the heap is used. I am not sure which is more efficient (using a sequence or the interpreter's function stack), or if there is much of a difference at all, but both should work equally well.

9. Re: Creating all combinations of a dynamic sequence

• Posted by petelomax Jul 03, 2010
• 1070 views

Hi,
This is the combo demo from Phix, which runs fine on RDS Eu, and has just been updated to calculate maxcomb properly. You should find it most useful.

-- 
-- combo.exw 
-- 
-- A simple demonstration program.  
-- 
-- groups: Contains lists of permitted values for each slot. 
--         Note that the length of each mini-set may be different. 
-- key(): A novel algorithm to quickly recreate any possible combination 
--        using only an integer code. The original challenge came from a 
--        locksmith who wanted to allocate keys for hotel rooms, and store  
--        them in the smallest possible way. Clearly this algorithm has  
--        other potential uses. See also (the later) perm.e/permutes.exw 
-- 
-- The results are AAB, AAC, ACB, ACC, BAB, BAC, BCB, BCC. 
-- 
 
sequence groups 
         groups={"AB","AC","BC"} 
 
function key(integer n) 
--returns the nth key 
sequence res 
integer w 
    n -= 1 
    res = repeat(' ',length(groups)) 
    for i=length(res) to 1 by -1 do 
        w = remainder(n,length(groups[i])) 
        n = floor(n/length(groups[i])) 
        res[i] = groups[i][w+1] 
    end for 
    return res 
end function 
 
 
integer maxcomb -- product of group lengths 
    maxcomb = length(groups[1]) 
    for i=2 to length(groups) do 
        maxcomb *= length(groups[i]) 
    end for 
    for i=1 to maxcomb do 
        puts(1,key(i)&", ") 
    end for 
    puts(1,'\n') 
--  if getc(0) then end if 

Obviously if you really (really?!) need a full set, then it is just a simple matter of res=repeat(0,maxcomb) and then res[i]=key(i) in the loop, but more sensibly wherever you (would) use res[i] you could/should just code key(i), and perhaps more importantly wherever you might store res[i], just store i instead.

Regards, Pete

11. Re: Creating all combinations of a dynamic sequence

• Posted by petelomax Jul 03, 2010
• 1020 views

I have to ask... did you read/try my code before you posted that?

Pete

13. Re: Creating all combinations of a dynamic sequence

• Posted by petelomax Jul 03, 2010
• 1031 views

You're pretty fast on the reply button tonite!

15. Re: Creating all combinations of a dynamic sequence

• Posted by petelomax Jul 03, 2010
• 1004 views

2:33am and I should really be in bed!