[Algorithm 풀이] 재귀 함수 : 순열구하기

본 문제는 중복 수열 문제이다. 

문제

서로 다른 n개의 원소들 중에서 r개만을 뽑아 일렬로 나열하는 것을 순열이라 한다. 예를 들어, 3개의 원소 a, b, c 중에서 2개만을 뽑아 나열하면 ab, ac, ba, bc, ca, cb 의 6가지 경우가 있다. n과 r이 주어질 때, n개의 소문자 중에서 r개만을 뽑아 나열하는 모든 경우를 출력하는 프로그램을 작성하시오. 단, a부터 시작하여 연속으로 n개의 알파벳을 갖고 있다고 하자.

---

입력

첫 번째 줄에 n과 r이 주어진다. ( 1 ≤ n ≤ 10, 0 ≤ r ≤ min(n, 7) )  

출력

각 줄에 n개의 소문자 중에서 r개만을 뽑아 나열하는 경우를 사전순으로 나열한 결과를 출력한다.

---

예제 입력

4 2

예제 출력

ab
ac
ad
ba
bc
bd
ca
cb
cd
da
db
dc

---

CODE

def permutation(arr, r):
  result = []
  if r == 0:        
    return [[]]
  for i in range(len(arr)): 
    alpha = arr[i]
    for j in permutation(arr[:i] + arr[i+1:], r-1): #재귀호출
      result.append([alpha] + j)
  return result
        
if __name__=='__main__':
  n, r = map(int, input().split(" "))  
  alphabet_list = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z']
  arr = alphabet_list[:n]
  result_list = permutation(arr, r)
  print('\n'.join([''.join([str(k) for k in m])for m in result_list])) #2차원 리스트 출력

 

⭐️ SOLUTION ⭐️

1) 중복 수열 문제이기 때문에 리스트 안의 전체 요소를 하나씩 기준으로 삼아 탐색한다

2) 자기자신을 제외하고 앞, 뒤 탐색하면서 r만큼의 원소를 result에 추가한다.

for j in permutation(arr[:i] + arr[i+1:], r-1): #재귀호출