为什么Python的itertools.permutations包含重复项？ （当原始列表重复时）
普遍认为，n个不同符号的列表有n！ 排列。 但是，当符号不明确时，在math和其他地方最常见的惯例似乎是只计算不同的排列。 因此，列表[1, 1, 2] 1,1,2 [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文档中这样说：
元素根据他们的位置被视为唯一的，而不是他们的价值。
我的问题：为什么这个devise决定了？
看来按照惯例，会给出更有用的结果（实际上它通常正是我想要的），还是有一些我缺less的Python行为的应用程序？
[或者是一些执行问题？ 在next_permutation的algorithm – 例如在这里（由我）在这里解释StackOverflow ，并在这里显示为O（1）摊销 – 看起来是有效的，并且可以在Python中实现，但Python做的事情更有效，因为它不保证字典顺序基于价值？ 如果是的话，效率提高是否值得呢？]
我不能代表itertools.permutations （Raymond Hettinger）的devise师，但在我看来，有一些赞成devise的观点：
首先，如果你使用next_permutation风格的方法，那么你只能传入支持线性sorting的对象。 而itertools.permutations提供了任何types的对象的排列。 想象一下，这将是多么令人讨厌：
>>> 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
其次，通过不testing对象上的相等性， itertools.permutations避免了在通常情况下不需要调用__eq__方法的代价。
基本上， itertools.permutations可靠而廉价地解决了常见的情况。 当然有一个论点需要提出， itertools应该提供一个避免重复排列的函数，但是除了itertools.permutations之外，这个函数应该不是itertools.permutations而是它。 为什么不写这样的function并提交补丁？
我接受Gareth Rees的答案作为最吸引人的解释（Python库devise者的答案不足），即Python的itertools.permutations没有比较元素的值。 想一想，这就是问题所在，但是我现在看到它是如何被看作是一个优势，取决于通常使用itertools.permutations 。
为了完整起见，我比较了三种产生所有不同排列的方法。 方法1是非常低效的记忆方式和时间方式，但要求最less的新代码，就是包装Python的itertools.permutations ，就像zeekay的答案一样。 方法2是C ++的next_permutation一个基于生成器的版本，来自这个博客文章 。 方法3是我写的更接近于C ++的next_permutationalgorithm ; 它就地修改了这个列表（我没有把它做得太笼统）。
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
代码在这里，如果有人想探索。
通过包装itertools.permutations来获得您喜欢的行为是相当容易的，这可能会影响决策。 如文档中所述， itertools被devise为构build您自己的迭代器的构build块/工具的集合。
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的新function或可选参数可以被添加到itertools ，以更有效地产生排列而不重复。
我也觉得itertools没有更直观的独特排列概念的function。 生成重复排列只是为了select其中的唯一对于任何严重的应用程序来说都是不可能的。
我写了自己的迭代生成器函数，其行为与itertools.permutations类似，但不返回重复。 只考虑原始列表的排列，可以使用标准的itertools库创build子列表。
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)
也许我错了，但似乎这样做的理由是： “元素根据他们的位置被视为唯一的，而不是他们的价值。 所以如果input元素是唯一的，那么在每个排列中都不会有重复的值。 你已经指定了（1,1,2），从你的angular度来看1在0索引和1在1索引是一样的 – 但是这并不是如此，因为排列python实现使用索引而不是值。
所以如果我们看一下默认的python permutations实现，我们会看到它使用索引：
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)
例如，如果将input更改为[1,2,3]，则将得到正确的排列（[（1，2，3），（1,3,2），（2，1，3），（2，3 ，1），（3,1,2），（3,2,1）]），因为这些值是唯一的。
