为什么Python的itertools.permutations会包含重复项？（当原始列表中存在重复项时）

Question

普遍认为具有n 不同 符号的列表有n！种排列方式。但是，当符号不是不同的时，数学和其他领域中最常见的约定似乎是仅计算独特的排列方式。因此，通常认为列表[1, 1, 2]的排列方式为
[1, 1, 2], [1, 2, 1], [2, 1, 1]。实际上，下面的C ++代码恰好打印了这三个排列方式:

int a[] = {1, 1, 2};
do {
    cout<<a[0]<<" "<<a[1]<<" "<<a[2]<<endl;
} while(next_permutation(a,a+3));

另一方面，Python的itertools.permutations似乎打印了其他内容：

import itertools
for a in itertools.permutations([1, 1, 2]):
    print a

这将会打印出来

(1, 1, 2)
(1, 2, 1)
(1, 1, 2)
(1, 2, 1)
(2, 1, 1)
(2, 1, 1)

正如用户Artsiom Rudzenka在答案中指出的那样，Python文档中有所说明：

元素是基于它们的位置而非值来视为唯一的。

我的问题是：为什么要做出这个设计决定？

按照通常的惯例似乎会产生更有用的结果（实际上这通常正是我想要的）... 或者我是否忽略了Python行为的某些应用？

[还是说这是某种实现上的问题？像next_permutation 算法——例如在StackOverflow中由我解释并且被证明是O(1)平摊复杂度的 —— 在Python中似乎很高效且易于实现，但是Python是否做出了更加高效的方法，因为它不保证基于值的字典序？如果是这样，那增加的效率是否值得考虑？]

- ShreevatsaR

---

根据文档，Python确实保证字典序顺序。 - Björn Pollex

上面的输出示例似乎没有排序（1,2,1出现在1,1,2之前）。也许是因为元素不唯一？ - Macke

@Macke：是的，这就是我的意思——词典顺序是基于位置而不是值。如果你把两个1看作"1"和"1+"，第二个更大，那么(1,2,1+)在(1+,1,2)之前是可以的。但当然，1就是1。 :-) 另外，如果你要求[3,2,1]的排列组合（比如说），结果实际上会按照反向词典顺序排列。如果你要求[2,1,3]，它们将不会按照任何一种顺序排列。重点是Python只关注位置而不是值。 - ShreevatsaR

我也在想。特别是因为“元素基于它们的位置而不是它们的值被视为唯一”，这似乎是多余的 - 只有一个元素可以占据一个特定的位置，所以基本上他们是在说“我们假设所有元素都是不同的”或者“我们不检查解决方案的唯一性”。 - pfctdayelise

Answer 1

我不能代表itertools.permutations的设计者（Raymond Hettinger），但我认为这个设计有几个优点：

首先，如果你使用next_permutation-style方法，那么你只能传递支持线性排序的对象。而itertools.permutations提供任何类型对象的排列组合。想象一下这会有多烦人：

>>> list(itertools.permutations([1+2j, 1-2j, 2+j, 2-j]))
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: no ordering relation is defined for complex numbers

不测试对象的相等性，itertools.permutations 避免在通常情况下不必要时调用 __eq__ 方法的开销。

基本上，itertools.permutations 可以可靠且廉价地解决常见问题。当然，可以提出这样的观点，即 itertools 应该提供一个避免重复排列的函数，但此类函数应作为 itertools.permutations 的补充，而不是替代它。为什么不编写这样一个函数并提交一个补丁呢？

- Gareth Rees

---

谢谢，这是一个很好的观点，有时候人们想要元素的排列顺序是不可比较的 - 为这种情况编写代码，并且不查看值，确实使itertools.permutations非常快。当然，这是否实际上是“通常情况”和“常见情况”取决于用户。 :-) 另外，提交补丁到Python库并跟踪其进展的整个过程有多容易？ - ShreevatsaR

很好的回答，关于效率也提出了很好的观点。然而，我并不认为这是itertools.permutations保留重复项的好理由。要求元素可比较对于排列来说是完全合理的。如果有人明确想要位置的排列，可以明确地编写：([it[index] for index in indexes] for indexes in itertools.permutations(range(len(it)))) - Neil G

我有点困惑，为什么你需要线性排序来进行unique_permutation？难道你不只需要相等性测试吗？ - Ehsan Kia

@EhsanKia：看看OP建议Python使用的next_permutation实现方式。它使用被排列对象上的<运算符来找到当前排列之后的最小排列。（显然，有各种方法可以解决这个问题，但它们会使建议的方法不那么吸引人。） - Gareth Rees

@NeilG，你的观点是很容易获得索引排列，只需按照OP所需的功能实现即可，这是一个强有力的观点。看起来OP的设计解决了当前实现处理的所有用例以及其他常见用例。而当前实现不能以简单的方式解决附加用例。 - Him

@Scott 我刚刚添加了一个答案。即使我们认为他们的决定是不合理的，标准库可能不会改变。 - Neil G

Answer 2

我认为Gareth Rees的回答是最具吸引力的解释（除了来自Python库设计者的回答），即Python的itertools.permutations并不比较元素的值。想一想，这正是问题所问，但现在我明白了，这可能取决于一个人通常使用itertools.permutations的目的。

仅为完整起见，我比较了生成所有不同排列的三种方法。方法1非常低效，无论在内存或时间上都如此，但需要的新代码最少，即像zeekay的回答那样包装Python的itertools.permutations。方法2是基于生成器的C++ next_permutation版本，来自这篇博客文章。方法3是我编写的，甚至更接近于C++的next_permutation算法；它在原地修改列表（我没有使它太通用）。

def next_permutationS(l):
    n = len(l)
    #Step 1: Find tail
    last = n-1 #tail is from `last` to end
    while last>0:
        if l[last-1] < l[last]: break
        last -= 1
    #Step 2: Increase the number just before tail
    if last>0:
        small = l[last-1]
        big = n-1
        while l[big] <= small: big -= 1
        l[last-1], l[big] = l[big], small
    #Step 3: Reverse tail
    i = last
    j = n-1
    while i < j:
        l[i], l[j] = l[j], l[i]
        i += 1
        j -= 1
    return last>0

这里是一些结果。我对Python内置函数的尊重更加深刻了：当元素全部（或几乎全部）不同的时候，它的速度大约是其他方法的三到四倍。当然，如果有很多重复的元素，使用它就是一个可怕的想法。

Some results ("us" means microseconds):

l                                       m_itertoolsp  m_nextperm_b  m_nextperm_s
[1, 1, 2]                               5.98 us       12.3 us       7.54 us
[1, 2, 3, 4, 5, 6]                      0.63 ms       2.69 ms       1.77 ms
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]         6.93 s        13.68 s       8.75 s

[1, 2, 3, 4, 6, 6, 6]                   3.12 ms       3.34 ms       2.19 ms
[1, 2, 2, 2, 2, 3, 3, 3, 3, 3]          2400 ms       5.87 ms       3.63 ms
[1, 1, 1, 1, 1, 1, 1, 1, 1, 2]          2320000 us    89.9 us       51.5 us
[1, 1, 2, 2, 3, 3, 4, 4, 4, 4, 4, 4]    429000 ms     361 ms        228 ms

如果有人想要探索，代码可以在这里找到。

- ShreevatsaR

---

结果表中的方法 m_itertoolsp，m_nextperm_b 和 m_nextperm_s 分别指的是方法1、2和3吗？ - Isaac Turner

你可以使用以下代码将尾部翻转：l[last:n] = p[n-1:last-1:-1] - Isaac Turner

@IsaacTurner，看来我错过了你的评论。是的，它们指的是答案中的方法1、2和3。我还没有尝试过反转尾部的另一种方式……虽然这样可以使代码更短，但我还没有考虑它的性能如何。 - ShreevatsaR

Answer 3

通过包装itertools.permutations，很容易获得您喜欢的行为方式，这可能会影响决策。正如文档所述，itertools被设计为一组构建块/工具，可用于构建自己的迭代器。

def unique(iterable):
    seen = set()
    for x in iterable:
        if x in seen:
            continue
        seen.add(x)
        yield x

for a in unique(permutations([1, 1, 2])):
    print a

(1, 1, 2)
(1, 2, 1)
(2, 1, 1)

然而，正如评论中指出的那样，这可能并不像你想象的那样高效：

>>> %timeit iterate(permutations([1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2]))
1 loops, best of 3: 4.27 s per loop

>>> %timeit iterate(unique(permutations([1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2])))
1 loops, best of 3: 13.2 s per loop

如果有足够的兴趣，可以向 itertools.permutations 添加一个新函数或可选参数，以更有效地生成不重复排列。

- Zach Kelling

---

+1. 如果想要独特的排列，这就是你需要做的事情。非独特排列也可能很有用（和有趣），但计算起来更昂贵。 - Macke

生成所有排列的复杂度是Ω(n!)，实际上我认为它是Ω(nn!)，因为你需要Ω(n)的时间来比较排列，相对于具有重复项的列表而言，这非常非常糟糕（因此实际*排列数远小于n！）。请参见例如此帖子。 - ShreevatsaR

不要使用[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2]，尝试再加几个1，比如[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2]——这至少需要多花一百倍的时间。 :-) - ShreevatsaR

确实！出于好奇，考虑以下列表：[1, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]，使用permutations比新的next_permutations实现更有效吗？主要优点是避免为已经生成的对象生成额外的排列，对吗？ - Zach Kelling

这个解决方案的另一个严重问题是内存：由于你将所有已经看到的排列都保存在一个“set”中，所以你需要的内存量就等于所有排列的总大小...这有点违背使用“itertools”的初衷。（例如对于[1,2,3,4,5,6,7,8,9,10]，需要在内存中保存所有的10！≈ 300万个排列，这相当于几兆字节。） - ShreevatsaR

Answer 4

我认为令人惊讶的是 itertools 没有用于更直观的唯一排列概念的函数。生成重复排列，只为选择其中唯一项，在任何严肃的应用程序中都是不可行的。

我编写了自己的迭代生成函数，其类似于 itertools.permutations，但不会返回重复项。只考虑原始列表的排列，可以使用标准的 itertools 库创建子列表。

def unique_permutations(t):
    lt = list(t)
    lnt = len(lt)
    if lnt == 1:
        yield lt
    st = set(t)
    for d in st:
        lt.remove(d)
        for perm in unique_permutations(lt):
            yield [d]+perm
        lt.append(d)

- Sasho

---

谢谢。在我上面的回答中，我有一个代码链接，其中包含3种方法和一些时间比较 - 你能测试一下你的unique_permutations与m_itertoolsp、m_nextperm_b和m_nextperm_s相比有多快吗？ - ShreevatsaR

我按照你的建议测试了速度，果然毫不意外地，我的代码比你建议的两个选项慢5到10倍。递归和列表修改是有代价的。尽管如此，它轻松击败了itertools的变通方法，优势高达百倍。我只是提出它作为另一种选择，如果它恰好更适合不同的目的，那么可能会有人找到改进的方法。 - Sasho

Answer 5

重新审视这个老问题，现在最简单的方法是使用more_itertools.distinct_permutations。

- Neil G

---

是的，more_itertools版本运行非常高效。 实现了在此处描述的方法：https://en.wikipedia.org/wiki/Permutation#Generation_in_lexicographic_order 我还测试了上述实现版本。它们也很棒。 - pvoj

Answer 6

也许我错了，但似乎这是由于“元素基于其位置而不是其值被视为唯一。因此，如果输入元素是唯一的，每个排列中就不会重复值。” 你指定了(1,1,2)，从你的角度来看，索引为0的位置上的1和索引为1的位置上的1是相同的 - 但实际并非如此，因为排列的 Python 实现使用索引而不是值。

所以，如果我们看一下默认的 Python 排列实现，我们会发现它使用的是索引：

def permutations(iterable, r=None):
    pool = tuple(iterable)
    n = len(pool)
    r = n if r is None else r
    for indices in product(range(n), repeat=r):
        if len(set(indices)) == r:
            yield tuple(pool[i] for i in indices)

例如，如果您将输入更改为[1,2,3]，则会得到正确的排列组合（[(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)]），因为这些值是唯一的。

- Artsiom Rudzenka

---

为什么会以这种方式实施，而我们通常期望其他的方式呢？ - Björn Pollex

@Space_C0wb0y - 抱歉 - 那么这个问题应该问那些已经实现了Python的人。他们会给我们教程和API参考，因此我们可以使用它的基本功能，如果对我们不可接受的话。但从教程的角度来看，这种方法是正确的。 - Artsiom Rudzenka

是的，Space_C0wb0y说得对：我的问题就在于为什么会这样。可能的一个解释是它根本没有考虑到包含重复项的列表，如果找到了相关的参考资料，那就是一个答案。但也可能有其他的解释。我认为关于语言设计背后的决策的问题并不完全超出了这个网站的范围：参与语言设计、或者可以访问相关讨论、或者对这个问题有一些见解的人群，可能与这个网站的用户有着非常重要的交集。 - ShreevatsaR