低调排列 [英] Understading permutations

问题描述

我正在阅读这篇文章，以尝试了解有关排列的更多信息:

I was going through this post trying to learn more about permutations: Finding all possible permutations of a given string in 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]如何帮助呢?我只是不知道发生了什么事

I'm not understanding the line where we swap the current index with the step, what exactly is this doing? I know that we move to the right once sith step but how does string_copy[step], string_copy[i] = string_copy[i], string_copy[step] aid that? I've just no idea what's happening

推荐答案

a,b = b,a是用于交换两个值的Python习惯用法，也可以编写为:

a,b = b,a is a Python idiom for swapping two values, it can also be written:

temp = a
a = b
b = temp

在for循环内，在permutations(...)上方，添加以下行:

Inside the for loop, above permutations(...), add this line:

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

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

Now it will show you the inner workings as it runs:

>>> 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. 查看步骤和索引相同时，字符将与自身交换而没有任何变化.因此，有十五个调用来生成六个排列.

我发现很难举一个例子来增加清晰度.怎么样:

I'm finding it hard to make an example that adds any more clarity. How about this:

 # (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()完成时，我们向左返回<-.
  • 向右移动可增加步幅.
  • 以相同的缩进量向下移动会增加索引.
  • 左右移动，可同时增加步长和索引.
  • This shows not just a loop, but a heirarchy, a tree. Things to the right are deeper, they are under things to the left. Beneath them. Inside them. The first part of the pattern is all the things under -- a, the second part is all things under -- b, the third part is all things under -- c.
  • Each call to permute() pushes everything -> to the right.
  • Each time permute() finishes, we return back <- to the left.
    • Moving right increases the step.
    • Moving down at the same indent increases the index.
    • Moving down and right, increases step and index together.

    ，然后尝试回答您的评论问题:

    and, to try and answer your comment questions:

    • for i in range(step, len(string)):行从当前的缩进/步进级别启动索引计数器.这就是为什么它在更深层次上从(1,1)变为(2,2) 的原因.您可以看到，当我们从(2,2)返回时，我们选择了先前的状态(1,1)，并在相同的级别进入(1,2)，然后进入(2， 2)在更深层次的那里.

    • The line for i in range(step, len(string)): starts the index counter from the current indent / step level. That's why it goes from (1,1) to (2,2) at a deeper level. You can see that when we come back from (2,2) we pick up the previous state (1,1) and at the same level go to (1,2), then into (2,2) at a deeper level under there.

    我们从(2,2)回到(0,0)的原因是，我们通过向右缩进尽可能多的次数来到达字符串的末尾，直到'以'a'开头的排列用完了. 'abc'和'acb'然后我们从'b'开始回到起点. 'bac'和'bca'.然后我们用完了，回到起点.

    The reason we go from (2,2) back to (0,0) is because we've got to the end of the string by indenting to the right, as many times as we can, until we've run out of permutations starting with 'a'. 'abc' and 'acb' Then we go back to the start, starting with 'b'. 'bac' and 'bca'. Then we've run out, go back to the start.

    例如

     (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.
    

    在每个级别，都发生着相同的模式.更改此列/级别，然后重复所有较低的级别.这是一种自相似，递归，循环的模式.

    At every level, the same pattern is happening. Change this column/level, and repeat all the lower levels. It's a self-similar, recursive, loopy pattern.

    在我的示例代码中，我有8个版本的print语句，它们打印出不同的组合以尝试显示正在发生的事情.我认为以上是最清楚的，但是我建议您放入打印语句并重新运行它.在交换之前和之后打印'string'和'string_copy'，打印'string_copy [step:]'并打印" "*(3*(step+1))以打印缩进.

    I have 8 versions of print statements in my example code, printing different combinations of things to try and show what's going on. I decided the above is the most clear, but I encourage you to put print statements in and re-run it. Print 'string' and 'string_copy' before and after the swap, print 'string_copy[step:]' and print " "*(3*(step+1)) to print indents.

    我不知道有什么简单的解释.只能盯着代码，一遍又一遍地遍历代码，直到变得更有意义为止.

    There's no easy explanation that I know of. There's no substitute for staring at the code, working through it bit by bit over and over until it makes more sense.

    这篇关于低调排列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！