Python递归排列

Question

我在尝试使用递归制作排列代码时遇到了麻烦.这假设将列表返回到具有每个字母的所有可能位置的使用.所以对于这个词,cat它应该返回['cat','act',atc,'cta','tca','tac'].到目前为止,我有这个

def permutations(s):
    lst=[]
    if len(s) == 1 or len(s) == 0 :
        # Return a list containing the string, not the string
        return [s]
    # Call permutations to get the permutations that don't include the
    # first character of s
    plst = permutations(s[1:])
    print(plst)
    for item in plst:
        print (item)
        plst= permutations(s[1+1:])

         # Now move through each possible position of the first character
        # and create a new string that puts that character into the strings
        # in plst
        for i in range(len(s)):
            pass
            # Create a new string out of item
            # and put it into lst
        # Modify
    for item in lst:
        print(index)

有步骤,但我不知道如何使用它们

Answer 1

你想做递归,所以你首先要弄清楚递归是如何工作的.在这种情况下,它是以下内容:

permutation [a,b,c,...] = [a + permutation[b,c,...], b + permutation[a,c,..], ...]

并作为最终条件:

permutation [a] = [a]

因此,递归会在子列表中拆分列表,每次都会提取一个元素.然后将该元素添加到子列表的每个排列的前面.

所以在伪代码中:

def permutation(s):
   if len(s) == 1:
     return [s]

   perm_list = [] # resulting list
   for a in s:
     remaining_elements = [x for x in s if x != a]
     z = permutation(remaining_elements) # permutations of sublist

     for t in z:
       perm_list.append([a] + t)

   return perm_list

这有帮助吗？

Answer 2

递归地,考虑基本情况并从这种直觉构建.

1)当只有一个字符'c'时会发生什么？该元素只有一个排列,因此我们返回一个仅包含该元素的列表.

2)如果给出最后一个排列,我们如何产生下一个排列？在前一个排列'c'的所有可能位置添加一个附加字母'a'给我们'ca','ac'.

3)我们可以通过在每个早期排列中的所有可能位置添加附加字符来继续构建越来越大的排列.

如果字符串包含一个或多个字符,则以下代码返回一个字符的列表.否则,对于不包括字符串s [-1]中的最后一个字符的所有排列,我们为每个位置生成一个新字符串,我们可以在其中包含该字符并将新字符串附加到我们当前的排列列表中.

def permutations(s):
    if len(s) <= 1:
        return [s]
    else:
        perms = []
        for e in permutations(s[:-1]):
            for i in xrange(len(e)+1):
                perms.append(e[:i] + s[-1] + e[i:])
        return perms

Answer 3

当您对递归函数迷失时，应该绘制调用树。以下版本（灵感来自@Ben答案）保持输入顺序（如果输入按字典顺序排列，则排列列表将为'012' -> ['012', '021', '102', '120', '201', '210']。

def permut2(mystr):
    if len(mystr) <= 1:
        return [mystr]
    res = []
    for elt in mystr:
        permutations = permut2(mystr.replace(elt, ""))
        for permutation in permutations:
            res.append(elt + permutation)
    return res

以下版本适用于字符串和列表，请注意重建步骤不同：

def permut(array):
    if len(array) == 1:
        return [array]
    res = []
    for permutation in permut(array[1:]):
        for i in range(len(array)):
            res.append(permutation[:i] + array[0:1] + permutation[i:])
    return res

作为练习，您应该绘制这些函数的调用树，您注意到什么了吗？

Answer 4

您可以使用通过列表迭代索引的函数，并生成一个列表，该列表由索引处的值和其余列表值的排列组成。下面是一个使用 Python 3.5+ 特性的例子：

def permutations(s):
    if not s:
        yield []
    yield from ([s[i], *p] for i in range(len(s)) for p in permutations(s[:i] + s[i + 1:]))

所以list(permutations('abc'))返回：

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