在Python中使用遞歸查找列表int的排列時考慮索引？

Question

我正在嘗試使用遞歸從特定範圍中找到所有整數列表的排列組合。例如，如果lst = [0,1,2]，則對def permute(lst, 0, 1)的調用應以該格式返回[[0,1], [1,0]]。同樣，致電permute(lst, 0, 2)應返回[[0,1,2], [0,2,1]...]。

到目前爲止，我的代碼只能找到一個完整列表排列，從指數0到LEN（LST）：

def permute(lst, low, high): 
    if low == high: 
     print(lst) 
    for index in range(low, high + 1): 
      lst[index], lst[low] = lst[low], lst[index] 
      permute(lst, low + 1, high) 
      lst[index], lst[low] = lst[low], lst[index] 

凡low = 0和high是len(lst)。

如果我改變這段代碼中的索引，我沒有得到正確的輸出。有關如何考慮指數的任何建議？

Answer 1

您可以用內遞歸函數，例如：

def permute(lst, start, end): 
    def permutations(l): 
     if len(l) <= 1: 
      return [l] 
     a = [] 
     for p in permutations(l[:-1]): 
      for i in range(len(l)): 
       a.append(p[i:] + [l[-1]] + p[:i]) 
     return a 
    return permutations(lst[start:end+1]) 

In [] 
lst = [0,1,2,3,4] 
permute(lst, 0, 1) 

Out[]: 
[[0, 1], [1, 0]] 

In [] 
permute(lst, 0, 2) 

Out[]: 
[[0, 1, 2], [1, 2, 0], [2, 0, 1], [1, 0, 2], [0, 2, 1], [2, 1, 0]] 

Answer 2

下面是一個使用一個額外的參數記住列表的起始位置代碼的一個版本做到這一點。我把你的函數改成了一個遞歸生成器，所以它產生了這些值，而不是將它們打印出來。我還將high更改爲stop，這符合Python的分片中使用的約定，例如seq[start:stop]和range(start, stop)。

def permute(lst, start, stop, low=None): 
    if low == stop - 1: 
     yield lst[start:stop] 
    if low is None: 
     low = start 
    for index in range(low, stop): 
      lst[index], lst[low] = lst[low], lst[index] 
      for t in permute(lst, start, stop, low + 1): 
       yield t 
      lst[index], lst[low] = lst[low], lst[index] 

# Test 
lst = list(range(5)) 
print(list(permute(lst, 1, 4))) 

for t in permute(lst, 0, 3): 
    print(t) 

輸出

[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 2, 1], [3, 1, 2]] 
[0, 1, 2] 
[0, 2, 1] 
[1, 0, 2] 
[1, 2, 0] 
[2, 1, 0] 
[2, 0, 1] 

---

該代碼工作相同關於Python 2 & 3中，儘管在Python 3它可以通過使用製成稍微更有效的（和更緊湊） yield from語法。替換for t in permute ...循環與

yield from permute(lst, start, stop, low + 1) 

在Python 3，您還可以在一個更緊湊的方式創建值列表：

[*permute(lst, 1, 4)] 

---

最後，這裏又建了遞歸發生器從你的算法，但它排列整個列表。當然，你可以使用接口函數調用它來排列子列表。

def permuter(lst): 
    if not lst: 
     yield lst 
    for index in range(len(lst)): 
     lst[index], lst[0] = lst[0], lst[index] 
     first = lst[:1] 
     for t in permuter(lst[1:]): 
      yield first + t 
     lst[index], lst[0] = lst[0], lst[index] 

def permute(lst, start, stop): 
    yield from permuter(lst[start:stop]) 

lst = list(range(5)) 
print(list(permute(lst, 1, 4)))