순열(Permutation)

순열(Permutation)

순열(Permutation)은 집합에서 일부 원소를 뽑아 순서를 고려하여 나열하는 것을 말한다. 예를 들어, 숫자 1, 2, 3으로 만들 수 있는 세 자리 수의 순열은 123, 132, 213, 231, 312, 321이다.

순열의 표기법

$n$ 개의 원소에서 $r$ 개를 선택하여 배열하는 경우: $_nP_r$
$n$ 개의 원소를 모두 배열하는 경우: $n!$
여기서 $n$은 집합의 크기, $r$은 선택하는 원소의 수다.

중복 순열

중복 순열은 원소의 중복을 허용하여 나열하는 것을 말한다. 예를 들어, 1, 2, 3으로 만들 수 있는 두 자리 수의 중복 순열은 11, 12, 13, 21, 22, 23, 31, 32, 33이다. 중복 순열의 경우 $_nP_r$로 표현할 수 없으며, 다음과 같은 식으로 나타낼 수 있다.

$n$ 개의 원소에서 $r$ 개를 선택하여 배열하는 경우: $n^r$

파이썬 코드

순열을 구현하기 위해서는 보통 재귀 함수를 사용한다.

# arr: 원소의 집합, r: 선택할 원소의 개수
def permutation(arr, r):
    # visited: 각 원소가 사용되었는지 여부를 저장하는 배열
    visited = [False] * len(arr)
    # result: 순열을 저장할 리스트
    result = []

    # chosen: 선택된 원소를 저장하는 리스트, remain: 선택되지 않은 나머지 원소들을 저장하는 리스트
    def generate(chosen, remain):
        # r개의 원소를 모두 선택한 경우, 결과 리스트에 추가하고 반환
        if len(chosen) == r:
            result.append(chosen[:]) # deepcopy를 통해 chosen 리스트를 복사해서 저장
            return

        # 나머지 원소들 중에서 사용되지 않은 원소를 하나씩 선택해 chosen 리스트에 추가하고, 다시 재귀적으로 호출
        for i in range(len(remain)):
            if not visited[i]:
                chosen.append(remain[i])
                visited[i] = True

                generate(chosen, remain)

                chosen.pop()
                visited[i] = False

    # 초기 호출: chosen 리스트와 remain 리스트를 빈 리스트와 arr로 초기화
    generate([], arr)
    # 순열 리스트 반환
    return result


arr = [1, 2, 3]
r = 2
permutations = permutation(arr, r)
print(permutations)

# [[1, 2], [1, 3], [2, 1], [2, 3], [3, 1], [3, 2]]