Python的递归排列Python的递归排列(Python recursion permutatio

有麻烦林试图与递归置换码。 这是假设返回一个列表回用与每个字母所有更多钞票位置。 因此对于单词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）我们怎样才能产生下一个排列给出的最后一个？ 增加一个额外的字母“A”在之前的置换“c”的所有可能的位置给了我们“CA”，“交流”。

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

作为exercice，你应该吸取的这些函数调用树，你会注意些什么呢？

Answer 4:

def permutations(string_input, array, fixed_value=""):
    for ch in string_input:
        permutations(string_input.replace(ch, ""), array, fixed_value + ch)
    if not string_input:
        array.append(fixed_value)

你可以把它叫做

array = []
permutations("cat", array)
print array

Answer 5:

这是我想出了一个简单的解决方案。

   def permutations(_string):
        # stores all generated permutations
        permutations = []

        # this function will do recursion
        def step(done, remain):
            # done is the part we consider "permutated"
            # remain is the set of characters we will use

            # if there is nothing left we can appened generated string
            if remain == '':
                permutations.append(done)
            else:

                # we iterate over the remaining part and indexing each character
                for i, char in enumerate(remain):
                    # we dont want to repeat occurance of any character so pick the remaining
                    # part minus the currect character we use in the loop
                    rest = remain[:i] + remain[i + 1:]
                    # use recursion, add the currect character to done part and mark rest as remaining
                    step(done + char, rest)
        step("", _string)
        return permutations

你可以测试一下：

@pytest.mark.parametrize('_string,perms', (
    ("a", ["a"]),
    ("ab", ["ab", "ba"]),
    ("abc", ["abc", "acb", "cba", "cab", "bac", "bca"]),
    ("cbd", ["cbd", "cdb", "bcd", "bdc", "dcb", "dbc"])
))
def test_string_permutations(_string, perms):
    assert set(permutations(_string)) == set(perms)

Answer 6:

我知道这是我太多，但我觉得这个可能是更容易一些人理解....

1. 基础案例是当输入仅是一个字符。
2. 设置了一个for循环，通过每个字符串中的字母的迭代。
3. 另一个用于遍历所有其他的可能性递归的置换。

DEF置换（一个或多个）：

out = []

if len(s) == 1:
    out = [s]
else:
    for i,let in enumerate(s):
        for perm in permute(s[:i]+s[i+1:]):
            out += [let+perm]
return out

Answer 7:

您可以使用遍历列表索引的功能，并产生由索引后跟列表值的其余部分的排列在值的列表。 下面是使用在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']]

文章来源: Python recursion permutations