不使用itertools实现带重复的Python列表全组合算法问询

没问题，我来帮你搞定这个需求！你要的其实是生成长度等于原列表长度的带重复元素的所有有序组合（本质是原列表自身的笛卡尔积，重复len(lst)次），不用itertools完全可以实现。我先给你完善你已经开始写的迭代版本，再给你一个递归版本作为参考。

你的代码已经有了迭代的雏形，不过初始的result = [list]是不对的，我们需要从长度为1的组合开始，逐步构建到目标长度。具体思路是：

• 先初始化结果列表为原列表中每个元素单独组成的列表（长度为1的所有可能）
• 然后循环len(lst)-1次，每次把当前所有组合和原列表的每个元素拼接，生成更长的组合
• 最终得到的就是长度等于原列表长度的所有带重复的有序组合

完整代码如下：

def all_possibilities(lst):
    # 初始化：长度为1的所有组合
    result = [[x] for x in lst]
    # 需要再拼接 len(lst)-1 次，让组合长度达到 len(lst)
    for _ in range(len(lst) - 1):
        temp = []
        # 遍历当前所有已有的组合
        for combo in result:
            # 遍历原列表的每个元素，拼接到组合末尾
            for num in lst:
                temp.append(combo + [num])
        # 更新结果为新生成的更长的组合
        result = temp
    return result

测试示例 #

比如测试你的第一个例子：

print(all_possibilities([1,2]))
# 输出：[[1,1], [1,2], [2,1], [2,2]]

测试第二个例子：

output = all_possibilities([1,2,3])
print(len(output))  # 输出：27
print(output[:5])   # 前5个组合：[[1,1,1], [1,1,2], [1,1,3], [1,2,1], [1,2,2]]

如果你更喜欢简洁的递归写法，思路是：

• 递归终止条件：当需要生成的组合长度为0时，返回包含空列表的列表（作为基础拼接单元）
• 否则，遍历原列表的每个元素，递归生成长度为length-1的所有组合，然后把当前元素加到每个组合的开头（或末尾），收集所有结果

代码如下：

def all_possibilities_recursive(lst):
    def helper(length):
        if length == 0:
            return [[]]
        # 递归生成更短的组合，再拼接当前元素
        shorter_combos = helper(length - 1)
        return [[num] + combo for num in lst for combo in shorter_combos]
    
    # 目标长度是原列表的长度
    return helper(len(lst))

测试递归版本 #

print(all_possibilities_recursive([1,2]))
# 同样输出：[[1,1], [1,2], [2,1], [2,2]]

两种方法都能满足你的需求，迭代版本更适合理解过程，递归版本代码更简洁。如果你的列表长度很大，迭代版本可能更稳妥（避免递归栈溢出），但一般日常使用的列表长度，两种方法都没问题。

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