2021-02-10

순열(Permutation)

순열을 구현하는 가장 쉬운 방법은 재귀적으로 접근하는 것이다. 다음처럼 접근해보자.
written by

Introduction

순열(Permutation)을 구하는 방법에 대해서 알아보자. 우선 순열의 개수를 구하는 수식을 보자.

  • nPr = n!/(n-r)!

이 수식이 의미하는 바는 무엇인가?

5개의 당구공이 있는데 3개를 골라내야 한다면 다음과 같이 골라낼 수 있을 것이다.

  • 남은 5개의 당구공에서 한 개를 골라내는 5가지 선택지가 있다.
  • 남은 4개의 당구공에서 한 개를 골라내는 4가지 선택지가 있다.
  • 남은 3개의 당구공에서 한 개를 골라내는 3가지 선택지가 있다.

순서에 의미가 있기 때문에 중복되는 당구공을 골라내더라도 다른 순열로 봐야 한다. 따라서 중복되는 당구공을 골라내는 경우는 신경 쓸 필요가 없다.

Algorithm

순열(Permutation)을 구현하는 가장 쉬운 방법은 재귀적으로 접근하는 것이다. 다음처럼 접근해보자.

  • 기존에 선택한 당구공들로 만든 순열에 나머지에 대한 순열을 구해서 더한다.
  • 당구공들이 더 이상 남아있지 않으면 모든 당구공에 대한 순열을 구한 것이다.

만약 특정 개수에 대한 순열만 구하고 싶다면 재귀 함수를 특정 개수의 깊이만큼만 호출하고 종료하면 된다.

Kotlin Scratch Code

// depth == 선택할 수 있는 당구공의 개수.
fun permutation(balls: List<Int>, depth: Int = balls.size, permutation: String = "") {
    if (depth == 0 || balls.isEmpty()) {
        println(permutation.toList())
    } else {
        for (i in balls.indices) {
            permutation(balls.filterIndexed { j, _ -> j != i }, depth - 1, permutation + balls[i])
        }
    }
}

// [1, 2, 3]이라는 3개의 당구공 중에서 2개의 당구공으로 구할 수 있는 모든 순열을 출력한다.
permutation(listOf(1, 2, 3), depth = 2)

Result

[1, 2]
[1, 3]
[2, 1]
[2, 3]
[3, 1]
[3, 2]
2021 © Cinntiq's Studio