一尘不染

为什么Python的itertools.permutations包含重复项?(当原始列表重复时)

algorithm

普遍同意,由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)

正如用户ArtioimRudzenka在一个答案中指出的那样,Python文档如此指出:

元素根据其位置而不是其价值被视为唯一。

我的问题:为什么要做出此设计决定?

似乎遵循通常的约定会给出更有用的结果(实际上,这通常正是我想要的)……或者我缺少一些Python行为的应用程序?

[还是一些实施问题?像这样的算法next_permutation-例如在此处
-在Python中似乎是有效且可实现的,但由于Python不能保证基于字典顺序,因此它的工作效率更高。价值?如果是这样,效率的提高是否值得?


阅读 495

收藏
2020-07-28

共1个答案

一尘不染

我不能代表itertools.permutations(RaymondHettinger)的设计师,但在我看来,有两点支持该设计:

首先,如果您使用了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,而不是替代。为什么不编写这样的函数并提交补丁?

2020-07-28