在置换问题中是否可以不使用嵌套循环？

Question

我正在编写一个打印 [a,b,c,d] 的所有排列的代码。我不想使用递归函数，而是使用了 4 个 for 循环，但我的代码的缺点是循环有与列表中的元素数量相同。我的问题是是否可以编写与元素数量无关的代码。alphabet=["a","b","c","d"]for first in alphabet:    for second in alphabet:        if second != first:            for third in alphabet:                if third!=second and third!=first :                    for fourth in alphabet:                        if fourth!=first and fourth!=second and fourth != third:                                     print(first,second,third,fourth)

Answer 1

这是一个依赖于初始池中没有重复项的非递归尝试：

from collections import deque

def perms(pool):

    agenda = deque([([], pool)])

    while agenda:

        perm, left = agenda.popleft()

        if not left:

            yield perm

            # Or, to mimic the original 

            # print(*perm)

        else:

            for x in left:

                agenda.append((perm+[x], [y for y in left if y != x]))

>>> list(perms('abc')))

[['a', 'b', 'c'],

 ['a', 'c', 'b'],

 ['b', 'a', 'c'],

 ['b', 'c', 'a'],

 ['c', 'a', 'b'],

 ['c', 'b', 'a']]

Answer 2

这是一种基本方法（很容易想出）。

先从简单开始。首先，让alpha = ["a", "b", "c", "d"]. 首先找到所有以 开头的排列"a"：

    start_a = [["a"]]

    two_start_a = [ start_a[0] + [i]  for i in alpha ]

    to_three_start_a = [ [ j + [i] for i in alpha ] for j in two_start_a ]

    three_start_a = []

    for i in to_three_start_a:

        #cleaned is to exclude list with multiple values

        cleaned = [lst for lst in i if len(set(lst)) == len(lst)] 

        three_start_element += cleaned

    to_four_start_a = [ [ j + [i] for i in alpha ] for j in three_start_a ]

    four_start_a = []

    for i in to_four_start_a:

        #cleaned is to exclude list with multiple values

        cleaned = [lst for lst in i if len(set(lst)) == len(lst)] 

        four_start_element += cleaned

现在我们four_start_a包含所有以 开头的排列"a"。自动版本是

    start_a = [[alpha[0]]]

    two_start_a = [ start_a[0] + [i]  for i in alpha ]

    k_start_element = two_start_element

    for k in range(3, len(alpha)+1): 

        to_k_start_a = [ [ j + [i] for i in alpha ] for j in k_start_element ]

        k_start_a = []

        for i in to_k_start_a:

            #cleaned is to exclude list with multiple values

            cleaned = [lst for lst in i if len(set(lst)) == len(lst)] 

            k_start_element += cleaned

那么最后的k_start_a就是从 的第一个元素开始的所有排列alpha。

解决方案

所以，对于所有的字母，我们可以自动化如下

all_permutations = []

for element in alpha:

    start_element = [[element]]

    two_start_element = [ start_element[0] + [i]  for i in alpha ]

    k_start_element = two_start_element

    for k in range(3, len(alpha)+1): 

        to_k_start_element = [ [ j + [i] for i in alpha ] for j in k_start_element ]

        k_start_element = []

        for i in to_k_start_element:

            #to exclude list with multiple values

            cleaned = [lst for lst in i if len(set(lst)) == len(lst)] 

            k_start_element += cleaned

    all_permutations.extend( k_start_element )