请说明此算法以获取字符串的所有排列 [英] Please explain this algorithm to get all permutations of a String

问题描述

以下代码生成字符串的所有排列:

The following code generates all the permutations for a string:

def permutations(word):
    if len(word)<=1:
        return [word]

    #get all permutations of length N-1
    perms=permutations(word[1:])
    char=word[0]
    result=[]
    #iterate over all permutations of length N-1
    for perm in perms:
        #insert the character into every possible location
        for i in range(len(perm)+1):
            result.append(perm[:i] + char + perm[i:])
    return result

您能解释一下它的工作原理吗?我不理解递归.

Can you explain how it works? I don't understand the recursion.

推荐答案

算法为:

• 删除首字母
• 找到其余字母的所有排列(递归步骤)
• 重新插入在所有可能位置删除的字母.

递归的基本情况是一个字母.只有一种方法可以置换单个字母.

The base case for the recursion is a single letter. There is only one way to permute a single letter.

可行示例

想象开始的单词是bar.

• 首先删除b.
• 查找ar的排列.这给出了ar和ra.
• 对于每个单词，将b放在每个位置:
  • ar-> bar，abr，arb
  • ra-> bra，rba，rab
  • First remove the b.
  • Find the permuatations of ar. This gives ar and ra.
  • For each of those words, put the b in every location:
    • ar -> bar, abr, arb
    • ra -> bra, rba, rab

    这篇关于请说明此算法以获取字符串的所有排列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！