Kotlin Permutation(순열)

 

 

 

 

---

1. Permutation - 순열

 

순열 : 서로 다른 n개의 원소에서 r개를 중복없이 골라 순서에 상관있게 나열하는 것

 

ex) a, b, c 가 있다면

 

1개 선택 -> (a), (b), (c)

2개 선택 -> (a,b), (a,c), (b,a), (b,c), (c,a), (c,b)

3개 선택 -> (a,b,c), (a,c,b), (b,a,c), (b,c,a), (c,a,b), (c,b,a)

 

이처럼 순열을 구할 수 있다.

 

 

 

Kotlin에서는 회귀와 flatMap 함수를 사용하여 순열을 구현할 수 있다.

 

 

Kotlin flatMap - 원소 값 변경 및 추가

 

 

 

 

---

2. 코 드

환경 : Kotlin Version = 1.4.20, JVM

fun <T> permutation(el: List<T>, fin: List<T> = listOf(), sub: List<T> = el ): List<List<T>> {
    return if(sub.isEmpty()) listOf(fin)
        else sub.flatMap { permutation(el, fin + it, sub - it) }
}

fun main(args: Array<String>) {
    val list = mutableListOf('a', 'b', 'c', 'd')
    val list2 = permutation(list)
    list2.forEach { print("$it ") }
    println()

    val list3 = mutableListOf(1, 2, 3, 4, 5)
    val list4 = permutation(list3)
    list4.forEach { print("$it ") }
    println()

    val str = "abcd"
    val list5 = permutation(str.toList())
    list5.forEach { print("$it ") }
}

 

결 과

 

- permutation 순열 함수를 제네릭 타입 형태로 만듬으로써 숫자 리스트나, 문자 리스트, 문자열을 함수를 사용하여 순열을 구해낼 수 있다.

 

 

 

- 인수로는 순열을 구하고자하는 원소들을 갖는 리스트를 받는다.

 

 

 

- 반환 타입은 List<List<T>> 타입으로서 List의 원소 리스트에는 각각 순서가 다른 원소들이 들어 있다.

 

 

---

(추가 설명)

 

순열을 구할 때 회귀가 사용되어서 회귀가 이해하기도 어렵고 설명하기도 어렵기 때문에 간단한 예시를 갖고 설명 드리겠습니다.

 

우선 permutation 함수의 파라미터를 설명하자면

 

el: 원본 데이터로서 변하지 않음  -> elements를 줄여서 el

fin: 원소를 담는 리스트로서 기본값은 listOf()로 빈 리스트  ->  finish를 줄여서 fin

sub: fin이 담는 리스트라면 sub는 빼는 리스트 기본값은 el  -> subtraction 줄여 sub

 

구조를 간단하게 설명하자면 sub의 있는 원소를 빼서 fin의 넣는 과정을 반복하여 sub가 비었을 때 fin을 반환합니다.

 

 

 

ex) listOf(1, 2, 3) 의 순열을 구할 경우

====1====

el: (1, 2, 3)

fin: ()

sub: (1, 2, 3)

 

sub가 비어있지 않으므로 else문이 실행되며

 

sub 리스트의 faltMap 이 실행되어 permutation(el, fin + 1, sub -1) 이 실행됩니다.

 > sub는 현재 (1, 2, 3)이므로 it=1 경우부터 시작,  1->2->3 순 실행

 > fin 리스트의 +1을 하여 원소 1을 추가하고 sub 리스트의 -1을 하여 원소 1을 제거합니다.

 

 

====2====

el: (1, 2, 3)

fin: (1)

sub: (2, 3)

 

위와 동일

 

 

====3====

el: (1, 2, 3)

fin: (1, 2)

sub: (3)

 

위와 동일

 

 

====4====

el: (1, 2, 3)

fin: (1, 2, 3)

sub: ()

 

sub가 비었으므로 fin을 반환하여 추가합니다. flatMap의 동작 방식을 모르겠다면 위의 flatMap 참고글을 봐주세요.

 

 

====5====

el: (1, 2, 3)

fin: (1, 3)

sub: (2)

 

회귀이기 때문에 3번으로 다시 가지만 sub it=3 다음은 없으므로 끝나 다시 2번으로 돌아갑니다. 

 

2번의 it=2일 경우 최종적으로 fin (1, 2, 3)을 반환하여 끝났으므로 그 다음 it=3일 경우가 실행됩니다. 그러면

 

el: (1, 2, 3)

fin: (1)

sub: (2, 3)

 

인 상태에서 permutation(el, fin + 3, sub - 3)이 실행되게 되며 현재 5번과 같은 상태가 됩니다.

 

 

 

이 같은 과정이 반복함으로써 최종적으로 순열을 구할 수 있게 됩니다.

 

---

 

해당 예시에서는 el은 사용하지 않기 때문에 굳이 있을 필요가 없습니다. 중간 원본 데이터를 사용하여 처리할 경우를 생각하여 파라미터로 넣어놨을 뿐입니다.

fun <T> permutation(sub: List<T>, fin: List<T> = listOf()): List<List<T>> {
    return if(sub.isEmpty()) listOf(fin)
        else sub.flatMap { permutation(sub - it, fin + it) }
}

 

이처럼 el을 제거하여도 무관합니다.