python - Python递归排列

Question

我在尝试使用递归制作排列代码时遇到了麻烦。这假设将一个列表返回给使用，其中包含每个字母的所有可能位置。所以对于这个词cat，它应该是 return ['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

When you're lost in recursive function, you should draw the call tree. The following version (inspired @Ben answer) keep the input order (if the input is in lexicographic order, the list of permutations will be, '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

The following version works for strings and lists, notice the reconstruction step is not the same:

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

As an exercice, you should draw call tree of the these functions, do you notice something ?

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']]

Answer 5

我知道这也是一个我，但我认为这对某些人来说可能更容易理解......

1. 基本情况是输入只有一个字符。
2. 设置一个循环遍历字符串中的每个字母。

3. 另一个 for 循环递归地排列所有其他可能性。

   def permute(s):
   
       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 6

这是我想出的最简单的解决方案。

   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 7

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 8

通过递归进行排列的最简单方法是首先为问题想象一个递归树

基本情况：如果给定一个空列表排列将是 [ [] ] 然后我们只想从列表中删除一个项目并将其添加到列表其余部分的所有索引中。

eg input : [a,b,c]
first = a
rest = [b,c]
all = [a,b,c] , [b,a,c] , [b,c,a]

Time: O(N!) #这是最好的，因为我们正在创建 N！element
Space O(N^2) #N 栈帧 * per_with_all 中的 N 项

来源： https ://www.youtube.com/watch?v=us0cYQXQpxg

def permetutation(arr):
    if len(arr) == 0:
        return [ [] ]
    #We remove 1st item from error as at each level we introduce 1 item 
    first_elenment = arr.pop(0)

    #getting permet for all other item 
    perm_without_first = permetutation(arr)

    per_with_all = []

    #Add permtution to every index 
    for comb in perm_without_first:
        for ind in range(len(comb)+1): #We also wan to add elenment to last so do +1 
            all = comb[0:ind] + [first_elenment] + comb[ind:] 
            per_with_all.append( all)

    return per_with_all

Answer 9

def permute(s):
    ch = list(s)
    if len(ch) == 2:
        per = ch[1] + ch[0] 
        return [''.join(ch)] + [per]
    if len(ch) < 2:
        return ch
    else:
        return [ init+per for init in ch for per in permute(''.join(ch).replace(init,""))] 

Answer 10

这些示例代码确实很有帮助，但是当我在CodeSignal上进行代码练习时，我发现一个测试用例失败了。基本上这里所有给定的方法都忽略了是否有任何重复。

Input: s: "ABA" 
Output: ["ABA", "AAB", "BAA", "BAA", "AAB", "ABA"] 
Expected Output: ["AAB", "ABA", "BAA"]

因此，如果您看到，它在输出中有以下重复项：

["BAA", "AAB", "ABA"]

我在这里一点一点地修改了这个

def stringPermutations(s):
        news = s
        if len(news) == 1:
            return [news]
        res = []
        for permutation in stringPermutations(news[1:]):
            for i in range(len(news)):
                res.append(permutation[:i] + news[0:1] + permutation[i:])
        # To Remove Duplicates From a Python List: list(dict.fromkeys(res))
        # To Sort List : sorted()
        return sorted(list(dict.fromkeys(res)))

def main():
    arr = 'ABA'
    print(stringPermutations(arr))

if __name__ == '__main__':
    main()

但是根据时间复杂度，这个答案是不合适的。这种方法的时间复杂度是：o(n^2)

我认为下面的方法是相当合理的。

def stringPermutations(string, prefix, permutation_list):
    #Edge case check
    if len(string) == 0:
        permutation_list.append(prefix)
    else:
        for i in range(len(string)):
            rem = string[0:i] + string[i + 1:]
            stringPermutations(rem, prefix + string[i], permutation_list)
    return sorted(list(dict.fromkeys(permutation_list)))
def main():
    permutation_list = []
    print(stringPermutations('aba','', permutation_list))

if __name__ == '__main__':
    main()