Permutations (순열)

If you prefer english, I recommend you to use immersive translation or google translate.

개요

서로 다른 n개의 원소에서 r개를 선택하여 나열하는 경우의 수

재귀

코드

function getPermutations<T>(arr: T[]): T[][] {
    const result: T[][] = [];

    function permute(currentPermutation: T[], remainingElements: T[]) {
        if (remainingElements.length === 0) {
            result.push(currentPermutation);
            return;
        }

        for (let i = 0; i < remainingElements.length; i++) {
            const nextElement = remainingElements[i];
            const newRemainingElements = remainingElements.slice(0, i).concat(remainingElements.slice(i + 1));
            permute(currentPermutation.concat(nextElement), newRemainingElements);
        }
    }

    permute([], arr);
    return result;
}

기본적인 아이디어는 아래와 같다.

1. 남은 요소 중 하나를 선택하여 현재 순열에 추가
2. 나머지 요소들로 다시 순열을 생성 (재귀)
3. 모든 요소를 선택하면 순열 완성

시각화

실제 [1, 2, 3] 을 값으로 넣었다고 생각하고 따라가보자.

plantUML

@startmindmap
* getPermutations([1, 2, 3])
** 1. nextElement = 1\npermute([1], [2, 3])
*** 1.1. nextElement = 2\npermute([1, 2], [3])
**** 순열 완성: [1, 2, 3]
*** 1.2. nextElement = 3\npermute([1, 3], [2])
**** 순열 완성: [1, 3, 2]
** 2. nextElement = 2\npermute([2], [1, 3])
*** 2.1. nextElement = 1\npermute([2, 1], [3])
**** 순열 완성: [2, 1, 3]
*** 2.2. nextElement = 3\npermute([2, 3], [1])
**** 순열 완성: [2, 3, 1]
** 3. nextElement = 3\npermute([3], [1, 2])
*** 3.1. nextElement = 1\npermute([3, 1], [2])
**** 순열 완성: [3, 1, 2]
*** 3.2. nextElement = 2\npermute([3, 2], [1])
**** 순열 완성: [3, 2, 1]
@endmindmap

mermaid

graph TD
A["getPermutations([1, 2, 3])<br/>permute([], [1, 2, 3])"] --> B["1. nextElement = 1<br/>permute([1], [2, 3])"]
A --> C["2. nextElement = 2<br/>permute([2], [1, 3])"]
A --> D["3. nextElement = 3<br/>permute([3], [1, 2])"]

B --> E["1.1. nextElement = 2<br/>permute([1, 2], [3])"]
B --> F["1.2. nextElement = 3<br/>permute([1, 3], [2])"]

C --> G["2.1. nextElement = 1<br/>permute([2, 1], [3])"]
C --> H["2.2. nextElement = 3<br/>permute([2, 3], [1])"]

D --> I["3.1. nextElement = 1<br/>permute([3, 1], [2])"]
D --> J["3.2. nextElement = 2<br/>permute([3, 2], [1])"]

E --> K["순열 완성:<br/>[1, 2, 3]"]
F --> L["순열 완성:<br/>[1, 3, 2]"]
G --> M["순열 완성:<br/>[2, 1, 3]"]
H --> N["순열 완성:<br/>[2, 3, 1]"]
I --> O["순열 완성:<br/>[3, 1, 2]"]
J --> P["순열 완성:<br/>[3, 2, 1]"]

classDef root fill:#e1f5fe
classDef level1 fill:#e8f5e8
classDef level2 fill:#fff3e0
classDef result fill:#ffebee

class A root
class B,C,D level1
class E,F,G,H,I,J level2
class K,L,M,N,O,P result

---

비재귀

코드

function getPermutationsIterative<T>(arr: T[]): T[][] {
    const result: T[][] = [];
    let currentPermutation = [...arr].sort(); // 시작은 정렬된 배열이어야 합니다.

    while (currentPermutation) {
        result.push([...currentPermutation]);
        currentPermutation = getNextPermutation(currentPermutation);
    }

    return result;
}

function getNextPermutation<T>(arr: T[]): T[] | null {
    const n = arr.length;
    let i = n - 2;

    // 1. 뒤에서부터 arr[i] < arr[i+1]을 만족하는 첫 번째 i를 찾습니다.
    // 이러한 i가 없으면, 배열은 마지막 순열입니다.
    while (i >= 0 && arr[i] >= arr[i + 1]) {
        i--;
    }

    if (i === -1) {
        return null; // 마지막 순열입니다.
    }

    // 2. 뒤에서부터 arr[j] > arr[i]을 만족하는 첫 번째 j를 찾습니다.
    let j = n - 1;
    while (arr[j] <= arr[i]) {
        j--;
    }

    // 3. arr[i]와 arr[j]를 교환합니다.
    [arr[i], arr[j]] = [arr[j], arr[i]];

    // 4. arr[i+1]부터 끝까지의 부분을 뒤집습니다.
    let left = i + 1;
    let right = n - 1;
    while (left < right) {
        [arr[left], arr[right]] = [arr[right], arr[left]];
        left++;
        right--;
    }

    return arr;
}

시각화

프로세스

[1, 2, 3] 예제

Ref

• nayuki.io