개요

특정 문자열을 입력하면 그 문자열로 만들 수 있는 순열의 모든 경우의 수를 출력하는 함수를 구해보자.
이 코드의 특징은 재귀알고리즘을 사용하는데 점화식이 작동하는 부분이 for문 안에 있다는 점이다. 알고리즘을 해석하면서 매우 복잡하다는 느낌이 들 수 있지만 경우의 수를 하나씩 보면서 생각하면 이해할 수 있을 것이다.

코드

def permute(seq):
    if not seq: # Shuffle any sequence
        print("not seq인 경우")
        return [seq] # Empty sequence
    else:
        res = []
        for i in range(len(seq)):
            rest = seq[:i] + seq[i+1:] # Delete current node
            print("1차 for문 진행중 seq=%s, i=%s, rest=%s" % (seq, i, rest))
            for x in permute(rest): # Permute the others
                print("2차 for문 진행전 res=%s, rest=%s, x=%s, seq=%s, i=%s" % (res, rest, x, seq, i))
                res.append(seq[i] + x) # Add node at front
                print("2차 for문 진행후 res=%s, rest=%s, x=%s, seq=%s, i=%s" % (res, rest, x, seq, i))
    return res

print(permute1("abc"))

코드해석

함수의 첫 if not seq:는 재귀알고리즘을 중지시키는 역할을 한다. 메인은 else:문이다.
for i in range(len(seq)):로 for문이 작동하는데 i=0인 경우만 생각해보자. (i=1, i=2인 경우를 모두 생각해보려고 하면 너무 복잡해진다. i=0인 경우만 이해하고 같은 논리로 i=1, i=2인 경우를 이해하면 된다.)

i=0, rest=bc, seq=abc -> permute(bc)=bc,cb / res=abc,acb
--ㄴ i=0, rest=c, seq=bc -> permute(c)=c / res=bc
----ㄴ i=0, rest=‘’, seq=c -> permute(‘’)=‘’ / res=c
--ㄴ i=1, rest=b, seq=bc -> permute(b)=b / res=cb
----ㄴ i=0, rest=‘’, seq=b -> permute(‘’)=‘’ / res=b

i=0일 때 코드가 진행되는 전체적인 구조는 다음과 같다. -가 많아질 수록 다음 단계의 재귀로 들어가는 것이고 같은 수의 --가 있는 부분은 동일한 깊이의 재귀 단계로 생각하면 된다.
주의해야하는 부분은 i를 구분해야 한다는 점이다. 같은 라인에 있어야 동일한 지역변수 i임을 의미한다. 그래서 --단계의 i는 0,1이 있고 ----단계의 i는 0만 존재한다.(경위의 수가 각각 2가지, 1가지가 있기 때문.) 재귀 알고리즘의 깊이별 res 지역변수의 공간도 구별해주어야 한다.
재귀 알고리즘의 연결성을 요약하면 3번째줄의 결과 res=c가 2번째줄의 permute(c)의 결과가 되는 것이고 5번째줄의 결과 res=b가 4번째줄의 permute(b)의 결과가 된다. 같은 논리로 2번째줄의 res=bc와 4번째줄 res=cb(같은 --라인 -> 같은 깊이의 재귀 알고리즘 상황)은 1번째줄의 permute(bc)의 결과가 된다.
i=0인 경우를 마치면 res=abc,acb가 존재하게 되고, 함수를 적용한 나머지 원소들은 i=1, i=2의 경우로 만들어진다.

실행결과

1차 for문 진행중 seq=abc, i=0, rest=bc
1차 for문 진행중 seq=bc, i=0, rest=c
1차 for문 진행중 seq=c, i=0, rest=
not seq인 경우
2차 for문 진행전 res=[], rest=, x=, seq=c, i=0
2차 for문 진행후 res=['c'], rest=, x=, seq=c, i=0
2차 for문 진행전 res=[], rest=c, x=c, seq=bc, i=0
2차 for문 진행후 res=['bc'], rest=c, x=c, seq=bc, i=0
1차 for문 진행중 seq=bc, i=1, rest=b
1차 for문 진행중 seq=b, i=0, rest=
not seq인 경우
2차 for문 진행전 res=[], rest=, x=, seq=b, i=0
2차 for문 진행후 res=['b'], rest=, x=, seq=b, i=0
2차 for문 진행전 res=['bc'], rest=b, x=b, seq=bc, i=1
2차 for문 진행후 res=['bc', 'cb'], rest=b, x=b, seq=bc, i=1
2차 for문 진행전 res=[], rest=bc, x=bc, seq=abc, i=0
2차 for문 진행후 res=['abc'], rest=bc, x=bc, seq=abc, i=0
2차 for문 진행전 res=['abc'], rest=bc, x=cb, seq=abc, i=0
2차 for문 진행후 res=['abc', 'acb'], rest=bc, x=cb, seq=abc, i=0
1차 for문 진행중 seq=abc, i=1, rest=ac
1차 for문 진행중 seq=ac, i=0, rest=c
1차 for문 진행중 seq=c, i=0, rest=
not seq인 경우
2차 for문 진행전 res=[], rest=, x=, seq=c, i=0
2차 for문 진행후 res=['c'], rest=, x=, seq=c, i=0
2차 for문 진행전 res=[], rest=c, x=c, seq=ac, i=0
2차 for문 진행후 res=['ac'], rest=c, x=c, seq=ac, i=0
1차 for문 진행중 seq=ac, i=1, rest=a
1차 for문 진행중 seq=a, i=0, rest=
not seq인 경우
2차 for문 진행전 res=[], rest=, x=, seq=a, i=0
2차 for문 진행후 res=['a'], rest=, x=, seq=a, i=0
2차 for문 진행전 res=['ac'], rest=a, x=a, seq=ac, i=1
2차 for문 진행후 res=['ac', 'ca'], rest=a, x=a, seq=ac, i=1
2차 for문 진행전 res=['abc', 'acb'], rest=ac, x=ac, seq=abc, i=1
2차 for문 진행후 res=['abc', 'acb', 'bac'], rest=ac, x=ac, seq=abc, i=1
2차 for문 진행전 res=['abc', 'acb', 'bac'], rest=ac, x=ca, seq=abc, i=1
2차 for문 진행후 res=['abc', 'acb', 'bac', 'bca'], rest=ac, x=ca, seq=abc, i=1
1차 for문 진행중 seq=abc, i=2, rest=ab
1차 for문 진행중 seq=ab, i=0, rest=b
1차 for문 진행중 seq=b, i=0, rest=
not seq인 경우
2차 for문 진행전 res=[], rest=, x=, seq=b, i=0
2차 for문 진행후 res=['b'], rest=, x=, seq=b, i=0
2차 for문 진행전 res=[], rest=b, x=b, seq=ab, i=0
2차 for문 진행후 res=['ab'], rest=b, x=b, seq=ab, i=0
1차 for문 진행중 seq=ab, i=1, rest=a
1차 for문 진행중 seq=a, i=0, rest=
not seq인 경우
2차 for문 진행전 res=[], rest=, x=, seq=a, i=0
2차 for문 진행후 res=['a'], rest=, x=, seq=a, i=0
2차 for문 진행전 res=['ab'], rest=a, x=a, seq=ab, i=1
2차 for문 진행후 res=['ab', 'ba'], rest=a, x=a, seq=ab, i=1
2차 for문 진행전 res=['abc', 'acb', 'bac', 'bca'], rest=ab, x=ab, seq=abc, i=2
2차 for문 진행후 res=['abc', 'acb', 'bac', 'bca', 'cab'], rest=ab, x=ab, seq=abc, i=2
2차 for문 진행전 res=['abc', 'acb', 'bac', 'bca', 'cab'], rest=ab, x=ba, seq=abc, i=2
2차 for문 진행후 res=['abc', 'acb', 'bac', 'bca', 'cab', 'cba'], rest=ab, x=ba, seq=abc, i=2
['abc', 'acb', 'bac', 'bca', 'cab', 'cba']