순열, 조합 구현하기(Kotlin - 코틀린 및 Python - 파이썬)

브루트 포스, 백트래킹 관련 문제를 풀 때 순열, 조합이 필요한 경우가 정말 많았는데 스스로 구현을 못해서... 정리를 해보게 되었다.

순열과 조합의 차이

순열은 permutation이다. nPr과 같은 형식으로 사용되는데 서로 다른 n개 중 r개를 "순서를 고려하고" 선택한다.
순열의 공식은 nPr = n! / (n-r)! 이다.
조합은 combination이다. nCr과 같은 형식으로 사용하며 서로 다른 n개 중 r개를 "순서를 고려하지 않고" 선택한다.
조합의 공식은 nCr = n! / (n-r)! * r! 이다.
둘의 큰 차이는 순서가 "고려되느냐 고려되지 않느냐" 이다.
n = [1, 2, 3, 4, 5]와 같은 수열이 있다. 여기서 3가지를 "순서를 고려"하여 뽑고 그 후에 "순서를 고려하지 않고" 뽑아보자.

순서를 고려하여 뽑기 (순열 == nPr)

1 2 3 
1 2 4 
1 2 5 
1 3 2 
1 3 4 
... 
5 3 2 
5 3 4 
5 4 1 
5 4 2 
5 4 3

nPr 공식을 적용하여보면 5P3 = 5! / (5-3)! = 60
총 60가지 경우의 수가 나온다. 너무 길어서 중간 부분은 생략했다.
순열은 [1 2 3]과 [3 2 1]을 다른 것으로 본다. 순서를 고려하기 때문이다.

순서를 고려하지 않고 뽑기 (조합 == nCr)

1 2 3 
1 2 4 
1 2 5 
1 3 4 
1 3 5 
1 4 5 
2 3 4 
2 3 5 
2 4 5 
3 4 5

nCr 공식을 적용하여보면 5C3 = 5! / (5-3)! * 3! = 10
총 10가지 경우의 수가 나온다.
조합은 [1 2 3]과 [3 2 1]을 같은 것으로 본다. 순서를 고려하기 때문이다.

순열 구현

순열을 구현하기 위해서 백트래킹, DFS를 사용하였다.
순열로 뽑힌 수들을 출력할 permutation()이라는 함수를 만들었다.
첫 번째 인자로는 cnt == 현재까지 뽑은 개수, 두 번째 인자로 depth == 총 뽑을 개수를 받는다.
numList = [1, 2, 3, 4, 5] 에서 순열로 3가지를 뽑고 싶다면(5P3) permutation(0, 3)을 ,
2가지를 뽑고 싶다면(5P2) permutation(0, 2)를 하면 된다.
numList는 총 원소가 담긴 리스트, visited는 해당 원소가 뽑혔는지(방문 처리) 확인할 리스트, pickednum은 순열로 뽑힌 숫자들이 담길 리스트이다.
재귀 호출을 하며 순열을 찾게 되는데 cnt == depth (현재 뽑은 개수 == 총 뽑을 개수) 가 될 때까지 재귀한다.
0 ~ 5인덱스까지 반복적으로 탐색하며 방문하지 않았다면 visited의 해당 인덱스를 true로 변환(방문 처리) pickednum에 해당 숫자를 넣고(뽑았다는 뜻), permutation(cnt+1,depth)를 재귀 호출하여 다음 인덱스를 확인한다. 탐색하며 방문하지 않은 곳들을 pickednum에 넣고 cnt와 depth가 같아지면 원하는 만큼 뽑았다는 뜻이므로 pickedNum을 출력한 뒤 return한다. return 하게되면 호출했던 함수로 돌아오고 pickednum.pop()과 visited에서 해당 인덱스를 다시 false로 바꿔준다.

파이썬 순열 코드 - Permutation by Python

numList = [1,2,3,4,5]
visited = [False] * len(numList)
pickednum = []

def permutation(cnt, depth) :

    if cnt == depth :
        print(pickednum)
        return
    for index in range(len(numList)) :
        if(visited[index] == False) :
            visited[index] = True
            pickednum.append(numList[index])
            permutation(cnt+1,depth)
            pickednum.pop()
            visited[index] = False

# 첫 번째 인자는 몇개 뽑았는지, 두 번째 인자는 몇개 뽑을 것인지.
permutation(0, 3)

코틀린 순열 코드 - Permutation by Kotlin

val numList = intArrayOf(1, 2, 3, 4, 5)
val pickednum = mutableListOf<Int>()
val visited = BooleanArray(numList.size, { false })

fun main() {
    // 첫 번째 인자는 몇개 뽑았는지, 두 번째 인자는 몇개 뽑을 것인지.
    permutation(0, 3)
}

fun permutation(cnt: Int, depth: Int) {
    if (cnt == depth) {
        pickednum.forEach {
            print("$it ")
        }
        println()
        return
    }
    for (index in 0 until numList.size) {
        if (visited[index] == false) {
            visited[index] = true
            pickednum.add(numList[index])
            permutation(cnt + 1, depth)
            pickednum.removeAt(pickednum.lastIndex)
            visited[index] = false
        }
    }
}

조합 구현

조합은 순열과 비슷하지만 순서를 고려하지 않는다. 따라서 인자로 cnt, depth, begtinwith를 받는다. beginwith 는 탐색을 시작할 인덱스이다. 순열과 마찬가지로 cnt == depth (현재 뽑은 개수 == 총 뽑을 개수)가 될 때까지 재귀 호출한다. 조합은 순서를 고려하지 않기 때문에 이미 뽑은 숫자라면 다시 확인할 필요가 없다. 따라서 별도의 방문처리를 하지 않고 beginwith로 탐색을 시작할 위치를 함수를 호출할 때 알려준다.

파이썬 조합 코드 - Combination by Python

numList = [1,2,3,4,5]
visited = [False] * len(numList)
pickednum = []

def combination(cnt, depth, beginWith) :
    if (cnt == depth) :
        print(pickednum)
        return
    for index in range(beginWith, len(numList)) :
        pickednum.append(numList[index])
        combination(cnt+1, depth, index+1)
        pickednum.pop()

# 첫 번째 인자는 몇개 뽑았는지, 두 번째 인자는 몇개 뽑을 것인지, 세 번째 인자는 탐색을 시작할 위치
combination(0,3,0)

코틀린 조합 코드 - Combination by Kotlin

val numList = intArrayOf(1, 2, 3, 4, 5)
val pickednum = mutableListOf<Int>()

fun main() {
    // 첫 번째 인자는 몇개 뽑았는지, 두 번째 인자는 몇개 뽑을 것인지, 세 번째 인자는 탐색을 시작할 위치
    combination(0, 3, 0)
}

fun combination(cnt: Int, depth: Int, beginWith: Int) {
    if (cnt == depth) {
        pickednum.forEach {
            print("$it ")
        }
        println()
        return
    }
    for (index in beginWith until numList.size) {
        pickednum.add(numList[index])
        combination(cnt + 1, depth, index + 1)
        pickednum.removeAt(pickednum.lastIndex)
    }
}