For循环使用递归调用的输出作为参数

2024-03-29 08:19:02 发布

您现在位置:Python中文网/ 问答频道 /正文

目前正在学习marklutz-Learning Python 5e,还有一个置换函数,我还不能理解,希望能得到一些指导。你知道吗

def permute1(seq):
    if not seq:
        return [seq]
    else:
        res = []
        for i in range(len(seq)):
            rest = seq[:i] + seq[i+1:]
            for x in permute1(rest):
                res.append(seq[i:i+1] + x)
        return res

seq = (1,2,3)
permute1(seq)
  1. 哪些值用于x。是上次permute1()的电话吗?你知道吗
  2. 为什么res语句顶部的else:在整个过程中保持为空?是可变还是不变的问题?for循环实际将其输出附加到哪个变量?你知道吗
  3. for循环中重建序列之前清空序列的过程是一种常见的设计模式吗?你知道吗

这里可能是permute1()的一个更有用的版本,所有变量都被打印出来。你知道吗

def permute1(seq):
    if not seq:
        return [seq]
    else:
        res = []
        print('at the top seq = {} res = {},'.format(seq, res))
        for i in range(len(seq)):
            rest = seq[:i] + seq[i+1:]
            print('recursive call seq = {}, rest = {}, i = {}'.format(seq, rest, i))
            for x in permute1(rest):
                print('inside x = {}, rest = {}, seq = {}'.format(x, rest, seq))
                res.append(seq[i:i+1] + x)
        print('seq = {}; res = {}'.format(seq,res))
        return res

seq = (1,2,3)
permute1(seq)

Tags: inrestformatforlenreturnifdef
1条回答
网友
1楼 · 发布于 2024-03-29 08:19:02

递归函数调用只是另一个函数调用,其实这种调用没有什么特别之处。调用一个函数,当它返回时,使用该调用的结果。你知道吗

使用递归时,会出现调用堆栈,一个调用另一个调用,直到函数返回结果,因此第一个外部调用可能需要等待一段时间才能继续执行给定的结果。你知道吗

在您的示例中,permute1()总是返回一个列表(return [seq]在顶部,或者return res在更远的地方),因此for x in ...在该结果上循环(一旦递归调用返回),并使用结果中的每个元组为其预先添加一个元素元组(res[i:i + 1]将一个元组分割为只包含一个元素,即索引i处的元素)。你知道吗

使用空元组调用函数时,函数将立即返回:

>>> permute1(())
[()]

这是一个没有递归调用的阶段,这很重要!递归就是这样结束的!你知道吗

另一个块使用rest = seq[:i] + seq[i+1:]seq创建一个新的元素列表。这是一个元组,去掉了一个元素,在索引i

>>> seq
(1, 2, 3)
>>> seq[:1] + seq[2:]  # if i is 1, then..
(1, 3)

如果使用单元素元组调用permute1(),则for i in range(len(seq))循环一次,使用i = 0。这意味着res被设置为一个空元组(长度为1且删除了1个元素的元组是一个空元组),因此进行了一个permute1(())调用。我们在上面看到,它只返回[()],最后将seq[i:i+1] + x添加到res,函数返回。你知道吗

因此,一个包含单个元素的调用将进行一个递归调用,并返回一个包含单个元组的列表,基本上与开始时相同:

>>> permute1((1,))
[(1,)]

对于2个元素,循环迭代两次,用一个元素元组调用permute1()两次,完成上述操作。这两个调用的结果都是一个包含1个元素的列表,因此您将得到带有两个新元组的res,即输入元素的两个顺序:

>>> permute1((1,))
[(1, 2), (2, 1)]

你可以从这里推断出3个元素是如何工作的。你知道吗

它可以通过传递级别信息来帮助缩进打印信息:

def permute1(seq, level=0):
    indent = '    ' * level
    p = lambda msg, *args: print(indent + msg.format(*args))
    p('permute1({}, {}) called', seq, level)
    if not seq:
        p('- end stage, seq is empty, returning [(),]')
        return [seq]
    else:
        p('- Looping {} times over {}', len(seq), seq)
        res = []
        for i in range(len(seq)):
            rest = seq[:i] + seq[i+1:]
            p('| Loop #{}, rest is: {}, seq[i] is {}, making recursive call', i + 1, rest, seq[i])
            for x in permute1(rest, level + 1):
                p(' + processing 1 result from recursive call, {}', x)
                res.append(seq[i:i+1] + x)
                p(' + res appended to, now {}', res)
            p('\ Loop #{} complete, res is: {}', i + 1, res)
        p('Function done, returning {}', res)
        return res

plambda以level乘以前面4个空格打印消息;递归越深,调用缩进越多。你知道吗

这有点冗长,但现在你可以看到事情发生在什么层次:

>>> permute1(seq)
permute1((1, 2, 3), 0) called
- Looping 3 times over (1, 2, 3)
| Loop #1, rest is: (2, 3), seq[i] is 1, making recursive call
    permute1((2, 3), 1) called
    - Looping 2 times over (2, 3)
    | Loop #1, rest is: (3,), seq[i] is 2, making recursive call
        permute1((3,), 2) called
        - Looping 1 times over (3,)
        | Loop #1, rest is: (), seq[i] is 3, making recursive call
            permute1((), 3) called
            - end stage, seq is empty, returning [(),]
         + processing 1 result from recursive call, ()
         + res appended to, now [(3,)]
        \ Loop #1 complete, res is: [(3,)]
        Function done, returning [(3,)]
     + processing 1 result from recursive call, (3,)
     + res appended to, now [(2, 3)]
    \ Loop #1 complete, res is: [(2, 3)]
    | Loop #2, rest is: (2,), seq[i] is 3, making recursive call
        permute1((2,), 2) called
        - Looping 1 times over (2,)
        | Loop #1, rest is: (), seq[i] is 2, making recursive call
            permute1((), 3) called
            - end stage, seq is empty, returning [(),]
         + processing 1 result from recursive call, ()
         + res appended to, now [(2,)]
        \ Loop #1 complete, res is: [(2,)]
        Function done, returning [(2,)]
     + processing 1 result from recursive call, (2,)
     + res appended to, now [(2, 3), (3, 2)]
    \ Loop #2 complete, res is: [(2, 3), (3, 2)]
    Function done, returning [(2, 3), (3, 2)]
 + processing 1 result from recursive call, (2, 3)
 + res appended to, now [(1, 2, 3)]
 + processing 1 result from recursive call, (3, 2)
 + res appended to, now [(1, 2, 3), (1, 3, 2)]
\ Loop #1 complete, res is: [(1, 2, 3), (1, 3, 2)]
| Loop #2, rest is: (1, 3), seq[i] is 2, making recursive call
    permute1((1, 3), 1) called
    - Looping 2 times over (1, 3)
    | Loop #1, rest is: (3,), seq[i] is 1, making recursive call
        permute1((3,), 2) called
        - Looping 1 times over (3,)
        | Loop #1, rest is: (), seq[i] is 3, making recursive call
            permute1((), 3) called
            - end stage, seq is empty, returning [(),]
         + processing 1 result from recursive call, ()
         + res appended to, now [(3,)]
        \ Loop #1 complete, res is: [(3,)]
        Function done, returning [(3,)]
     + processing 1 result from recursive call, (3,)
     + res appended to, now [(1, 3)]
    \ Loop #1 complete, res is: [(1, 3)]
    | Loop #2, rest is: (1,), seq[i] is 3, making recursive call
        permute1((1,), 2) called
        - Looping 1 times over (1,)
        | Loop #1, rest is: (), seq[i] is 1, making recursive call
            permute1((), 3) called
            - end stage, seq is empty, returning [(),]
         + processing 1 result from recursive call, ()
         + res appended to, now [(1,)]
        \ Loop #1 complete, res is: [(1,)]
        Function done, returning [(1,)]
     + processing 1 result from recursive call, (1,)
     + res appended to, now [(1, 3), (3, 1)]
    \ Loop #2 complete, res is: [(1, 3), (3, 1)]
    Function done, returning [(1, 3), (3, 1)]
 + processing 1 result from recursive call, (1, 3)
 + res appended to, now [(1, 2, 3), (1, 3, 2), (2, 1, 3)]
 + processing 1 result from recursive call, (3, 1)
 + res appended to, now [(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1)]
\ Loop #2 complete, res is: [(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1)]
| Loop #3, rest is: (1, 2), seq[i] is 3, making recursive call
    permute1((1, 2), 1) called
    - Looping 2 times over (1, 2)
    | Loop #1, rest is: (2,), seq[i] is 1, making recursive call
        permute1((2,), 2) called
        - Looping 1 times over (2,)
        | Loop #1, rest is: (), seq[i] is 2, making recursive call
            permute1((), 3) called
            - end stage, seq is empty, returning [(),]
         + processing 1 result from recursive call, ()
         + res appended to, now [(2,)]
        \ Loop #1 complete, res is: [(2,)]
        Function done, returning [(2,)]
     + processing 1 result from recursive call, (2,)
     + res appended to, now [(1, 2)]
    \ Loop #1 complete, res is: [(1, 2)]
    | Loop #2, rest is: (1,), seq[i] is 2, making recursive call
        permute1((1,), 2) called
        - Looping 1 times over (1,)
        | Loop #1, rest is: (), seq[i] is 1, making recursive call
            permute1((), 3) called
            - end stage, seq is empty, returning [(),]
         + processing 1 result from recursive call, ()
         + res appended to, now [(1,)]
        \ Loop #1 complete, res is: [(1,)]
        Function done, returning [(1,)]
     + processing 1 result from recursive call, (1,)
     + res appended to, now [(1, 2), (2, 1)]
    \ Loop #2 complete, res is: [(1, 2), (2, 1)]
    Function done, returning [(1, 2), (2, 1)]
 + processing 1 result from recursive call, (1, 2)
 + res appended to, now [(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2)]
 + processing 1 result from recursive call, (2, 1)
 + res appended to, now [(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)]
\ Loop #3 complete, res is: [(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)]
Function done, returning [(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)]
[(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)]

相关问题 更多 >