순열 파이썬 구현

1. 순열 (Ordered Sequence, Permutation)

  ㅇ 전체(n) 중 일부(r)를 선택하여 순서적으로 나열 (nPr)

  ㅇ 경우의 수  :  
[# _nP_r = \frac{n!}{(n-r)!} #]

  ㅇ 재귀 트리
     


2. 파이썬에 의한 순열 구현 例)

  
def permutation(arr, r):
    result = []
    if r > len(arr):
        return result
    if r == 1:
        for i in arr:
            result.append([i])
    elif r > 1:
        # 주어진 수열 내 각 원소를 추출 및 처리하는 반복문
        for i in range(len(arr)):
            # 주어진 수열과 동일한 수열 생성
            ans = [j for j in arr]
            # 주어진 수열에서 추출된 원소를 제외
            ans.remove(arr[i])
            # 추출된 원소 이외 나머지 수열에 대해 재귀 호출하고, 그 결과를 덧붙이는 반복문
            for p in permutation(ans, r-1):
                # 추출된 원소 arr[i] 뒤에 재귀 호출 permutation(ans, r-1)의 결과 p를 덧붙임
                result.append([arr[i]] + p)
    return result

if __name__ == "__main__" :
    arr = ['a','b','c']
    print(permutation(arr, 3))
        # [['a','b','c'], ['a','c','b'], ['b','a','c'], ['b','c','a'], ['c','a','b'], ['c','b','a']]
    print(permutation(arr, 2))
        # [['a','b'], ['a','c'], ['b','a'], ['b','c'], ['c','a'], ['c','b']]
    print(permutation(arr, 1))
        # [['a'], ['b'], ['c']]