python itertools與綁定值排列

我想查找有效具有綁定值的向量的排列。python itertools與綁定值排列

例如，如果我希望獲得作爲輸出等等[0,0,1,2], [0,0,2,1], [0,1,2,0]所有組合，但我不希望獲得[0,0,1,2]兩次這是什麼標準itertools.permutations(perm_vector)會給。

我嘗試以下，但是當perm_vector grows的len它的工作原理很慢：

的問題是更普遍的「加速」的性質，實際上。主要時間用於創建長向量的排列 - 即使沒有重複性，創建12個唯一值向量的排列也需要「無窮大」。是否有可能迭代調用itertools而不訪問整個排列數據，但是對其進行處理？

來源

2016-01-11 user3861925

的[爲什麼Python的和itertools.permutations包含重複可能的複製？（當原始列表有重複時）]（http://stackoverflow.com/questions/6534430/why-does-pythons-itertools-permutations-contain-duplicates-when-the-original） –

這裏是一個外部[鏈接]（ http://blog.bjrn.se/2008/04/lexicographic-permutations-using.html）來自上述評論引用的線索中的評論，這可能是有幫助的。 – Praveen

在itertools模塊中有這樣的配方，請檢查unique_everseen配方：https：//docs.python.org/3/library/itertools.html#itertools-recipes – Copperfield

如何：

from collections import Counter 

def starter(l): 
    cnt = Counter(l) 
    res = [None] * len(l) 
    return worker(cnt, res, len(l) - 1) 

def worker(cnt, res, n): 
    if n < 0: 
     yield tuple(res) 
    else: 
     for k in cnt.keys(): 
      if cnt[k] != 0: 
       cnt[k] = cnt[k] - 1 
       res[n] = k 
       for r in worker(cnt, res, n - 1): 
        yield r 
       cnt[k] = cnt[k] + 1

來源

2016-02-01 12:35:34

試試這個，如果perm_vector小：

import itertools as iter 
{x for x in iter.permutations(perm_vector)}

這應該給你獨特的價值觀，因爲現在它變成一組，默認情況下刪除重複。

如果perm_vector很大，你可能會想嘗試回溯：

def permu(L, left, right, cache): 
    for i in range(left, right): 
     L[left], L[i] = L[i], L[left] 
     L_tuple = tuple(L) 
     if L_tuple not in cache:     
      permu(L, left + 1, right, cache) 
      L[left], L[i] = L[i], L[left] 
      cache[L_tuple] = 0 
cache = {} 
permu(perm_vector, 0, len(perm_vector), cache) 
cache.keys()

來源

2017-03-22 17:03:13 Rose

儘管這在技術上有效，但它在過濾之前仍然會生成所有重複的排列，因此當有很多重複項時它效率極低。 – user2357112

@ user2357112的確如此。如果列表很大，可能需要使用回溯和記憶來提高效率。我上面發佈了我的代碼（如果有一種方法可以避免「for循環」中的「if」），那麼會很好。 – Rose

python itertools與綁定值排列

回答

相關問題