唯一排列生成器？

Question

问题：我有一些数字列表，例如 [1,1,2]。我需要生成唯一的排列组合。这些排列组合是 [1,1,2], [1,1,2], [1,2,1], [1,2,1], [2,1,1], [2,1,1]。我仅需要生成唯一的排列组合，即 [1,1,2], [1,2,1], [2,1,1]。

我的尝试：我第一次尝试是保留现有排列组合的集合，并创建一个过滤器用于 itertools.permutations 生成器，该过滤器将使用集合来过滤重复项。然而，由于效率原因，我宁愿不生成那些排列组合。即使对于仅含有12个数字的小列表，只有1％是唯一的。

我有一个初始想法，但似乎无法全部理解：我可以创建列表中唯一值的排列组合，即 [1,2]，并将剩余数字放在不同的位置中。

感谢任何帮助，并且明确表示，我不想过滤掉重复的排列组合，我想首先只生成唯一的排列组合。

- DanRedux

---

已经在这里解答过了：https://dev59.com/H2ox5IYBdhLWcg3wbDsk。 - ebarr

您能告诉我用于过滤重复项的最佳算法的时间复杂度是多少吗？如果有更好时间复杂度的预防算法，我想了解一下。 - Mohsen Kamrani

这里还有一个Python的答案：https://dev59.com/lW015IYBdhLWcg3w_Aug?rq=1 - ebarr

为什么不直接使用frozenset(itertools.permutations(seq))呢？在应用frozenset之前，可能需要将可变对象转换为不可变对象。 - jrennie

jrennie，这要求您将整个排列列表存储到内存中才能将其转换为集合。对于11个项目，这需要使用我计算机上的全部4GB RAM。13个项目，我可能可以存储在596GB的HDD上。15个项目，我将不得不依靠处理服务器农场上的列表，该农场占用120TB...实际上，我有256个项目，我需要多个宇宙的存储空间来存储其排列。（具体而言，我需要一个宇宙来存储我们宇宙中的每个原子，并且这些宇宙的每个原子都需要为我存储1个整数。） - DanRedux

Answer 1

我从之前的Stack Overflow答案中改编了这段代码：

def distinct_permutations(seq):
  from collections import Counter

  def perm_unique_helper(item_counts, perm, i):
    if i < 0:
      yield tuple(perm)
    else:
      for item in item_counts:
        if item_counts[item] <= 0:
          continue
        perm[i] = item
        item_counts[item] -= 1
        # In Python < 3.3 you can replace the yield from with a loop
        yield from perm_unique_helper(item_counts, perm, i - 1)
        item_counts[item] += 1

  item_counts = Counter(seq)
  L = len(seq)

  return perm_unique_helper(item_counts, [0] * L, L - 1)

我的笔记本电脑无法使用set(permutations(seq))方法处理长度为11的输入序列，但是使用这种方法可以！

- bbayles