Permutation

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

List의 원소들을 나열하는 함수들

n개의 목록중 1개 선택

fun perm(depth:Int, n:Int) {
    if (depth == n) { // 선택이 완료 된 경우
        for (i in 0 until n) {
            print("${ans[i]} ") 
        }
        println()
        return
    }

    for (i in 0 until n) { // 전체 목록중에서 선택
        if (!visit[i]) { // 중복 없이 선택
            ans[depth] = data[i]
            visit[i] = true
            perm(depth + 1, n)
            visit[i] = false
        }
    }
}

n개 중에 r개 선택하여 나열

fun perm(depth:Int, n:Int, r:Int) {
    if (depth == r) {
        for (i in 0 until r) {
            print("${ans[i]} ")
        }
        println()
        return
    }

    for (i in 0 until n) {
        if (!visit[i]) {
            ans[depth] = data[i]
            visit[i] = true
            perm(depth + 1, n, r)
            visit[i] = false
        }
    }
}

부분 집합

원소들에서 순서 없이 선택 할 수 있는 경우의 수

재귀

val isSelected = BooleanArray(numbs.size) { false }

fun subset(depth:Int) {
    if (depth == numbs.size) {
        val subset = numbs.filterIndexed { index, _ ->
            isSelected[index] // 선택한 원소만 있는 리스트 생성
        }.joinToString(" ")

        println(subset)
        return
    }

    isSelected[depth] = true
    subset(depth + 1)
    isSelected[depth] = false
    subset(depth + 1)
}

subset(0)

비트 마스킹 사용 부분집합

val numbs = readLine().split(" ").map { it.toInt() }

fun List<Int>.subset(): List<List<Int>> {
    val res = mutableListOf<List<Int>>()

    for (i in 0 until (1 shl numbs.size)) { // 모든 경우 탐색
        val list = mutableListOf<Int>()
        for (j in numbs.indices) {
            if (i and (1 shl j) != 0) { // 선택한 경우인지 확인
                list.add(this[j])
            }
        }

        res.add(list) // 선택이 완료된 결과물 저장
    }
    return res
}

val list = numbs.subset() // 모든 부분집합
println(list)

2진수를 0, 1 로 생각하는 아이디어를 이용하여, 비트연산을 이용하여 부분집합을 생성.

조합

유한 개의 원소에서 주어진 수만큼의 원소들을 고르는 방법

시작위치를 변경

    val selected = IntArray(m) { 0 }
    fun comb(count:Int, start:Int) {
        if (count == m) {
            val list = selected.toList()
            // do somgthing
            return
        }

        for (i in start .. numbs.lastIndex) { // start 이후부터 반복
            selected[count] = numbs[i]
            comb(count + 1, i + 1) // i번 이후부터 탐색 시작 하도록
        }
    }

기본적으로 순열에서 사용했던 구조에서 반복의 범위를 '0 ~ 마지막원소' 에서 '시작 ~ 마지막원소' 로 변경 조합에서는 순서정보가 없기 때문에 선택한 다음 원소 부터 탐색을 시작하면 조합을 만들수 있음.

부분집합에서 n개인 경우만 선택

val list = numbs.subset()
val comb = list.filter {
	it.size == n // size == n 인 부분집합만 선택
}

부분집합에서 n개를 선택한 경우만 골라낸 경우 조합과 동일함.