為什么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<

另一方面，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 "", line 1, in 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)])，因為這些值是唯一的。

總結

以上是生活随笔為你收集整理的permutations python_为什么Python的itertools.permutations包含重复项？ （当原始列表重复时）...的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。