Finding every combination of elements in a table (Lua/PseudoCode)

Question

I'm trying to execute a function with every single combination of elements from a table. (In Lua). The table and the elements can change, but the structure will stay the same. The table is organized so that [1] of it would be the first argument of the function, and so on and so on.

If this is a table that I've got,

Table = {
    [1] = {Player1, Player2}
    [2] = {PlayerA, PlayerB, PlayerC}
    [3] = {PlayerOne, PlayerTwo}
}

If I wrote that out manually, it would probably look like this: (Given that the function is named Exe).

Exe(Player1, PlayerA, PlayerOne)
Exe(Player2, PlayerA, PlayerOne)
Exe(Player3, PlayerA, PlayerOne)

Exe(Player1, PlayerB, PlayerOne)
Exe(Player2, PlayerB, PlayerOne)
Exe(Player3, PlayerB, PlayerOne)

Exe(Player1, PlayerC, PlayerOne)
Exe(Player2, PlayerC, PlayerOne)
Exe(Player3, PlayerC, PlayerOne)


Exe(Player1, PlayerA, PlayerTwo)
Exe(Player2, PlayerA, PlayerTwo)
Exe(Player3, PlayerA, PlayerTwo)

Exe(Player1, PlayerB, PlayerTwo)
Exe(Player2, PlayerB, PlayerTwo)
Exe(Player3, PlayerB, PlayerTwo)

Exe(Player1, PlayerC, PlayerTwo)
Exe(Player2, PlayerC, PlayerTwo)
Exe(Player3, PlayerC, PlayerTwo)

However, I don't WANT to write that out, and it breaks my general rule of thumb that if you're copying and pasting in a program, you're doing it wrong.

So instead, I would like to go through the table and execute every single possible combination. The problem so that the table can (potentially) have any number of tables inside of it, and also that the table inside of the table can potentially have unlimited number of values.

For example, the table could end up looking like this:

Table = {
    [1] = {Player1, Player2}
    [2] = {PlayerA}
    [3] = {PlayerOne}
}

In which execution would end up looking like this manually:

Exe(Player1, PlayerA, PlayerOne)
Exe(Player2, PlayerA, PlayerOne)

Also, the table might end up like this:

Table = {
    [1] = {Player1, Player2}
    [2] = {PlayerA}
    [3] = {PlayerOne}
    [4] = {PlayerUno, PlayerDos}
    [5] = {PlayerApple, PlayerBoy, PlayerCat, PlayerDog}
}

In which the exeuction would end up like..

Exe(Player1, PlayerA, PlayerOne, PlayerUno, PlayerApple)
Exe(Player2, PlayerA, PlayerOne, PlayerUno, PlayerApple)

Exe(Player1, PlayerA, PlayerOne, PlayerDos, PlayerApple)
Exe(Player2, PlayerA, PlayerOne, PlayerDos, PlayerApple)


Exe(Player1, PlayerA, PlayerOne, PlayerUno, PlayerBoy)
Exe(Player2, PlayerA, PlayerOne, PlayerUno, PlayerBoy)

Exe(Player1, PlayerA, PlayerOne, PlayerDos, PlayerBoy)
Exe(Player2, PlayerA, PlayerOne, PlayerDos, PlayerBoy)


Exe(Player1, PlayerA, PlayerOne, PlayerUno, PlayerCat)
Exe(Player2, PlayerA, PlayerOne, PlayerUno, PlayerCat)

Exe(Player1, PlayerA, PlayerOne, PlayerDos, PlayerCat)
Exe(Player2, PlayerA, PlayerOne, PlayerDos, PlayerCat)


Exe(Player1, PlayerA, PlayerOne, PlayerUno, PlayerDog)
Exe(Player2, PlayerA, PlayerOne, PlayerUno, PlayerDog)

Exe(Player1, PlayerA, PlayerOne, PlayerDos, PlayerDog)
Exe(Player2, PlayerA, PlayerOne, PlayerDos, PlayerDog)

As you can see, I have found a pattern... I was able to divide the above 'Execution' thing above into segments/groups, such as line 1 and line 2 have one change. Then, they get copied into line 4 and 5, but the next variable get's changed.

As you can see, I'm having trouble putting that pattern into code. I think some function recursion will be required, but I'm not sure how to pull it off or recurse through it. I'm thinking that I'll have to use functions with ... as the arguments, and the unpack function, but I'm not sure how this would even work.

Also, the reason this is required, and not just manually copying and pasting it (Which actually would be easier), is because the content of the table will be generated.

Can you guys help me?

Answer 1

Use recursion.

Imagine a function map_all (fcn, tab, idx, ...) that maps fcn to the product of the elements of all the tables tab[1] to tab[idx] prepended to ...

The base case is when idx is less than 1. In that case, simply apply fcn(...)

Otherwise, map_all(fcn, tab, idx-1, <el>, ...) for all <el> in tab[idx]

function map_all (fcn, tab, idx, ...)
    if idx < 1 then
        fcn(...)
    else
        local t = tab[idx]
        for i = 1, #t do map_all(fcn, tab, idx-1, t[i], ...) end
    end
end

So,

> Table = {
>>     [1] = {'Player1', 'Player2'},
>>     [2] = {'PlayerA', 'PlayerB', 'PlayerC'},
>>     [3] = {'PlayerOne', 'PlayerTwo'}
>> }
> map_all(print, Table, #Table)
Player1 PlayerA PlayerOne
Player2 PlayerA PlayerOne
Player1 PlayerB PlayerOne
Player2 PlayerB PlayerOne
Player1 PlayerC PlayerOne
Player2 PlayerC PlayerOne
Player1 PlayerA PlayerTwo
Player2 PlayerA PlayerTwo
Player1 PlayerB PlayerTwo
Player2 PlayerB PlayerTwo
Player1 PlayerC PlayerTwo
Player2 PlayerC PlayerTwo

and

> Table = {
>>     [1] = {'Player1', 'Player2'},
>>     [2] = {'PlayerA'},
>>     [3] = {'PlayerOne'}
>> }
> map_all(print, Table, #Table)
Player1 PlayerA PlayerOne
Player2 PlayerA PlayerOne

and

> Table = {
>>     [1] = {'Player1', 'Player2'},
>>     [2] = {'PlayerA'},
>>     [3] = {'PlayerOne'},
>>     [4] = {'PlayerUno', 'PlayerDos'},
>>     [5] = {'PlayerApple', 'PlayerBoy', 'PlayerCat', 'PlayerDog'},
>> }
> map_all(print, Table, #Table)
Player1 PlayerA PlayerOne   PlayerUno   PlayerApple
Player2 PlayerA PlayerOne   PlayerUno   PlayerApple
Player1 PlayerA PlayerOne   PlayerDos   PlayerApple
Player2 PlayerA PlayerOne   PlayerDos   PlayerApple
Player1 PlayerA PlayerOne   PlayerUno   PlayerBoy
Player2 PlayerA PlayerOne   PlayerUno   PlayerBoy
Player1 PlayerA PlayerOne   PlayerDos   PlayerBoy
Player2 PlayerA PlayerOne   PlayerDos   PlayerBoy
Player1 PlayerA PlayerOne   PlayerUno   PlayerCat
Player2 PlayerA PlayerOne   PlayerUno   PlayerCat
Player1 PlayerA PlayerOne   PlayerDos   PlayerCat
Player2 PlayerA PlayerOne   PlayerDos   PlayerCat
Player1 PlayerA PlayerOne   PlayerUno   PlayerDog
Player2 PlayerA PlayerOne   PlayerUno   PlayerDog
Player1 PlayerA PlayerOne   PlayerDos   PlayerDog
Player2 PlayerA PlayerOne   PlayerDos   PlayerDog
>