재귀함수를 이용해 순열 구하기

✏️ 목표

1부터 n까지 번호가 적힌 구슬이 있는데, 이 중 m개를 뽑아 일렬로 나열하는 방법을 모두 출력해 보자.

(이때 출력 순서는 사전순으로 오름차순으로 한다.)

 

📍 입력

첫 번째 줄에 자연수 n(3 <= n <= 10)과 m(2 <= m <= n)이 주어진다.

 

 

 

❓ 순열

n개의 수 중에서 r개를 뽑아 순서대로 배열하는 경우의 수를 나타낸다.

중복순열에서는 동일한 수를 여러 번 뽑는 것이 가능하지만 그냥 순열에서는 하나의 수는 한 번만 뽑을 수 있다는 점에서 차이를 보인다.

수를 뽑았을 때 같은 구성이더라도 배열한 순서가 다르면 서로 다른 순열로 취급하는 것은 같다.

 

<ex>

1부터 3까지의 수 중에서 2개를 뽑아 순서대로 배열하면 (순열을 구하면)

(1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2) 이렇게 6가지의 순열을 만드는 것이 가능하다.

 

 

 

💡 해결하기

➡️ 트리로 표현할 때 한 노드에서 n개의 간선이 뻗어나가고, 반복문(for문)을 사용하여 1부터 n까지의 숫자를 모두 돌게 하여 pick 리스트에 뽑힌 숫자(현재 i의 값)를 차례로 기록(이것이 곧 일렬로 나열하는 것)하여 트리의 레벨을 나타내는 L이 뽑아야 할 숫자의 수인 m과 같아지면 pick에 기록된 숫자를 차례로 출력하는 기본적인 과정은 중복 순열에서와 비슷하다.

 

재귀함수를 이용해 중복순열 구하기 (tistory.com)

재귀함수를 이용해 중복순열 구하기

 

➡️ 그런데 중복순열에서와 다르게 그냥 순열에서는 숫자를 중복하여 뽑을 수 없다고 하였다. 즉, 뻗어나가는 간선 중 cut해야 할 것이 존재한다.

이를 구현하기 위해 어떤 숫자가 뽑혔는지를 기록하기 위한 체크 리스트인 ch를 만들어 주었다.

값이 1이면 그 index에 해당하는 숫자가 뽑혔다는 의미이고, 0이면 뽑히지 않았다는 의미이다.

ch의 길이는 숫자의 종류인 n보다 1 크게 만들어 주었고, 숫자 i를 선택할 때, i번째에 해당하는 부분을 1로 변경해 준다. 

그런 후 permutation 함수를 재귀 호출한다.

그 후에는 숫자 i를 선택한 것을 back 해야 하므로 ch[i]를 다시 0으로 만들어 숫자 i를 뽑지 않은 것으로 만들어 준다.

위 과정을 진행하기 전에는 ch[i]가 0인지(i가 이미 뽑힌 숫자인지)를 확인해야 한다.

 

📍 트리로 나타내보기

 

 

 

💻 Python으로 코드 작성하기

 

def permutation(L):
    global cnt
    if L == m:
        for num in pick:
            print(num, end=' ')
        print()
        cnt += 1
    else:
        for i in range(1, n + 1):
            # ch 리스트의 i번째 값이 0일 경우는 i가 뽑히지 않은 숫자임을 의미한다.
            if ch[i] == 0:
                # 숫자를 하나 고른 후 (그 숫자는 i이다.)
                pick[L] = i
                # ch 리스트의 해당 숫자에 해당하는 번째에 1 표시
                ch[i] = 1
                # permutation 함수 재귀 호출
                permutation(L + 1)
                # 뽑은 숫자를 다시 back하여 안 뽑은 상태로 돌아가기 (다음 i를 뽑기 위해)
                ch[i] = 0

n, m = map(int, input().split())
pick = [0] * m
ch = [0] * (n + 1)     # 중복을 피하기 위해 체크 리스트를 하나 만듦. 
cnt = 0
permutation(0)
print(cnt)

 

 

 

📌 참고 강의

파이썬 알고리즘 문제풀이 입문(코딩테스트 대비) 대시보드 - 인프런 | 강의 (inflearn.com)

파이썬 알고리즘 문제풀이 입문(코딩테스트 대비) - 인프런 | 강의