不断变换的排列

Question

我正在阅读这篇文章,试图了解有关排列的更多信息:在python中查找给定字符串的所有可能排列

我被困在这段代码上:

def permutations(string, step = 0):

    # if we've gotten to the end, print the permutation
    if step == len(string):
        print "".join(string)

    # everything to the right of step has not been swapped yet
    for i in range(step, len(string)):

        # copy the string (store as array)
        string_copy = [character for character in string]

        # swap the current index with the step
        string_copy[step], string_copy[i] = string_copy[i], string_copy[step]

        # recurse on the portion of the string that has not been swapped yet (now it's index will begin with step + 1)
        permutations(string_copy, step + 1)

我不理解我们将当前索引与步骤交换的行,这究竟是做什么的？我知道我们一旦向西移动,step但是如何string_copy[step], string_copy[i] = string_copy[i], string_copy[step]援助呢？我不知道发生了什么

Answer 1

a,b = b,a 是一个用于交换两个值的Python习语,它也可以写成:

temp = a
a = b
b = temp

在for循环中,在排列(...)之上,添加以下行:

print "step", step, "index", i, string, "->", string_copy

现在它将显示运行时的内部工作原理:

>>> permutations("abc")

step 0 index 0 abc -> ['a', 'b', 'c']
step 1 index 1 ['a', 'b', 'c'] -> ['a', 'b', 'c']
step 2 index 2 ['a', 'b', 'c'] -> ['a', 'b', 'c']
abc
step 1 index 2 ['a', 'b', 'c'] -> ['a', 'c', 'b']
step 2 index 2 ['a', 'c', 'b'] -> ['a', 'c', 'b']
acb
step 0 index 1 abc -> ['b', 'a', 'c']
step 1 index 1 ['b', 'a', 'c'] -> ['b', 'a', 'c']
step 2 index 2 ['b', 'a', 'c'] -> ['b', 'a', 'c']
bac
step 1 index 2 ['b', 'a', 'c'] -> ['b', 'c', 'a']
step 2 index 2 ['b', 'c', 'a'] -> ['b', 'c', 'a']
bca
step 0 index 2 abc -> ['c', 'b', 'a']
step 1 index 1 ['c', 'b', 'a'] -> ['c', 'b', 'a']
step 2 index 2 ['c', 'b', 'a'] -> ['c', 'b', 'a']
cba
step 1 index 2 ['c', 'b', 'a'] -> ['c', 'a', 'b']
step 2 index 2 ['c', 'a', 'b'] -> ['c', 'a', 'b']
cab

1. 每当步骤和索引相同时,就会看到一个字符与自身交换而没有任何变化.所以有十五个调用来生成六个排列.

我发现很难做出一个更加清晰的例子.这个怎么样:

 # (step, index)

 (0, 0) -- a
    (1, 1) -- ab
       (2, 2) -- abc        # reached the last character, print this!
      <-
    (1, 2) -- ac
       (2, 2) -- acb        # reached the last character, print this!
      <-
   <-
 (0, 1) -- b
    (1, 1) -- ba
       (2, 2) -- bac        # reached the last character, print this!
      <-
    (1, 2) -- bc
       (2, 2) -- bca        # reached the last character, print this!
      <-
   <-
 (0, 2) -- c
    (1, 1) -- cb
       (2, 2) -- cba        # reached the last character, print this!
      <-
    (1, 2) -- ca
       (2, 2) -- cab        # reached the last character, print this!
      <-
   <-

• 这不仅显示了一个循环,还显示了一个层,一个树.正确的事情更深入,它们在左边的事物之下.在他们下面.在他们里面.图案的第一部分是所有的东西下 -- a,第二部分是下的所有东西-- b,第三部分是下的所有东西-- c.
• 每次调用permute()都会将所有内容 - >推向右侧.
• 每次permute()完成后,我们返回< - 向左.
  • 向右移动会增加步骤.
  • 向下移动相同的缩进会增加索引.
  • 向下和向右移动,一起增加步骤和索引.
• 每次我们缩进 - >我们从父事件中获取状态.一切都在--a开始-- a.一切都在-- ab开始-- ab.
• 缩进有3个左右的位置,因为字符串中有3个字符,一个4字符串得到缩进的另一个层面,因此很多更行 - 为更大量的置换.
• 'step'数字与缩进的正确程度相匹配并非巧合.

并且,尝试回答您的评论问题:

• 该行for i in range(step, len(string)):从当前缩进/步骤级别开始索引计数器.这就是为什么它从(1,1)到更深层次的(2,2).你可以看到,当我们从(2,2)前,我们拿起以前的状态(1,1),并在同一水平去(1,2),然后进入(2,2)在更深的层面下那里.

• 我们从(2,2)返回到(0,0)的原因是因为我们通过缩进到右边到了字符串的结尾,因为很多时候,我们可以,直到我们已经用完了排列以'a'开头.'abc'和'acb'然后我们回到开头,从'b'开始.'bac'和'bca'.然后我们就跑了,回到开始.

例如

 (0, 0) -- a
    (1, 1) -- ab
       (2, 2) -- abc    #STEP has reached the end of the string, move left

    # We moved left, index was 1 so we've got more work to do
    (1, 2) -- ac
       (2, 2) -- acb    #STEP has reached the end of the string, move left

    # We moved left, index was 2 so that has also reached the end of the string
    # no more work to do inside the group (0,0) -- a, so move left again.
  <- 
  # Now at this far left level, we can change the far left column from (0,0) to (0,1)
  # and then repeat all of the above.

在每个级别,都会出现相同的模式.更改此列/级别,并重复所有较低级别.它是一种自相似,递归,循环的模式.

我的print示例代码中有8个语句版本,打印不同的组合以尝试显示正在发生的事情.我认为上面的内容是最明确的,但我鼓励你将print语句放入并重新运行.在交换之前和之后打印'string'和'string_copy',打印'string_copy [step:]'并打印" "*(3*(step+1))以打印缩进.

我所知道的并不容易解释.没有什么可以替代盯着代码,一遍又一遍地一遍又一遍地工作直到它变得更有意义.