In lua I want to get every possible combination of every possible combination of whole strings in array... Let me explain what I mean by that. Let's say that we got an array C = { "a", "b", "c", "d", "e"}. I want to get this result:
output = {
{ "a", "b", "c", "d", "e"};
{ "ab", "c", "d", "e};
{ "ac", "b", "d", "e" };
{ "abc", "d", "e"};
{ "aeb", "d", "c"};
{ "a", "bde", "c"};
{ "ab", "cd", "e"};
{ "a", "bcd", "e" };
{ "acd", "b", "e};
{ "ac", "bd", "e"};
{ "abc", "de"};
{ "abcd", "e"};
{ "acd", "be"}
{ "ac" "bde"};
...and so on until
{"abcde"};
}
So every WHOLE string from C array is combine with every other whole string - and the higher combinations of this combinations combine with every other - and so on - giving ONLY UNIQUE combinations without repeating any element - which differs it from "superpermutation" because any combo must be "first unique"[so to speak] - so "ab" or "abc", but no "ba", "aba", "bab", "bac" etc. .
To be perfectly honest i cannot get a grip on this problem. Maybe someone have an idea how to solve this?
What i tried so far was to get basic permutations for C array by below function:
local function getPermuations(array)
local wrap, yield, board = coroutine.wrap, coroutine.yield, {};
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
local function permutate (tbl, sub, min)
sub = sub or {}
min = min or 1
return wrap (function ()
if #sub > lim then
yield (sub);
end
if #sub < #tbl then
for i = min, #tbl do
for combo in permutate (tbl, append (sub, tbl [i]), i + 1) do
yield (combo)
end
end
end
end)
end
for combo in permutate(array) do
--table.sort( combo, self.sortAlphabetical )
table.insert(board, combo);
end
return board;
end
It returns table of arrays each holding one permutation. After that i tried to write a recurrent function that takes rests of elements from C for each returned array and permutate them as well and so on. So it is basically something like "super non repeating permutation". But i couldn't get this to work:
local function getRest(str, inh)
local backbone, rest = {}, {};
for k,v in ipairs(C) do
backbone[v] = true;
end
for key in pairs(inh) do
for k,v in ipairs(C) do
if string.find(key, v) then backbone[v] = nil; end
end;
end;
for _, e in ipairs(C) do
if string.find(str, e) then backbone[e] = nil; end
end
if next(backbone) then
for obj in pairs(backbone) do
table.insert(rest, obj)
end
table.sort(rest, function(a, b)
return string.lower(a) < string.lower(b)
end)
end
return rest;
end;
local mainBoard = {};
local function superpermutation(permutation, inheritance)
inheritance = inheritance or {};
local px = getPermuations(permutation);
for _, array in ipairs(px) do
local r = getRest(table.concat(array), inheritance);
if #r>1 then
inheritance[table.concat(array)] = true;
superpermutation(r, inheritance);
elseif next(inheritance) then
local m = {};
for k in pairs(inheritance) do
table.insert(m, {k})
end;
if r and r[1] then
table.insert(m, {r[1]})
end
table.insert(mainBoard, m)
end;
end
return
end;
superpermutation(C);
for index, superarray in ipairs(mainBoard) do
local str = "";
for _, array in ipairs(superarray) do
str = str.."("..table.concat( array )..")"
end
print(str)
end
In lua I want to get every possible combination of every possible combination of whole strings in array... Let me explain what I mean by that. Let's say that we got an array C = { "a", "b", "c", "d", "e"}. I want to get this result:
output = {
{ "a", "b", "c", "d", "e"};
{ "ab", "c", "d", "e};
{ "ac", "b", "d", "e" };
{ "abc", "d", "e"};
{ "aeb", "d", "c"};
{ "a", "bde", "c"};
{ "ab", "cd", "e"};
{ "a", "bcd", "e" };
{ "acd", "b", "e};
{ "ac", "bd", "e"};
{ "abc", "de"};
{ "abcd", "e"};
{ "acd", "be"}
{ "ac" "bde"};
...and so on until
{"abcde"};
}
So every WHOLE string from C array is combine with every other whole string - and the higher combinations of this combinations combine with every other - and so on - giving ONLY UNIQUE combinations without repeating any element - which differs it from "superpermutation" because any combo must be "first unique"[so to speak] - so "ab" or "abc", but no "ba", "aba", "bab", "bac" etc. .
To be perfectly honest i cannot get a grip on this problem. Maybe someone have an idea how to solve this?
What i tried so far was to get basic permutations for C array by below function:
local function getPermuations(array)
local wrap, yield, board = coroutine.wrap, coroutine.yield, {};
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
local function permutate (tbl, sub, min)
sub = sub or {}
min = min or 1
return wrap (function ()
if #sub > lim then
yield (sub);
end
if #sub < #tbl then
for i = min, #tbl do
for combo in permutate (tbl, append (sub, tbl [i]), i + 1) do
yield (combo)
end
end
end
end)
end
for combo in permutate(array) do
--table.sort( combo, self.sortAlphabetical )
table.insert(board, combo);
end
return board;
end
It returns table of arrays each holding one permutation. After that i tried to write a recurrent function that takes rests of elements from C for each returned array and permutate them as well and so on. So it is basically something like "super non repeating permutation". But i couldn't get this to work:
local function getRest(str, inh)
local backbone, rest = {}, {};
for k,v in ipairs(C) do
backbone[v] = true;
end
for key in pairs(inh) do
for k,v in ipairs(C) do
if string.find(key, v) then backbone[v] = nil; end
end;
end;
for _, e in ipairs(C) do
if string.find(str, e) then backbone[e] = nil; end
end
if next(backbone) then
for obj in pairs(backbone) do
table.insert(rest, obj)
end
table.sort(rest, function(a, b)
return string.lower(a) < string.lower(b)
end)
end
return rest;
end;
local mainBoard = {};
local function superpermutation(permutation, inheritance)
inheritance = inheritance or {};
local px = getPermuations(permutation);
for _, array in ipairs(px) do
local r = getRest(table.concat(array), inheritance);
if #r>1 then
inheritance[table.concat(array)] = true;
superpermutation(r, inheritance);
elseif next(inheritance) then
local m = {};
for k in pairs(inheritance) do
table.insert(m, {k})
end;
if r and r[1] then
table.insert(m, {r[1]})
end
table.insert(mainBoard, m)
end;
end
return
end;
superpermutation(C);
for index, superarray in ipairs(mainBoard) do
local str = "";
for _, array in ipairs(superarray) do
str = str.."("..table.concat( array )..")"
end
print(str)
end
1 Answer
Reset to default 5Your problem can be solved by partitioning algorithm, such as Generate all partition of a set. The solution is implemented by using recursion to generate all possible partitions of the given set C. Here is the LUA implementation:
-- Function to generate all partitions of a set
local function generatePartitions(input, index, currentPartition, result)
if index == #input then
-- Convert the current partition to the desired format
local partition = {}
for _, group in ipairs(currentPartition) do
table.insert(partition, table.concat(group, ""))
end
table.insert(result, partition)
else
-- Add the current element to each existing group in the partition
for i = 1, #currentPartition do
table.insert(currentPartition[i], input[index + 1])
generatePartitions(input, index + 1, currentPartition, result)
table.remove(currentPartition[i]) -- backtrack
end
-- Create a new group with the current element
local newGroup = {input[index + 1]}
table.insert(currentPartition, newGroup)
generatePartitions(input, index + 1, currentPartition, result)
table.remove(currentPartition) -- backtrack
end
end
local input = {"a", "b", "c", "d", "e"}
local results = {}
generatePartitions(input, 0, {}, results)
-- Print all results
for _, result in ipairs(results) do
print("{" .. table.concat(result, ", ") .. "}")
end
Here is the output for your specific set C:
{abcde}
{abcd, e}
{abce, d}
{abc, de}
{abc, d, e}
{abde, c}
{abd, ce}
{abd, c, e}
{abe, cd}
{ab, cde}
{ab, cd, e}
{abe, c, d}
{ab, ce, d}
{ab, c, de}
{ab, c, d, e}
{acde, b}
{acd, be}
{acd, b, e}
{ace, bd}
{ac, bde}
{ac, bd, e}
{ace, b, d}
{ac, be, d}
{ac, b, de}
{ac, b, d, e}
{ade, bc}
{ad, bce}
{ad, bc, e}
{ae, bcd}
{a, bcde}
{a, bcd, e}
{ae, bc, d}
{a, bce, d}
{a, bc, de}
{a, bc, d, e}
{ade, b, c}
{ad, be, c}
{ad, b, ce}
{ad, b, c, e}
{ae, bd, c}
{a, bde, c}
{a, bd, ce}
{a, bd, c, e}
{ae, b, cd}
{a, be, cd}
{a, b, cde}
{a, b, cd, e}
{ae, b, c, d}
{a, be, c, d}
{a, b, ce, d}
{a, b, c, de}
{a, b, c, d, e}
n-1between-the-letters positions where you may place a comma, and you want all possible arrangements of them. All you need is a simple binary counter. – user58697 Commented Mar 9 at 18:07{ "aeb", "d", "c"};in your example, but it is supposed to be incorrect, is it? – Alexander Mashin Commented Mar 10 at 2:22