为什么 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 是否在做一些更高效的事情，因为它不保证基于值的字典顺序？如果是这样，效率的提高是否值得？]

Answer 1

我不能代表 itertools.permutations 的设计者（Raymond Hettinger）说话，但在我看来，有几点支持该设计：

首先，如果您使用 next_permutation 式的方法，那么您将被限制只能传入支持线性排序的对象。而 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 的补充，而不是代替它。为什么不写一个这样的函数并提交补丁呢？

Answer 2

我接受 Gareth Rees 的答案作为最吸引人的解释（缺少 Python 库设计者的答案），即 Python 的 itertools.permutations 不比较元素的值。想想看，这就是问题所问的问题，但我现在明白了如何将其视为一种优势，具体取决于人们通常使用 itertools.permutations 的用途。

为了完整起见，我比较了生成所有不同排列的三种方法。方法 1 的内存和时间效率非常低，但需要的新代码最少，它是包装 Python 的 itertools.permutations，如 zeekay 的答案所示。方法 2 是 C++ next_permutation 的基于生成器的版本，来自 此博文。方法 3 是我写的，它更接近 C++ 的 next_permutation 算法< /a>；它就地修改列表（我没有把它做得太笼统）。

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

如果有人想探索，代码位于此处。

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 的可选参数到itertools，更有效地生成没有重复的排列。

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)

Answer 5

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

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)]) 因为这些值是唯一的。