为什么Python的和itertools.permutations包含重复？ （当原来的列表中有重复） [英] Why does Python's itertools.permutations contain duplicates? (When the original list has duplicates)

问题描述

人们普遍认为，n的列表的不同的的符号有n！排列。然而，当符号不显着，最常见的惯例，在数学和其他地方，似乎是只计算不同的排列组合。名单因此，排列 [1，1，2] 通常被认为是
[1，1，2]，[1，2，1]，[2，1，1] 。事实上，下面的C ++ code打印precisely这三种：

It is universally agreed that a list of n distinct symbols has n! permutations. However, when the symbols are not distinct, the most common convention, in mathematics and elsewhere, seems to be to count only distinct permutations. Thus the permutations of the list [1, 1, 2] are usually considered to be
[1, 1, 2], [1, 2, 1], [2, 1, 1]. Indeed, the following C++ code prints precisely those three:

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

在另一方面，Python的和itertools.permutations 似乎打印别的东西：

On the other hand, Python's itertools.permutations seems to print something else:

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指出，在应答中，<一个href="http://docs.python.org/release/2.6.6/library/itertools.html?highlight=itertools#itertools.permutations">Python文档是这么说的：

元素都基于它们的位置视为唯一的，而不是他们的价值。

Elements are treated as unique based on their position, not on their value.

我的问题：为什么作出这样的设计决策？

My question: why was this design decision made?

看来，按照通常的惯例将使结果更加有用（实际上通常正是我想要的）......或者是有Python的行为的一些应用程序，我失踪？

It seems that following the usual convention would give results that are more useful (and indeed it is usually exactly what I want)... or is there some application of Python's behaviour that I'm missing?

[或者是它的一些执行问题？该算法在 next_permutation - 计算器上，例如解释的这里（由我）和<一href="http://stackoverflow.com/questions/4973077/the-amortized-complexity-of-stdnext-permutation">shown这里是O（1）摊销 - 似乎是有效的和可实施在Python，但Python中做一些更有效，因为它并不能保证基于价值字典顺序？如果是的话，被认为是值得的，效率的提高？]

[Or is it some implementation issue? The algorithm as in next_permutation — for instance explained on StackOverflow here (by me) and shown here to be O(1) amortised — seems efficient and implementable in Python, but is Python doing something even more efficient since it doesn't guarantee lexicographic order based on value? And if so, was the increase in efficiency considered worth it?]

推荐答案

我不能为和itertools.permutations 的设计师（雷蒙德赫廷杰）说话，但似乎对我来说，有几个点的赞成设计的：

I can't speak for the designer of itertools.permutations (Raymond Hettinger), but it seems to me that there are a couple of points in favour of the design:

首先，如果你使用了 next_permutation 式的方法，那么你会被限制在传递支持线性排序的对象。而和itertools.permutations 提供的任意的类的对象排列。试想一下，如何讨厌这将是：

First, if you used a next_permutation-style approach, then you'd be restricted to passing in objects that support a linear ordering. Whereas itertools.permutations provides permutations of any kind of object. Imagine how annoying this would be:

>>> 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 __ 方法在通常情况下，这是没有必要的。

Second, by not testing for equality on objects, itertools.permutations avoids paying the cost of calling the __eq__ method in the usual case where it's not necessary.

基本上，和itertools.permutations 解决了通常情况下可靠和便宜。有肯定是要提出的论点，即 itertools 应该提供的功能，避免重复排列，但这样的功能应该是除了和itertools.permutations ，而不是相反它。为什么不写这样的功能，并提交补丁？

Basically, itertools.permutations solves the common case reliably and cheaply. There's certainly an argument to be made that itertools ought to provide a function that avoids duplicate permutations, but such a function should be in addition to itertools.permutations, not instead of it. Why not write such a function and submit a patch?

这篇关于为什么Python的和itertools.permutations包含重复？ （当原来的列表中有重复）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！