알고리즘 - 조합(Conbinations) 구현[Swift]

조합에는 "순서"가 없다.

그저 몇 개를 뽑을 것인지를 사용할 때 조합을 사용한다. 순서는 상관없고 몇개를 다양하게 뽑을지..

순서가 없다는건 1, 2, 3과 3, 2, 1을 같은 숫자로 본다는 것이다.

 

조합의 개수를 구하는 공식은 다음과 같다

 

n = 자료의 총 개수

r = 뽑아서 사용할 자료의 개수

 

만약 5C3일 경우

 

이 되며  5! = 120        (n-r)2! = 2          3! = 6이 되어 120/12 -> 10이 된다. 

 

[1, 2, 3, 4, 5] 5개의 숫자에서 3개를 뽑는 경우의 수는 실제로

1, 2, 3       2, 3, 4

1, 2, 4       2, 3, 5

1, 2, 5       2, 4, 5                   => 총 10개이다

1, 3, 4       3, 4, 5

1, 3, 5 

1, 4, 5   

 

실제로 횟수를 구하는 공식이 아닌 리스트를 구하는 공식을 작성해본다.

 

let list = [1, 2, 3, 4, 5]

var arr = [Int]()
           //start는 index를, target은 목표 개수를 의미
func Combination(_ start: Int,_ target: Int){
	//arr의 count가 target과 같으면? 여기선 요소를 3개 선택했으면?
    if arr.count == target{
        print(arr)
        return
    }else{
    //i는 start +1에서 list의 개수까지 순회한다
        for i in start+1..<list.count{
            arr.append(list[i])
            Combination(i, 3)
            arr.removeLast()
        }
        return
    }
}

Combination(-1, 3)

//[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]

 

해당 알고리즘을 통하여 해결한 문제

https://clamp-coding.tistory.com/entry/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EC%82%BC%EC%B4%9D%EC%82%ACSwift%EC%A1%B0%ED%95%A9

프로그래머스 - 삼총사[Swift][조합]

https://clamp-coding.tistory.com/entry/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EC%86%8C%EC%88%98%EB%A7%8C%EB%93%A4%EA%B8%B0Swift%EC%A1%B0%ED%95%A9-%EC%97%90%EB%9D%BC%EC%8A%A4%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%B2%B4