Generating all combinations from a table in Lua

user_10474318 0
Viewed 459

I'm trying to iterate through a table with a variable amount of elements and get all possible combinations, only using every element one time. I've landed on the solution below.

arr = {"a","b","c","d","e","f"}

function tablelen(table)
  local count = 0
  for _ in pairs(table) do 
    count = count + 1 
  end
  return count
end

function spellsub(table,start,offset)
  local str = table[start]
  for i = start+offset, (tablelen(table)+1)-(start+offset) do
    str = str..","..table[i+1]
  end
  return str
end

print(spellsub(arr,1,2))    -- Outputs: "a,d,e" correctly
print(spellsub(arr,2,2))    -- Outputs: "b"     supposed to be "b,e,f"

I'm still missing some further functions, but I'm getting stuck with my current code. What is it that I'm missing? It prints correctly the first time but not the second?

combinations lua
2 Answers

A solution with a coroutine iterator called recursively:

local wrap, yield = coroutine.wrap, coroutine.yield

-- This function clones the array t and appends the item new to it.
local function append (t, new)
    local clone = {}
    for _, item in ipairs (t) do
        clone [#clone + 1] = item
    end
    clone [#clone + 1] = new
    return clone
end

--[[
    Yields combinations of non-repeating items of tbl.
    tbl is the source of items,
    sub is a combination of items that all yielded combination ought to contain,
    min it the minimum key of items that can be added to yielded combinations.
--]]
local function unique_combinations (tbl, sub, min)
    sub = sub or {}
    min = min or 1
    return wrap (function ()
        if #sub > 0 then
            yield (sub) -- yield short combination.
        end
        if #sub < #tbl then
            for i = min, #tbl do    -- iterate over longer combinations.
                for combo in unique_combinations (tbl, append (sub, tbl [i]), i + 1) do
                    yield (combo)
                end
            end
        end
    end)
end
            
for combo in unique_combinations {'a', 'b', 'c', 'd', 'e', 'f'} do
    print (table.concat (combo, ', '))
end
user_66327360

For a tables with consecutive integer keys starting at 1 like yours you can simply use the length operator #. Your tablelen function is superfluous.

Using table as a local variable name shadows Lua's table library. I suggest you use tbl or some other name that does not prevent you from using table's methods.

The issue with your code can be solved by printing some values for debugging:

local arr = {"a","b","c","d","e","f"}


function spellsub(tbl,start,offset)
  
local str = tbl[start]
print("first str:", str)
  print(string.format("loop from %d to %d", start+offset, #tbl+1-(start+offset)))
  for i = start+offset, (#tbl+1)-(start+offset) do
    print(string.format("tbl[%d]: %s", i+1, tbl[i+1]))
    str = str..","..tbl[i+1]
  end
  return str
end

print(spellsub(arr,1,2))    -- Outputs: "a,d,e" correctly
print(spellsub(arr,2,2))    -- Outputs: "b"     supposed to be "b,e,f"

prints:

first str:  a
loop from 3 to 4
tbl[4]: d
tbl[5]: e
a,d,e
first str:  b
loop from 4 to 3
b

As you see your second loop does not ran as the start value is already greater than the limit value. Hence you only print the first value b

I don't understand how your code is related to what you want to achieve so I'll leave it up to you to fix it.

user_28581700
Related