[Kotlin] - 순열, 조합, 중복순열, 중복조합

완전탐색, 백트래킹, DFS에서 조합과 순열을 많이 사용한다.

Kotlin은 정말 잘 만든 언어이지만, 조합은 파이썬처럼 라이브러리로 구현되어 있지 않아서 우리가 한 땀 한 땀 구현을 해야 한다.

매번 문제를 풀 때 헷갈리기도 하고, 정리하면 좋을 거 같아서 포스팅하게 되었다.

---

 

순열 (Permutation)

정의는 다음과 같다.

서로 다른 n개의 원소에서 r개를 중복 없이 순서에 상관있게 선택하는 혹은 나열하는 것

중복이 없고, 순서가 있다는 것이 순열의 특징이다.

순열은 재귀함수를 통해서 구현할 수 있다.

cnt는 현재 내가 뽑은 원소의 수, depth는 내가 뽑아야 할 원소의 수이다.

즉 원소의 개수가 N이고, 내가 중복 없이 순서를 지키면서 R개를 뽑으려고 할 때는 nPr이고,

makePermutation(0, R)을 호출하면 된다.

기본적인 흐름은 다음과 같다.

1. 재귀의 깊이는 내가 뽑고자 하는 원소의 개수인 depth이다.
   • 만약 다 뽑았다면 문제 요구사항에 맞는 처리과정을 거치고, return을 통해서 재귀 함수를 탈출한다.
   • 뽑지 않았다면 2번 과정을 진행한다.
2. 전체 리스트를 돌면서 방문여부에 대해서 검사를 한다.
   • 방문 여부를 검사하는 이유는 순열은 중복을 허용하지 않기 때문이다.
3. 방문하지 않은 원소라면 배열에 추가하고, 방문 처리를 하고 재귀함수를 호출한다.
4. 재귀함수를 탈출하면 해당 원소에 대한 방문처리와 집합에서 제거해 준다.

코드

val List = listOf("a","b","c","d","e")
val myList = mutableListOf<String>()
val isPick = BooleanArray(List.size){false}
fun main(){
    print("기준 원소 : ")
    List.forEach{num->
        print("$num ")
    }
    println()
    makePermutation(0,3)
}
fun makePermutation(cnt : Int, depth : Int){
    if(cnt==depth){ // R개를 뽑았을 경우
        myList.forEach {num->
            print("$num ")
        }
        println()
        return
    }
    for(element in List){
        val index = List.indexOf(element)
        if (isPick[index]) continue //이미 추가한 원소라면 넘어감.
        isPick[index] = true //방문 처리
        myList.add(element) //원소 추가
        makePermutation(cnt+1,depth) //재귀 호출
        myList.remove(element) //원소 제거
        isPick[index]=false //방문 처리
    }
}

결과

결과가 너무 많아서 전부 캡처하지 못했지만, 주목해야 할 점은 {a, b, c}와 {b, a, c}가 다르게 취급된다는 것이다.

 

중복 순열

정의는 다음과 같다.

중복 순열은 순열과 마찬가지로 n개 중에 r개를 순서에 상관있게 뽑는데, 중복을 허락하여 뽑는 것을 말한다.

순열과 다른 점은 중복을 허용한다는 점이다.

따라서 순열의 코드에서 isPick이라는 중복을 검사하는 부분을 제거하면 중복 순열의 구현이 된다.

코드

val List = listOf("a","b","c","d","e")
val myList = mutableListOf<String>()
fun main(){
    print("기준 원소 : ")
    List.forEach{num->
        print("$num ")
    }
    println()
    makePermutation(0,3)
}
fun makePermutation(cnt : Int, depth : Int){
    if(cnt==depth){
        myList.forEach {num->
            print("$num ")
        }
        println()
        return
    }
    for(element in List){
        myList.add(element)
        makePermutation(cnt+1,depth)
        myList.remove(element)
    }
}

결과

 

조합 (Combination)

정의는 다음과 같다.

조합이란 n개의 원소를 갖는 집합에서 r개의 원소를 선택하는 것 

순열과 다른 점은 순서가 없다는 뜻이다. 순서가 없다는 뜻은 {a, b, c}와 {b, c, a}가 동일하다는 얘기이다.

조합은 순서를 생각할 필요가 없기에 방문처리보다는 원소의 탐색 시작시점을 변화시켜서 추가하는 것이 기본적이다.

makeCombination을 뜯어보면 

cnt는 추가한 원소의 수, cur : 추가한 원소의 index, depth : 뽑아야 할 원소의 개수

따라서 원소를 추가하고 재귀를 호출할 때, 추가한 원소의 index인 i를 cur에 넣어준다.

 

 

코드

val list = listOf("a","b","c","d","e")
val myList = mutableListOf<String>()
fun main(){
    print("기준 원소 : ")
    list.forEach{num->
        print("$num ")
    }
    println()
    makeCombination(0,0,3)
}
fun makeCombination(cnt : Int, cur : Int, depth : Int){
    if(cnt==depth){
        myList.forEach {num->
            print("$num ")
        }
        println()
        return
    }
    for(i in cur until  list.size){
        myList.add(list[i])
        makeCombination(cnt+1,i+1,depth)
        myList.removeLast()
    }
}

 

결과

 

중복 조합

 

정의는 다음과 같다.

중복 조합은 조합과 마찬가지로 n개 중에 r개를 순서에 상관없이 뽑는데, 중복을 허락하여 뽑는 것을 말한다.

 

 

코드

val list = listOf("a","b","c","d","e")
val myList = mutableListOf<String>()
fun main(){
    print("기준 원소 : ")
    list.forEach{num->
        print("$num ")
    }
    println()
    makeCombination(0,0,3)
}
fun makeCombination(cnt : Int, cur : Int, depth : Int){
    if(cnt==depth){
        myList.forEach {num->
            print("$num ")
        }
        println()
        return
    }
    for(i in cur until  list.size){
        myList.add(list[i])
        makeCombination(cnt+1,i,depth)
        myList.removeLast()
    }
}

조합은 원소가 중복되면 안 되기에, 탐색할 원소의 인덱스를 추가한 경우 +1 해줘야 하지만,

중복조합은 원소가 중복돼도 상관없기에, 탐색할 원소의 인덱스를 변경해주지 않아도 된다.

반복문이 돌아가면서 i에 맞게 원소를 추가해 주면 된다.

 

결과

조합인데 원소가 중복되는 결과를 볼 수 있다.