Справка по программе перестановки Python

Question

Я нашел этот код в activestate, он принимает строку и печатает перестановки строки. Я понимаю, что это рекурсивная функция, но я не совсем понимаю, как она работает, было бы замечательно, если бы кто-то мог провести меня через поток программы, спасибо большое!

import sys

def printList(alist, blist=[]):
    if not len(alist): print ''.join(blist)
    for i in range(len(alist)):
        blist.append(alist.pop(i))
        printList(alist, blist)
        alist.insert(i, blist.pop())

if __name__ == '__main__':
    k = 'love'
    if len(sys.argv) > 1: k = sys.argv[1]
    printList(list(k))

Answer 1

Вы можете выяснить, как ведет себя printList, нарисовав дерево рекурсии. Каждый узел состоит из двух элементов: alist и blist. Корень имеет alist с начальной последовательностью элементов, которые вы хотите переставить, и пустой blist. Каждый узел дерева имеет одну ветвь для каждого элемента этого узла alist; вы переходите от узла «отца» к каждому из его «детей», выбирая элемент из папок alist и:

• присвоение ребенку alist отца alist минус этот элемент ;
• присвоение ребенку blist отца blist плюс этот элемент , добавленный в его конец .

Листья имеют пустой alist, и, поскольку, следуя различным путям от корня до листьев, вы должны выбирать элементы из alist корня в разных порядках, blist самих листьев содержат все перестановки корня alist.

Например ([abc],[] == alist,blist):

                           [abc],[] 
                         /     |     \
                       a/     b|      \c
                       /       |       \
                  [bc],[a]  [ac],[b]   [ab],[c]
                  /     \
                b/       \c
                /         \
           [c],[ab]      [b],[ac]
              |             |
             c|             |b
              |             |
           [],[abc]      [],[acb]


def printList(alist, blist=[]):
    # if alist is empty, we are in a 'leaf' in the recursion tree;
    # then blist contains one permutation; print it
    if not len(alist): print ''.join(blist)

    # ELSE, for each possible position in alist,
    for i in range(len(alist)):

        # move the element at that position from alist to the end of blist
        blist.append(alist.pop(i))

        # go to the 'children' node and do the printing job for its subtree
        printList(alist, blist)

        # then move back the element from the end of blist to its original
        # position in alist, so we can continue with the for loop
        # without altering alist
        alist.insert(i, blist.pop())

Answer 2

Чтобы понять это, ясно удалите цикл с alist = love и blist, инициализированными в []: Теперь 4 вызова списка печати в цикле for будут (на первом уровне рекурсии):

   printList("ove","l");
   printList("lve","o");
   printList("loe","v");
   printList("lov","e");

Каждый из этих вызовов printList имеет bList, инициализированный для всех возможных перестановок списков из одной буквы, а alist имеет остальные 3 буквы. Это будет продолжаться до тех пор, пока alist не станет пустым, а все буквы не будут в блисте (и печать произойдет if not len(alist): print ''.join(blist))

На втором уровне рекурсии, например

   printList("ove","l") will result in 3 calls

   printList("ve","lo");
   printList("oe","lv");
   printList("ov","le");

Всего перестановок = 4 (первый уровень) * 3 (2-й уровень) * 2 * 1

Answer 3

Бесстыдный плагин - вот элементарный код перестановки в python вместе с пояснениями из моего блога. Игра с рекурсией - перестановка строк