Lua实现数组字符串无重复嵌套全组合的技术方案咨询

核心思路 #

我们要生成的是原数组元素顺序不变、元素不重复使用的所有非空子序列拼接结果。简单来说，就是从原数组中挑选任意数量（1到n）的元素，严格保持它们在原数组中的先后顺序拼接成字符串，自动排除逆序（如ba）、重复元素（如aba）的非法组合。

实现上采用递归逻辑最直观：

• 维护当前已拼接的字符串和当前处理到的数组索引
• 对每个元素做两种选择：包含它（拼接到当前字符串后递归处理下一个元素），或不包含它（直接递归处理下一个元素）
• 处理完所有元素时，若当前字符串非空，则加入结果集合

代码实现 #

function generateOrderedCombinations(arr)
    local result = {}
    local function recurse(currentStr, index)
        -- 处理完所有元素，非空字符串加入结果
        if index > #arr then
            if currentStr ~= "" then
                table.insert(result, currentStr)
            end
            return
        end
        -- 分支1：包含当前元素，拼接后递归
        recurse(currentStr .. arr[index], index + 1)
        -- 分支2：不包含当前元素，直接递归
        recurse(currentStr, index + 1)
    end
    -- 从第一个元素开始递归，初始字符串为空
    recurse("", 1)
    return result
end

-- 测试示例
local C = {"a","b","c","d","e"}
local combinations = generateOrderedCombinations(C)
-- 按长度+字典序排序输出，更易查看
table.sort(combinations, function(a,b) 
    return #a < #b or (#a == #b and a < b) 
end)
for _, str in ipairs(combinations) do
    print(str)
end

代码说明 #

1. 递归函数recurse：参数currentStr记录当前已拼接的字符串，index标记当前处理的数组位置。
2. 终止条件：当index超出数组长度时，检查currentStr是否非空，非空则加入结果列表。
3. 双分支逻辑：通过两种选择遍历所有合法组合，确保只保留原数组顺序的拼接结果。
4. 结果排序：最后按字符串长度升序、同长度按字典序排序，方便验证结果。

验证结果 #

对于输入{"a","b","c","d","e"}，输出共31个合法组合（2^5-1），包含：

• 单个元素：a、b、c、d、e
• 两个元素：ab、ac、ad、ae、bc、bd、be、cd、ce、de
• 三个元素：abc、abd、abe、acd、ace、ade、bcd、bce、bde、cde
• 四个元素：abcd、abce、abde、acde、bcde
• 五个元素：abcde

如果原数组含重复元素（如{"a","a","b"}），可改用集合去重：

-- 带去重的版本
function generateUniqueOrderedCombinations(arr)
    local resultSet = {}
    local result = {}
    local function recurse(currentStr, index)
        if index > #arr then
            if currentStr ~= "" and not resultSet[currentStr] then
                resultSet[currentStr] = true
                table.insert(result, currentStr)
            end
            return
        end
        recurse(currentStr .. arr[index], index + 1)
        recurse(currentStr, index + 1)
    end
    recurse("", 1)
    table.sort(result, function(a,b) 
        return #a < #b or (#a == #b and a < b) 
    end)
    return result
end

内容的提问来源于stack exchange，提问作者Aer