"wolf, carrot, goat" riddle on steroids (generating a table in lua)

Question

I have an array with a large number of elements in it, and would like to group them as many ways as possible, making each group an element in a new array. However, certain elements are incompatible, example:

objects = {a, b, c, d}
incompatible = {{a,b}, {a,d}, {c,d}}

I would like to generate an array containing all compatible arrangements of objects, with no duplicates. An element of this array can contain any and all number of objects, even singltons, as long as it's contents are all compatible.

in the case of the example above, it would look like this:

compatible_groups = {{},{a},{b},{c},{d},{a,c},{b,c},{b,d}}

One possible solution i considered was a function which takes an arbitrary number of arguments, comparing them all against one another such as:

function generate_groups(...)
    local arg={...}
    for i=1, #arg-(n+0) do -- only looping partially through array to prevent repeats
        for j=i+1, #arg-(n+1) do
            for k=j+1, #arg-(n+2) do
               ...

but for that to work, i would need to have as many nested for loops as the function has arguments. No idea how to do that.

Once that's settled, it would be fairly trivial to check to see if two of the arguments form one of the elements of the incompatible array.

for i=1, #incompatible
if arg[a][1] == incompatible[a][1] and arg[a][2] == incompatible[a][2]...

So i think anyway. Is there a simpler approach I'm missing here?

Oliver · Accepted Answer · 2014-01-15T08:34:17.047

Notice that if you have a set S(n) of all combinations for a list of length n, it is equal to S(n-1) + {list[1] with each combo in S(n-1)} where S(n-1) is set of all combinations for list of n-1 rightmost items of list. This means you can have recursive function. Since Lua does not have a splice operation (as opposed to python or lisp), we use an index "rightLen" which is the # items to use, from right end:

function getAllCombinations(list, rightLen)
    local N = #list
    rightLen = rightLen or N
    if rightLen <= 1 then 
        return {{}, {list[N]}}
    end
    local combosNm1 = getAllCombinations(list, rightLen-1)
    local combos = table.copy(combosNm1)
    local addItem = list[N-rightLen+1]
    for i,combo in ipairs(combosNm1) do
        table.insert(combo, addItem)
        table.insert(combos, combo)
    end
    return combos 
end

and table.copy is defined as

function table.copy(tt)
    local newT = {}
    for i,t in ipairs(tt) do
        if type(t) == 'table' then
            table.insert(newT, table.copy(t))
        else
            table.insert(newT, t)
        end
    end
    return newT
end

I have no idea if this is best performance possible. For 14 items it looked instantaneous on my laptop VM, for 17 items it required 1 second, for 19 items 5 seconds. Exponential growth of course. The copy is nasty, maybe the following would give faster results:

local combos = {} -- old: table.copy(combosNm1)
local addItem = list[N-rightLen+1]
for i,combo in ipairs(combosNm1) do
    table.insert(combos, combo)
    extCombo = table.copy(combo)
    table.insert(extCombo, addItem)
    table.insert(combos, extCombo)
end

and table.copy can simply be

function table.copy(tt)
    local newT = {}
    for i,t in ipairs(tt) do
         newT[i] = t
    end
    return newT
end

This seems about 40% faster.

Would be nice to transform this into algorithm that makes use of Lua's tail call so that not limited by function call stack limit. Might also gain performance. — Oliver, Jan 15 '14 at 08:38
This may very well be the answer to my question, but after playing with the code for a few hours I still feel like it's over my head. I'll keep at it for a while and if I can get it to work, make this the answer. Thanks! — ridthyself, Jan 15 '14 at 18:00
@etothepowerofx does it not produce the combinations you are looking for? what do you not understand? — Oliver, Jan 15 '14 at 18:06
This code works just as advertised, but I had some trouble understanding it without further study. Thank you! — ridthyself, Jan 21 '14 at 13:48
@etothepowerofx Great to hear. Hopefully you figured out where to add the filter for your exclusions, the second method will be more efficient when exclusions are involved. — Oliver, Jan 21 '14 at 14:17

score 2 · Answer 2 · edited May 23 '17 at 11:57

2

You can first generate all possible permutations of the list then subtract the items you don't want.

You can use recursion to generate permutations without a ton of loops. See Algorithm to generate all possible permutations of a list?. You can either adapt the algorithm to check into your filter table and simply ignore the offending results, or simply remove them from the results afterwards.

edited May 23 '17 at 11:57

Community

1
1

answered Jan 15 '14 at 03:56

Colonel Thirty Two

23,953
8
45
85

Note that "permutations" does not equal "combinations". I believe the algorithms are quite different. – Oliver Jan 15 '14 at 07:56
Right, the idea is to determine how many legal ways there are to combine a list of items into groups. Your idea of tail recursion rather than nested loops does sound appealing, but a permutation will require tons of wasted computation that will need to be filtered out. – ridthyself Jan 21 '14 at 13:58
Well, the same idea applies; just generate combinations instead of permutations, then filter out the items you don't want. Schollii's answer is more complete though. – Colonel Thirty Two Jan 21 '14 at 14:40

"wolf, carrot, goat" riddle on steroids (generating a table in lua)

2 Answers2