首页
学习
活动
专区
工具
TVP
发布
社区首页 >问答首页 >这种递归函数是如何产生所有排列的呢?

这种递归函数是如何产生所有排列的呢?
EN

Stack Overflow用户
提问于 2019-04-17 06:38:47
回答 1查看 48关注 0票数 0

我真的很难理解递归代码。我复制了一段我想要理解的代码。我已经看到了以图形化的方式描述这一点,但我不明白程序是如何得到结果的。

到目前为止,这是我的理解

最初为

如果条件不满足,则将

  • (ABC,0,3)传递到函数
  • ,因此进入ELSE分支
  • j为0,这次i为0(将第一个字符与first character)
  • **THEN*交换第一个字符将新的'data‘发送回函数并重新运行Question
  • Why是否"j“保持i递增?循环无论如何都没有运行到结束...)。由于某些原因,j和i都会增加,直到i=3,然后输出“ABC”
  • 到目前为止,我们还没有超过行permute(

,i+1,

  • ),我不明白为什么程序会跳到permute(
  • ...)行在打印"ABC“行之后,我们处于”if-
  • “子句的"IF”而不是"ELSE“分支中。
  • 我不明白如何使用"i”和“j”在所有字符之间进行迭代。

这有意义吗?请有人解释一下这段代码是如何产生所有解决方案的。谢谢

代码语言:javascript
复制
def permute(data, i, length): 
    if i==length: 
        print(''.join(data) )
    else: 
        for j in range(i,length): 
            #swap
            data[i], data[j] = data[j], data[i] 
            permute(data, i+1, length) 
            data[i], data[j] = data[j], data[i]  


string = "ABC"
n = len(string) 
data = list(string) 
permute(data, 0, n)
EN

回答 1

Stack Overflow用户

回答已采纳

发布于 2019-04-17 06:49:13

让我们逐行分解代码。我们将从字符串的开头步进到结尾,在每次调用时递增i。在每次调用中,我们对字符串的其余部分迭代j

代码语言:javascript
复制
def permute(data, i, length): 
    # If "i" is at the end, we're done with one permutation: print the result.
    if i==length: 
        print(''.join(data) )

    else:
        # for each remaining character (later in the string)
        for j in range(i,length):

            # Swap that character with the "ith" character
            data[i], data[j] = data[j], data[i]

            # Keeping data[0:i] fixed,
            # generate all permutations of the remainder of the string
            permute(data, i+1, length)

            # Swap the characters back
            data[i], data[j] = data[j], data[i]

现在,添加一些基本的工具来跟踪执行:跟踪例程条目和递归;每次重复时缩进。

代码语言:javascript
复制
indent = ""

def permute(data, i, length): 
    global indent
    print(indent, "ENTER", ''.join(data), i)
    indent += "  "

    if i==length: 
        print("PERMUATATION:", ''.join(data) )
    else: 
        for j in range(i,length): 
            print(indent, "SWAP", i, j)
            #swap
            data[i], data[j] = data[j], data[i] 
            permute(data, i+1, length) 
            data[i], data[j] = data[j], data[i]  

    indent = indent[2:]


string = "ABC"
n = len(string) 
data = list(string) 
permute(data, 0, n)

输出:

代码语言:javascript
复制
 ENTER ABC 0
   SWAP 0 0
   ENTER ABC 1
     SWAP 1 1
     ENTER ABC 2
       SWAP 2 2
       ENTER ABC 3
PERMUATATION: ABC
     SWAP 1 2
     ENTER ACB 2
       SWAP 2 2
       ENTER ACB 3
PERMUATATION: ACB
   SWAP 0 1
   ENTER BAC 1
     SWAP 1 1
     ENTER BAC 2
       SWAP 2 2
       ENTER BAC 3
PERMUATATION: BAC
     SWAP 1 2
     ENTER BCA 2
       SWAP 2 2
       ENTER BCA 3
PERMUATATION: BCA
   SWAP 0 2
   ENTER CBA 1
     SWAP 1 1
     ENTER CBA 2
       SWAP 2 2
       ENTER CBA 3
PERMUATATION: CBA
     SWAP 1 2
     ENTER CAB 2
       SWAP 2 2
       ENTER CAB 3
PERMUATATION: CAB

现在使用此信息跟踪代码。

票数 -1
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/55717523

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档