find all possible combination of these two sets of items? Lua

Question

I see similar answers to this question given in different programming languages like Haskell and Python but all of them use build-in functionality that Lua doesn't have, so please don't mark this question as duplicate.

Let's say i have two tables like bellow:

table1 = {A,B,C}
table2 = {D,E,F}  

I would like to find all unique ways of matching the items from two tables, the answer should be (in informal notation):

AD,BE,CF
AD,BF,CE
AE,BD,CF
AE,BF,CD
AF,BD,CE
AF,BE,CD  

so the answer will store in a table that table[1] would be {{A, D}, {B, E}, {C, F}} and so on.
tables length can be anything but both will be the same size.

Answer 1

function get_all_combinations(arr1, arr2)
   local n, e, all_comb  = #arr1, {}, {}
   for j = 1, n do
      e[j] = arr2[j]
   end
   local function generate(m)
      if m <= 1 then
         local comb = {}
         all_comb[#all_comb + 1] = comb
         for j = 1, n do
            comb[j] = arr1[j]..e[j]  -- it should be {arr1[j], e[j]} to fulfill your requirements
         end
      else
         for j = 1, m do
            generate(m - 1)
            local k = j < m and m % 2 == 1 and 1 or j
            e[k], e[m] = e[m], e[k]
         end
      end
   end
   generate(n)
   return all_comb
end

for i, v in ipairs(get_all_combinations({"A", "B", "C"}, {"D", "E", "F"})) do
  print(i, table.concat(v, ";"))
end

Answer 2

An alternate way of doing it is with the following code. This was written to help with a game (Typeshift) to discover all possible combinations of variable groups of letters. I've modified it to fit your example, though.

-- table array: { {1, 2}, {3, 4}, {5, 6} }
-- Should return { 135, 136, 145, 146, 235, 236, 245, 246 }
--
-- This uses tail recursion so hopefully lua is smart enough not to blow the stack
function arrayCombine(tableArray)
  -- Define the base cases
  if (tableArray == nil) then
      return nil
  elseif (#tableArray == 0) then
      return {}
  elseif (#tableArray == 1) then
      return tableArray[1]
  elseif (#tableArray == 2) then
      return arrayCombine2(tableArray[1], tableArray[2])
    end -- if

  -- We have more than 2 tables in the input parameter.  We want to pick off the *last*
  -- two arrays, merge them, and then recursively call this function again so that we 
  -- can work our way up to the front.
  local lastArray = table.remove(tableArray, #tableArray)
  local nextToLastArray = table.remove(tableArray, #tableArray)
  local mergedArray = arrayCombine2(nextToLastArray, lastArray)

  table.insert(tableArray, mergedArray)

  return arrayCombine(tableArray)
end -- arrayCombine


function arrayCombine2(array1, array2)
  local mergedArray = {}

  for _, elementA in ipairs(array1) do
    for _, elementB in ipairs(array2) do
      table.insert(mergedArray, elementA .. elementB) 
    end -- for
  end -- for

  return mergedArray
end -- arrayCombine2

-- You can set it up this way:
combinedArray = {}
table.insert(combinedArray, {"A", "B", "C"})
table.insert(combinedArray, {"D", "E", "F"})

for i,v in ipairs(arrayCombine(combinedArray)) do
  print(i,v)
end

-- Or go this way, which may be somewhat cleaner:

for i,v in ipairs(arrayCombine({{"A", "B", "C"}, {"D", "E", "F"}})) do
  print(i,v)
end

Either way, it produces the results you're looking for.

Answer 3

we can get all shuffles via induction (not the fastest way, but pretty easy to write/understand)

local function deepcopy(orig)
    local copy
    if type(orig) == 'table' then
        copy = {}
        for orig_key, orig_value in next, orig, nil do
            copy[deepcopy(orig_key)] = deepcopy(orig_value)
        end
        setmetatable(copy, deepcopy(getmetatable(orig)))
    else
        copy = orig
    end

    return copy
end

local function get_shuffles(N)
  if N == 1 then
    return {{1}}
  end
  local shuffles = get_shuffles(N-1)
  local result = {}
  for index = 1, #shuffles do
    local shuffle = shuffles[index]
    for position = 1, #shuffle do
      local new_shuffle = deepcopy(shuffle)
      table.insert(new_shuffle, position, N)
      table.insert(result, new_shuffle)
    end
    local new_shuffle = deepcopy(shuffle)
    table.insert(new_shuffle, N)
    table.insert(result, new_shuffle)
  end
  return result
end

table1 = {"A", "B", "C"}
table2 = {"D","E", "F"}

assert(#table1 == #table2)


local result = {}

local shuffles = get_shuffles(#table1)
for index = 1, #shuffles do
  local shuffle = shuffles[index]
  local part = {}
  for i = 1, 3 do
    table.insert(part, {})
    table.insert(part[i], table1[i])
    table.insert(part[i], table2[shuffle[i]])
  end
  table.insert(result, part)
end

for index = 1, #result do
  print(result[index][1][1], result[index][1][2], result[index][2][1], result[index][2][2], result[index][3][1], result[index][3][2])
end