为什么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)的设计师,但在我看来,有几点赞成设计:

首先,如果您使用了a- next_permutationstyle方法,那么您将被限制为传递支持线性排序的对象.而是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,内存和时间非常低效但需要最少的新代码itertools.permutations,就像包装Python一样,就像在zeekay的回答中一样.方法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

如果有人想探索,代码就在这里.

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,以更有效地生成没有重复的排列.