[Python] 중복순열 구하기 - DFS

오늘은 DFS를 이용하여 중복순열의 경우의 수를 출력하고 가짓수도 출력하는 코드를 작성해 봅시다.

중복순열 이란?

고등학교 수학시간에 순열과 조합을 배웠죠.

순서를 고려하고, n개 중 r개를 중복 없이/있이 뽑는 순열
순서를 고려하지 않고, n개 중 r개를 중복 없이/있이 뽑는 조합

그 중 중복순열 은 순서 고려하여 n개 중 r개를 중복 허용하여 뽑는 방법 입니다.

접근방법

A={1,2,3} 에서 숫자 2개를 뽑아 중복순열을 만든다고 가정합시다.

중복순열로 만들면 결과는
1 1
1 2
1 3
2 1
2 2
2 3
3 1
3 2
3 3
총 9개 (=$3^2$) 가 나옵니다.

이걸 어떻게 만들까요?

우선, 뽑혀진 숫자의 배열을 res 라 하고, res의 크기는 2개를 뽑는다 했으니 2개면 됩니다.

1) res[0]=1을 넣고 res[1]은 1~3까지 넣으면 되겠죠.
2) res[0]=1일때, 모든 경우의 수를 고려했으니 이제 res[0]=2를 넣고 1)을 반복합니다.
이런식으로 res[0]에 모든 원소를 넣고 1)과 2)를 반복하면 됩니다.

이중 반복문으로 쉽게 그려지니, 이제 DFS로 만들어 봅시다.
코드는 아래와 같습니다.

def DFS(L):
    global cnt #함수 내에서 사용하기 위해 전역변수 global로 선언
    if L==m:
        for i in range(m):
            print(res[i], end=' ')
        print()
        cnt+=1
    else:
        for i in range(1, n+1):
            res[L]=i
            DFS(L+1)

if __name__=="__main__":
    n, m=map(int, input().split())
    res=[0]*n
    cnt=0 #중복순열의 경우의 수를 세는 변수 (지역변수)
    DFS(0)
    print(cnt)

DFS(0) 일땐 res[0]에 숫자를 집어 넣고,
DFS(1) 일땐 res[1]에 숫자를 집어 넣습니다.
res 배열이 꽉 찬 경우는 곧 중복순열이 완성된 순간이니, 그 때 중복순열의 경우의 수를 출력하면 됩니다.

오늘의 게시글 끝!