遞歸生成所有唯一置換的代碼？

說我有一個列表L=[1,2,3,3,4]，我想要遞歸地查找所有長度爲3的排列。遞歸生成所有唯一置換的代碼？

我試圖返回所有獨特的排列，這意味着類似[1,2,3]不包括在輸出中兩次，因爲L中有兩個3。

我問，因爲和itertools.permutations包括重複，還我試圖通過排列迭代爲了（從最低[1,2,3]迭代高達[4,3,3]），因爲我希望能夠退出迭代每當我需要。

如果我沒有正確解釋，我很抱歉。

編輯：我應該再說一遍。在實踐中，我不希望實際上生成每一個可能的排列（可能會有太多的），儘管代碼可能會跑到完成。我試圖按照特定的順序遍歷所有的排列，這樣我可以在必要的時候提早進行保釋。

來源

2012-11-15 John Smith

你想避免重複'[1,2,3]'，但是你也想在輸出中包含'[4,3,3]'？也許這是可能的，但對我來說似乎是不一致的... – senderle

@senderle那麼[1,2,3]可能與另一個[1,2,3]重複。 [4,3,3]本身仍然是一個有效的排列。 –

是的，但在一種情況下，您將「3」視爲相同，而在另一種情況下，您將它們視爲不同。做一個事後過濾器並不難，但我很難看到如何只產生你想要的值。你怎麼知道什麼時候把'3's視爲完全相同，何時將它們視爲不同的？再一次，也許這是可能的，但我不確定這個好處是否超過了複雜度的增加。 – senderle

如何：

l = [1,2,3,3,4] 

print sorted(set(itertools.permutations(l,3)))

輸出：

[(1, 2, 3), (1, 2, 4), (1, 3, 2), (1, 3, 3), (1, 3, 4), ..., (4, 3, 3)]

這使得它爲了和刪除重複。

如果你想避免產生每個可能的置換前手，我會做這樣的事情：

gen = itertools.permutations(l,3) 
s = set() 

for i in gen: 
    if i not in s: 
     print i # or do anything else 
    # if some_cond: break 
    s.add(i)

這裏gen是發電機，這樣你就不會預先創建所有您可能會使用的元素。

來源

2012-11-15 23:47:22 arshajii

儘管如此，這並不允許我通過即時迭代並在需要時從子循環中提取出來。如果可能，我正在尋找遞歸類型的方法。 –

@johnsmith - 我認爲你需要澄清你打算'紓困'的條件。 – Aesthete

@JohnSmith爲什麼你不能迭代？此外，我強烈建議不要重新發明輪子，並儘可能使用「itertools」（因爲它正是爲此而制定/優化的）。 – arshajii

遞歸生成所有唯一置換的代碼？

回答

相關問題