Python中如何按含重复元素的参考列表生成目标列表的全部合法排序

首先明确核心规则：参考列表排序后，相同值对应的原目标列表元素仅可在对应值的位置区间内任意排列，不可跨区间调换位置。例如你给出的示例中，参考列表排序后分为「1的位置区间、2的位置区间、3的位置区间」，1对应的原字母a、d、f只能在第一个区间排列，2对应的b、e只能在第二个区间排列，3对应的c固定在最后一位。

高效实现方案 #

我们可以借助Python标准库itertools的内置方法实现，底层为C语言实现，性能远高于自定义递归逻辑，且是理论最优效率：因为合法结果的总数量本身就是各组元素数量阶乘的乘积，没有比遍历所有排列组合更快的方案。

完整代码示例 #

from itertools import permutations, product
from collections import defaultdict

# 输入示例
numbers = [1, 2, 3, 1, 2, 1]
letters = ['a', 'b', 'c', 'd', 'e', 'f']

# 步骤1：按参考列表的值分组，收集对应的目标元素
group_map = defaultdict(list)
for num, letter in zip(numbers, letters):
    group_map[num].append(letter)

# 步骤2：按参考列表的排序规则获取分组顺序（示例为升序，可根据需求调整排序规则）
sorted_group_keys = sorted(group_map.keys())
sorted_groups = [group_map[key] for key in sorted_group_keys]

# 步骤3：生成每个分组的所有全排列
group_permutation_list = [permutations(group) for group in sorted_groups]

# 步骤4：对各组排列做笛卡尔积，拼接得到所有合法结果
all_valid_results = []
for group_perm_comb in product(*group_permutation_list):
    # 拼接多组排列为完整列表
    full_perm = sum(group_perm_comb, ())
    all_valid_results.append(list(full_perm))

# 验证结果：示例中总共有3! * 2! * 1! = 12种合法结果
print(len(all_valid_results))  # 输出12
print(all_valid_results[0])    # 输出['a', 'd', 'f', 'b', 'e', 'c']
print(all_valid_results[-1])   # 输出['f', 'd', 'a', 'e', 'b', 'c']

适配优化说明 #

如果需要调整参考列表的排序规则，只需要修改sorted(group_map.keys())的排序逻辑即可，比如改为倒序、自定义排序函数都可以。
如果列表规模很大、结果数量太多导致内存占用过高，可以改为迭代器模式逐次返回结果，不需要一次性存入列表：

def generate_all_valid_arrangements(numbers, letters):
    group_map = defaultdict(list)
    for num, letter in zip(numbers, letters):
        group_map[num].append(letter)
    sorted_groups = [group_map[k] for k in sorted(group_map.keys())]
    group_perms = [permutations(g) for g in sorted_groups]
    for comb in product(*group_perms):
        yield list(sum(comb, ()))

# 使用迭代器逐次获取结果，适合大规模数据
for arrangement in generate_all_valid_arrangements(numbers, letters):
    # 处理单个排列
    print(arrangement)

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