[알고리즘] 순열(Permutation)

계기

SSAFY 교육 정리

순열(Permutation)

• 서로 다른 것들 중 몇 개를 뽑아서 한 줄로 나열하는 것
• 서로 다른 n개 중 r개를 택하는 순열은 아래와 같이 표현한다.

• 그리고 nPr은 다음과 같은 식이 성립한다
  

• nPn = n!이라고 표기하며 Factorial이라 부른다.
  

• 다수의 알고리즘 문제들은 순서화된 요소들의 집합에서 최선의 방법을 찾는 것과 관련 있다.

  • 예> TSP(Traveling Salesperson Problem, 외판원 순회)

• N개의 요소들에 대해서 n!개의 순열들이 존재한다.

  • 12! = 479,001,600
  • n > 12 인 경우, 시간 복잡도 폭발적으로 ↑

• 단순하게 순열을 생성하는 방법
  • 예) {1, 2, 3}을 포함하는 모든 순열을 생성하는 함수
    • 동일한 숫자가 포함되지 않았을 때, 각 자리 수 별로 loop을 이용해 아래와 같이 구현할 수 있다.

FOR i1 in 1 -> 3
   FOR i2 in 1 -> 3
      IF i2 ≠ i1
          FOR i3 in 1 -> 3
              IF i3 ≠ i1 AND i3 ≠ i2
                print(i1, i2, i3)

• 사전적 순서(Lexicographic-Order)

  • {1, 2, 3}, n = 3 인 경우 다음과 같이 생성된다.
  • [1 2 3] [1 3 2] [2 1 3] [2 3 1] [3 1 2] [3 2 1]

• 최소 변경을 통한 방법(Minimum-exchange requirement)

  • 각각의 순열들은 이전의 상태에서 단지 두 개의 요소들 교환을 통해 생성
  • [1 2 3] [3 2 1] [2 3 1] [2 1 3] [3 1 2] [1 3 2]

• swap을 통한 순열 생성

// arr[] : 데이터가 저장된 배열
// swap(i, j) : arr[i] <--교환--> arr[j]
// n: 원소의 개수, k: 현재까지 교환된 원소의 개수
perm(n, k)
    IF k == n
        print array // 원하는 작업 수행
    ELSE
        FOR i in k -> n-1
            swap(k, i);
            perm(n, k+1);
            swap(k, i);

• 방문 체크를 통한 순열 생성

nums: 데이터
result : 결과 저장 배열
check : 해당 원소 사용했는지 체크하기 위한 배열

permutation(idx) {
    if idx == N
        (순열 생성완료)
        return
    for i from 0 to N-1
        if check[i] { continue }
        result[idx] = nums[i]
        check[i] = true
        permutation(idx+1)
        check[i] = false
}

• 비트 마스킹을 통한 순열 생성

nums : 데이터
sel : 결과 저장 배열
visited : 해당 원소 사용했는지 체크
permutation(idx, visited) {
    if idx == N
        (순열 생성완료)
        return
    for i from 0 to N-1
        if visited & (1 << i) != 0 { continue }
        sel[idx] = nums[i]
        permutation(idx+1, visited | 1 << i)
}