순열 (Permutation) & 조합 (Combination)

순열이란?

---

수학에서 순열(Permutation) 또는 치환은 순서가 부여된 임의의 집합을 다른 순서로 뒤섞는 연산이다. 즉, 순열은 정의역과 공역이 같은 일대일 대응이다. n개의 원소의 순서를 뒤섞는 순열의 개수는 n의 계승 n!와 같다. 즉, n 이하의 양의 정수들을 곱한 값이다. 쉽게 말하자면 서로 다른 n개중에서 r개를 선택하는 경우의 수이다.

 

1. Swap 을 이용한 순열

첫번째는 swap 함수를 만들어서 배열들의 값을 직접 바꾸는 방법이다.

배열의 첫 값부터 순서대로 하나씩 바꾸며 모든 값을 한번씩 swap 한다.

depth 를 기준 인덱스로 하여 depth 보다 인덱스가 작은 값들은 그대로 고정하고

depth 보다 인덱스가 큰 값들만 가지고 다시 swap 을 진행한다.

Swap & Recursion

하지만 이 방식은 사전 순으로 경우의 수를 찾지 않기 때문에 순열들의 순서가 보장되지 않는다.

val num = intArrayof(1, 2, 3)
val output = mutableListOf<Int>()
val visited = BooleanArray(num.size)

fun main() {
	permutation(3, 3)
}

fun permutation(cnt : Int, depth : Int) {
    if (depth == cnt) {
        print(num, cnt)
        return
    }
    
    for (i in depth until num.size) {
        swap(depth, i)
        permutation(cnt, depth + 1)
        swap(depth, i)
    }
}
 
fun swap(depth : Int, i : Int) {
    var temp = num[depth]
    num[depth] = num[i]
    num[i] = temp
}

 

1 2 3
1 3 2
2 1 3
2 3 1
3 2 1
3 1 2

2. Visited 배열을 이용한 순열

두번째로는 visited 배열을 이용하는 방법이다.

1번과 달리 사전식으로 순열을 구현할 수 있다.

Visited & Recursion

Visited 배열을 이용한 순열은 visited 라는 BooleanArray를 이용해서 해당 인덱스를 방문했는지를 묻게된다.

DFS를 돌면서 모든 인덱스를 방문하고 output에 결과값을 넣게된다.

val num = intArrayof(1, 2, 3)
val output = mutableListOf<Int>()
val visited = BooleanArray(num.size)

fun main() {
	permutation(3, 3)
}

fun permutation(cnt: Int, depth: Int) {
	if (cnt == depth) {
    	print("$output")
        return
    }
    for (i in 0 until num.size) {
    	if(visited[i] == false) {
			visited[i] = true
            output.add(num[i])
            permutation(cnt + 1, depth)
            add.removeAt(num.lastIndex)
            visited[i] = false
        }
    }
}

 

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

조합이란?

---

집합에서 서로 다른 n개의 값 중에서 r 개의 숫자를 순서를 고려하지 않고 나열한 경우의 수이다.

순열과는 순서를 고려하지 않는다는 점이 다르다고 할 수 있다.

 

ex) 1, 2, 3

1개 선택 - (1), (2), (3)

2개 선택 - (1, 2), (1, 3), (2, 3)

3개 선택 - (1, 2, 3)

 

fun main() {
    var num = listOf(1, 2, 3)
    for(i in 1 .. num.size) {
        val answer = mutableListOf<List<Int>>()
        println("================$i 개====================")
        combination(answer, num, Array<Boolean>(num.size) { false }, 0,  i)
        answer.forEach { println(it) }
    }

}

fun combination(answer: MutableList<List<T>>, el: List<T>, ck: Array<Boolean>, start: Int, target: Int) {
    if(target == 0) {
        answer.addAll( listOf(el.filterIndexed { index, t -> ck[index] }) )
    } else {
        for(i in start until el.size) {
            ck[i] = true
            combination(answer, el, ck, i + 1, target - 1)
            ck[i] = false
        }
    }
}

Reference

https://rutgo-letsgo.tistory.com/221

Permutation Algorithm(순열 알고리즘) & Combination Algorithm(조합 알고리즘)

https://bcp0109.tistory.com/14

순열 Permutation (Java)

https://medium.com/depayse/kotlin-%EC%88%9C%EC%97%B4-permutation-36e85898896c

[Kotlin] 순열(Permutation)

https://notepad96.tistory.com/111