Python：使用嵌套循环的程序不能正常工作

Question

此程序需要通过使用此规则交换元素来找到列表的所有排列 - 交换最后一个元素，直到它变为第一个为止（例如，1,2,3,4变为1,2， 4，3等等，直到4,1,2,3），当它成为第一个元素时，则需要切换最后2个元素并在相反方向上执行相同的操作（交换第一个元素，直到它变为最后一个，然后交换第一个元素2元素和重复），这也被称为Steinhaus-Johnson-Trotter算法。出于某种原因，我的实现不能在Python中工作，我想知道为什么以及为了使其工作需要做什么。

编辑：通过“不工作”我的意思是，该程序只打印list1和别的什么都不做，程序只能通过“杀”它关闭，这意味着它被卡在无限循环（这可以证明在将list1附加到all_permutations后打印all_permutations）。

list1 = [0, 1, 2, 3] #list that will be swapped 
x = 3 #this is used for swapping 

all_permutations = [] #list where permutations will be added 

print(list1) #print list1 because it is the first permutation 

while len(all_permutations) != 23: #loop until all permutations are found (4! = 24 but since list1 is already 1 permutation we only need 23) 
    x -= 1 
    list1[x], list1[x+1] = list1[x+1], list1[x] 
    all_permutations.append(list1) 

           #code above swaps the last element until it becomes 1st in the list 
    if x == 0: #if last element becomes 1st 
     list1[2], list1[3] = list1[3], list1[2] #swap last 2 elements 
     while x != 3: #loop which swaps 1st element until it becomes the last element 
      if len(all_permutations) == 23: 
       break 
      else: 
       continue 
      x += 1 
      list1[x-1], list1[x] = list1[x], list1[x-1] 
      all_permutations.append(list1) 


     list1[0], list1[1] = list1[1], list1[0] #when loop is over (when 1st element becomes last) switch first 2 elements 
     all_permutations.append(list1) 


    else: 
     continue 



print(all_permutations) #print all permutations 

Answer 1

while x != 3: 
    if len(all_permutations) == 23: 
     break 
    else: 
     continue 

这段代码就在这里将导致一个无限循环。如果all_permutations的长度不是23，那么将会发出continue声明。这会将程序返回到循环的开始，而不会修改x或all_permutations。

我相信你在这里找的是pass它什么都不做。 continue将回到循环的开始。因此，要修复程序的这部分内容，您实际上可以完全摆脱else，因为break无论如何都将退出循环。

while x != 3: 
    if len(all_permutations) == 23: 
     break 
    x += 1 
    list1[x-1], list1[x] = list1[x], list1[x-1] 
    all_permutations.append(list1) 

或者你也可以消除if干脆：

while x != 3 or len(all_permutations) != 23: 
    x += 1 
    list1[x-1], list1[x] = list1[x], list1[x-1] 
    all_permutations.append(list1) 

Answer 2

你加入到同一个列表对象多次引用all_permutations，并通过循环每次该清单对象被修改。相反，请添加列表的副本，以便您拥有不同排列的集合。

all_permutations.append(list1[:]) 

这是一个错误;无限循环是由IanAuld指出的问题引起的。

Answer 3

您在http://pastebin.com/bY7ZznR1新的代码卡住在一个无限循环的原因是，当len(all_permutations) == 23在内部while循环将成为真正的你再附加上线30的另一个列表，并在控制获取到外环len(all_permutations) == 24顶部，所以循环继续执行。

这很容易解决，但是你的算法不太正确。我修改了代码以生成任意大小的列表的排列，并且注意到它为长度为3或4的列表提供了正确的结果，但是不能为长度为2或5的列表提供正确的结果;我没有打扰测试其他尺寸。

FWIW，这是一个实现Steinhaus - Johnson - Trotter算法递归版本的程序。如果您想改进迭代算法，您可能会发现它很有用。

#!/usr/bin/env python 

''' Generate permutations using the Steinhaus - Johnson - Trotter algorithm 

    This generates permutations in the order known to bell ringers as 
    "plain changes". 
    See https://en.wikipedia.org/wiki/Steinhaus%E2%80%93Johnson%E2%80%93Trotter_algorithm 

    From http://stackoverflow.com/q/31209826/4014959 

    Written by PM 2Ring 2015.07.03 
''' 

import sys 

def sjt_permute(items): 
    num = len(items) 
    if num == 1: 
     yield items[:1] 
     return 

    last = items[-1:] 
    uprange = range(num) 
    dnrange = uprange[::-1] 
    descend = True 
    for perm in sjt_permute(items[:-1]): 
     rng = dnrange if descend else uprange 
     for i in rng: 
      yield perm[:i] + last + perm[i:] 
     descend = not descend 

def main(): 
    num = int(sys.argv[1]) if len(sys.argv) > 1 else 4 
    items = range(num) 
    for p in sjt_permute(items): 
     print(p) 

if __name__ == '__main__': 
    main() 

输出

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