Python高效生成允许元素重复、不计顺序的定长子列表

现有长度为151的输入列表，需要从中生成长度为6的子列表，规则如下：

• 允许重复选取列表内的元素
• 子列表不考虑元素排列顺序，元素组成完全一致、仅排列顺序不同的子列表视为重复结果，仅保留一份

以输入list_given = [1, 2]为例，合法输出如下：

possible_sublists = [
[1, 1, 1, 1, 1, 1],
[1, 1, 1, 1, 1, 2],
[1, 1, 1, 1, 2, 2],
[1, 1, 1, 2, 2, 2],
[1, 1, 2, 2, 2, 2],
[1, 2, 2, 2, 2, 2],
[2, 2, 2, 2, 2, 2]
]

类似[1, 1, 1, 1, 1, 2]和[1, 1, 1, 1, 2, 1]这种仅排列不同的结果属于重复项，不需要输出。

原有实现的问题 #

之前尝试过两种实现，都存在明显缺陷：

1. 递归实现：递归深度过大，出现栈溢出问题
2. 6层嵌套for循环实现：总迭代次数高达151^6 = 11853911588401次，但根据可重复组合公式C(n+r-1, r)（即156选6）计算，实际合法结果仅为18161699556个，超过99.8%的迭代都是无效计算，时间复杂度极高。同时该实现用列表存储结果、每次通过Counter判断重复的去重逻辑，会随着结果集增大产生线性增长的判断开销，进一步拖慢运行速度。

原有实现代码如下：

from collections import Counter
def make_teams(poke):
    global_set = []
    for i in poke:
        for j in poke:
            for k in poke:
                for l in poke:
                    for m in poke:
                        for n in poke:
                            temp = Counter([i, j, k, l, m, n])
                            if temp not in global_set:
                                global_set.append(temp)
    return global_set

这个需求本质是数学上的可重复组合问题，直接使用Python标准库itertools提供的combinations_with_replacement即可实现零冗余计算，不需要额外去重逻辑。
该方法的核心逻辑是按非递减的索引选取元素，从根源上避免了仅排列不同的重复结果生成，总遍历次数恰好等于合法结果的总数，没有任何无效迭代。

基础实现（直接返回子列表元组） #

如果需要直接返回和示例格式一致的子列表，代码如下：

from itertools import combinations_with_replacement

def make_teams(poke):
    # 如果原列表本身有重复元素，取消注释下一行做保序去重
    # poke = list(dict.fromkeys(poke))
    return list(combinations_with_replacement(poke, 6))

适配原有返回格式（返回Counter列表） #

如果需要和原有实现一样返回Counter格式的结果，代码如下：

from itertools import combinations_with_replacement
from collections import Counter

def make_teams(poke):
    result = []
    # 原列表有重复元素时取消注释下一行做保序去重
    # poke = list(dict.fromkeys(poke))
    for combo in combinations_with_replacement(poke, 6):
        result.append(Counter(combo))
    return result

大结果集优化 #

由于最终合法结果有180亿条级别，全部加载到内存会占用极大存储空间，如果不需要一次性获取所有结果，可以直接遍历生成器逐个处理，避免内存溢出：

from itertools import combinations_with_replacement

# 逐个处理结果，不需要全部存入内存
for team in combinations_with_replacement(poke, 6):
    # 在这里写单条结果的处理逻辑
    pass

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