[재귀함수] 순열구하기 / Python

문제

서로 다른 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개만을 뽑아 나열하는 경우를 사전순으로 나열한 결과를 출력한다.

입출력 예시

💡 사고의 흐름

• 입력값 r 만큼 for 문을 반복해야 함.
  -> 재귀함수를 통한 for 문 사용 !
• alpha -> 넣을 알파벳
• 알파벳 중복되면 안되니까 list 형태의 check를 두어 체크해줌!
• x==r일때 출력하도록 하고, 바깥의 값부터 제거(pop)해주며 모든 경우를 다 조합해봄.

Code

import sys
check=[False] * 100
result=[]

def permutation(x):
  if x>=r:
    for res in result:
      print(res, end='')
    print('')
  else:
    for i in range(n):
      alpha = chr(ord('a')+i)
      if check[i]==False:
        result.append(alpha)
        check[i]=True
        permutation(x+1)
        check[i]=False
        result.pop()
        
if __name__=='__main__':
  n,r = map(int, sys.stdin.readline().split())
  permutation(0)