如何高效生成含重复排名列表的所有无重复有效重排结果

规则说明 #

• 得分相近理论上可赋予相同排名，但排名不可重复
• 具体示例：
  • 输入[1,1,2]，输出可为[1,2,3]、[2,1,3]
  • 输入[1,1,1]，输出可为任意不重复排列（如[1,2,3]、[1,3,2]…[3,2,1]）
  • 输入[2,1,2]，输出可为[2,1,3]、[3,1,2]
  • 输入[1,2,3]，无其他合法重排结果，输出为None
  • 输入[1,2,2]，输出可为[1,2,3]、[1,3,2]

现有问题与已实现代码 #

• 现有Stack Overflow方案会生成重复排名，不符合需求
• 已编写代码生成各原始排名对应的可替换采样池：

from collections import Counter
from itertools import permutations
import random 

ranks = [1,2,2,3,3,1,1,2,4,2]
counter = Counter(ranks)
sorted_counter = dict(sorted(counter.items(), key = lambda x: x[0]))
print(sorted_counter)

range_to_from = {1:(1,counter[1])}
sample_from = {}# 原始排名为i的位置，可替换为该范围内的任意数字

for key,val in sorted_counter.items():
    if key == 1:
        sample_from[1] = list(range(val+1))
        continue
    else:
        start, end = (range_to_from[key-1][-1]+1, range_to_from[key-1][-1]+val)
        range_to_from[key] = (start,end)
        sample_from[key] = list(range(start,end+1))

需求 #

若通过循环生成所有排列再逐一比对去重，时间成本过高，寻求高效解决方案。

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