“狼、胡萝卜、山羊”谜语强化版（在lua中生成表格）

2014-1-15 8:20:33
收藏：0
阅读：120
评论：2

我有一个包含大量元素的数组，并希望尽可能多地将它们分组，使每个组作为新数组中的一个元素。但有些元素是不兼容的，例如：

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

就是这样。这里我是否漏掉了更简单的方法？

点赞
用户646619
用户646619

你可以先生成列表的所有可能排列，然后再减去你不想要的项目。

你可以使用递归来生成排列，而不需要很多循环。参见Algorithm to generate all possible permutations of a list?。你可以将算法适应到筛选表中进行检查并简单地忽略不合适的结果，或者在生成的结果中直接移除它们。

2014-01-15 03:56:02
用户869951
用户869951

请注意，如果您有一个长度为n的列表的所有组合的集合S（n），它等于S（n-1）+ {list \ [1 ]与S（n-1）中的每个组合}其中S（n-1）是列表右边n-1个项目的所有组合的集合。这意味着您可以拥有递归函数。由于Lua没有剪接操作（与Python或Lisp相反），因此我们使用“rightLen”索引，该索引是要使用的项目数，从右侧开始：

function getAllCombinations(list, rightLen)
    local N =＃list
    rightLen = rightLen或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个项目，在我的笔记本电脑VM上看起来瞬间就完成了，对于17个项目它需要1秒钟，对于19个项目需要5秒钟。指数增长当然。复制很糟糕，也许以下内容会获得更快的结果：

local combos = {}  - 旧版：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％。

2014-01-15 07:55:04

作者:

用户2395058

用户2395058
推荐文章