类固醇"wolf, carrot, goat"谜语(在lua中生成表)

Question

我有一个数组，里面有很多元素，我想尽可能多地对它们进行分组，使每组都成为新数组中的一个元素。然而，某些元素是不兼容的，例如：

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

我想生成一个数组，其中包含所有兼容的对象排列，没有重复项。这个数组的一个元素可以包含任意数量的对象，甚至是单个对象，只要它的内容都是兼容的。

在上面的例子中，它看起来是这样的：

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

我考虑的一个可能的解决方案是一个函数，它接受任意数量的参数，并将它们相互比较，例如：

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
...

但要实现这一点，我需要有与函数参数一样多的嵌套for循环。不知道怎么做。

一旦解决了这个问题，检查其中两个参数是否构成了不兼容数组的一个元素就相当简单了。

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

所以我认为无论如何。有没有一种我遗漏的更简单的方法？

Answer 1

注意，如果您有一个长度为n的列表的所有组合的集合S(n)，它等于S(n-1)+{list[1]，其中S(n--1)是列表最右边n-1项列表的所有结合的集合。这意味着您可以使用递归函数。由于Lua没有拼接操作(与python或lisp相反)，我们使用索引"rightLen"，这是要使用的#项，从右端开始：

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

table.copy被定义为

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

我不知道这是否是最好的表现。14个项目在我的笔记本电脑虚拟机上看起来是即时的，17个项目需要1秒，19个项目需要5秒。当然是指数增长。复制是令人讨厌的，也许以下会给出更快的结果：

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

和table.copy可以简单地成为

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

这似乎快了40%。

Answer 2

您可以首先生成列表的所有可能排列，然后减去不需要的项。

您可以使用递归生成排列，而不需要大量的循环。请参阅生成列表的所有可能排列的算法？。您可以调整算法以检查您的筛选表，并简单地忽略有问题的结果，或者稍后简单地将它们从结果中删除。