使用堆棧列表的排列

我試圖找到一種方法來枚舉數字列表的所有組合，而無需遞歸或使用itertools。我想出了一個可行的解決方案，但我認爲它終究變成了遞歸函數。我是Python新手，不確定如何在沒有遞歸的情況下完成這項工作。使用堆棧列表的排列

任何幫助表示讚賞，因爲我認爲我仍然沒有看到兩者之間的區別。

result = [] 

def permutation(li): 
    if len(li) == 1: 
     result.append(li[0]) 
     print (result) 
     result.pop() 
     return 

    for i in range(0,len(li)): 
     result.append(li[i]) 
     permutation(li[:i] + li[i+1:]) 
     result.pop()  

permutation([1,2,3])

來源

2016-09-30 W.B

似乎是一個功課問題？否則，我不明白爲什麼你不會使用itertools。 – Lagerbaer

我最初的想法是創建一組生成器（每個生成器都有一個偏移量表示它們何時吐出下一個值），但我不確定這符合問題的精神。這裏有一些有趣的想法：http://stackoverflow.com/questions/2710713/algorithm-to-generate-all-possible-permutations-of-a-list –

這不是直觀拿出一個算法「就是這樣」產生的所有排列，而無需使用遞歸的。

但是存在幾種不同的這種算法。有看Heap's algorithm例如：直到隊列中的每個變化的長度等於輸入的長度

：

def permutation(li): 
    n = len(li) 
    c = [0] * n 

    print(li) 
    i = 1 
    while i < n: 
     if c[i] < i: 
      j = c[i] if i % 2 else 0 
      li[j], li[i] = li[i], li[j] 
      print(li) 
      c[i] += 1 
      i = 1 
     else: 
      c[i] = 0 
      i += 1

來源

2016-09-30 23:56:58 trincot

感謝分享這個。這是我正在嘗試，但不能完全達到那裏。 –

不客氣;-) – trincot

我一直很喜歡這種方法發生在每個變化

的所有位置的下一個輸入元素

input [1,2,3] 

queue [[1]] 
insert 2 in all positions of each variation 
queue [[2,1],[1,2]] 
insert 3 in all positions of each variation 
queue [[3,2,1],[2,3,1],[2,1,3],[3,1,2],[1,3,2],[1,2,3]]

來源

2016-10-01 04:41:04

使用堆棧列表的排列

回答

相關問題