Permutation(순열) 알고리즘

Permutation은 알고리즘 문제를 풀다보면 다른 문제와 결합되어 자주 출제되는 문제 중 하나다.

 

여기서는 중복 순열은 다루지 않고 나중에 다루도록 하겠다.

 

순열은 [1,2,3,4]에서 4개를 뽑아 순서를 정하는 순열은

1,2,3,4

1,2,4,3

1,3,2,4,

1,3,4,2

1,4,2,3,

1,4,3,2

...

이렇게 나오게 될 것이다.

 

이 글에서는 permutation 알고리즘을 구현하는 것과 다음 permutation을 구하는 알고리즘을 구현하겠다.

 

1.모든 Permutation을 구하는 코드 작성

 

함수의 매개변수로는 배열 또는 리스트[numbers], 몇 개를 뽑을 건지[r], 그리고 배열의 값을 변경할 위치[depth]

 

모든 Permutation을 구하는 코드를 설명하자면, recurssion으로 구현했다.

 

구현하는 함수의 이름을 permutation(numbers:List[int], r:int, depth:int)

현재 depth 위치에서 시작해서 배열의 끝까지를 가면서

swap(numbers[i], numbers[depth])

permutation(numbers, r, depth+1)

swap(numbers[i], numbers[depth])

이렇게 depth == r 이 될 때 까지 진행한다.

 

depth == r 이면

if depth == r:

      print numbers from 0 to r-1

      return

r 개의 순열을 출력하면 우리가 원하는 함수를 만들 수 있다.

 

2. 다음 순열을 구하는 함수를 구현해 보자

현재 순열 [2,1,3,4] 가 주어졌다면 이 함수를 실행하면 [2,1,4,3]을 반환하는 함수를 구현해야 한다.

 

leetcode discussion에서 다른 사람의 code를 보고 공부했다. 다음 순열을 구하는 아이디어는 증가하는 부분과 감소하는 부분을 분리하는 것에 있다.

 

만약에 현재 순열 [4,3,2,1]이 주어졌다고 생각해보면, i = len(numbers] - 1에서 numbers[i-1] >= numbers[i] 이므로 최종적으로 i = 0이 될 것이다.

 

i를 기준으로 j = i + 1부터 len(numbers) -1 까지 [3,2,1]을 볼 때 numbers[i] 보다 큰 원소가 존재하지 않기 때문에, 

swap(numbers[i],numbers[j-1]) --> swap(numbers[0], numbers[0]) 하면 변경되는 원소는 없다.

반환해야 할 새로운 배열 또는 리스트는 numbers[:i+1](빈 배열), numbers[i+1:][::-1](1,2,3,4)를 연결한 것을 반환한다.

 

좀 더 일반적인 케이스 [2,1,3,4]가 주어졌으면, i = len(numbers) - 1에서 numbers[i-1] >= numbers[i] 를 만족하는 동안 i를 감소시키면 최종적으로 i = 2 이다.

i = 2에서의 오른편이면 i =3 부터 배열의 끝까지 numbers[i] < numbers[j] 를 만족하는 동안 j를 1씩 증가시킨다. 

최종적으로 j = 4 가 된다.

swap(numbers[i], numbers[j-1])하면 [4,3]이 되고 

numbers[:i+1](2,1,4) + numbers[i+1:][::-1](3)을 합쳐 새로운 배열을 반환한다.

 

 

3.  1 과 2 를 구현한 코드

def permutation(numbers:[int], r: int, depth:int):
    if r == depth:
        for i in range(0, r):
            print(numbers[i], end=' ')
        print()
        return

    for i in range(depth, len(numbers)):
        numbers[i], numbers[depth] = numbers[depth], numbers[i]
        permutation(numbers, r, depth+1 )
        numbers[i], numbers[depth] = numbers[depth], numbers[i]

def next_permutation(numbers:[int]):

    i = len(numbers) - 1
    while i >= 0 and numbers[i-1] >= numbers[i]:
        i -= 1
    i -= 1
    while i >= 0:
        j = i + 1
        while j < len(numbers) and numbers[i] < numbers[j]:
            j += 1
        numbers[j-1], numbers[i] = numbers[i], numbers[j-1]
        break
    numbers = numbers[:i+1] + numbers[i+1:][::-1]
    return numbers