재귀로 순열과 중복순열 만들기

경우의 수를 빠짐없이 만들어내는 게 완전탐색의 절반이다. 중복을 허용하느냐 아니냐에 따라 재귀의 모양이 꽤 달라진다.

중복순열

1, 2, 3으로 4자리 수를 만드는 경우다. 같은 숫자를 여러 번 써도 된다.

def do(li, cur, length):
    if len(cur) == length:
        print(cur)
        return

    for i in li:
        do(li, cur + str(i), length)

do([1, 2, 3], '', 4)

자리마다 후보 전체를 다시 훑으면 된다. 무엇을 이미 썼는지 기억할 필요가 없어서 상태가 cur 하나뿐이다. 3의 4제곱인 81개가 나온다.

중복을 빼려면

0~9에서 서로 다른 숫자 4개를 뽑는 걸 같은 방식으로 짜봤다.

def perm(n, cur=[]):
    if n == 0:
        if len(set(cur)) == 4: print(cur)
        return

    for i in range(10):
        perm(n - 1, cur + [i])

중복순열을 그대로 만든 뒤 set 으로 바꿔 길이가 4면 통과시키는 방식이다. 답은 맞게 나온다.

문제는 만들어놓고 버리는 양이다. 10의 4제곱인 10000개를 전부 만들어서 그중 5040개만 남긴다. 자리가 늘어날수록 버리는 비율이 커진다.

자리를 맞바꾸는 방식

만들지 않는 쪽으로 바꿨다.

def perm(x, li):
    if x == 5:
        print(data)

    for y in range(x, n):
        data[x], data[y] = data[y], data[x]
        perm(x + 1, data)
        data[x], data[y] = data[y], data[x]

n = 5
data = [i for i in range(1, n + 1)]
perm(0, data)

x 번째 자리를 정할 차례에, x 이후의 아무 원소나 하나 끌어와 x 자리에 놓는다. 이미 앞에서 확정한 것은 range(x, n) 밖이라 다시 선택되지 않는다. 중복 검사가 필요 없어진다.

핵심은 재귀에서 돌아온 뒤 다시 맞바꿔 원래대로 되돌리는 마지막 줄이다. 이게 없으면 다음 y 를 시도할 때 배열이 이미 흐트러져 있다.

배열 하나를 계속 고쳐 쓰기 때문에 cur + [i] 처럼 매번 새 리스트를 만들지 않는다는 것도 다르다.

두 군데가 마음에 걸린 채로 남아 있다. 종료 조건의 5 가 n 이 아니라 숫자로 박혀 있고, li 를 인자로 받으면서 정작 안에서는 전역 data 를 쓴다. n 을 바꾸면 바로 어긋난다.