스위프트 Combination

 

조합은 집합에서 서로 다른 n개의 원소 중에서 순서에 상관없이 r개를 선택하는 것입니다.
이전에도 정리를 한 번 한 적이 있지만(https://hyerios.tistory.com/172) 조합은 순서에 상관없이 뽑기만 하면 됩니다. 
combinations(ofCount: ) 메서드를 사용하면은 컬렉션 요소의 모든 조합의 시퀀스를 반환하며,
각 조합은 원래 컬렉션의 순서대로 표시됩니다.

combinations가 만들어지기 전에는 대부분 아래와 같이 구현했습니다.

//5개 중에 2개를 뽑는 모든 경우의 수
func combos<T>(elements: ArraySlice<T>, k: Int) -> [[T]] {
    if k == 0 {
        return [[]]
    }

    guard let first = elements.first else {
        return []
    }

    let head = [first]
    let subcombos = combos(elements: elements, k: k - 1)
    var ret = subcombos.map { head + $0 }
    ret += combos(elements: elements.dropFirst(), k: k)

    return ret
}

func combos<T>(elements: Array<T>, k: Int) -> [[T]] {
    return combos(elements: ArraySlice(elements), k: k)
}

let numbers = [1,2,3,4,5]
print(combos(elements:numbers,k:2))

/*
returns
[[1, 1], [1, 2], [1, 3], [1, 4], [1, 5], 
[2, 2], [2, 3], [2, 4], [2, 5], [3, 3], 
[3, 4], [3, 5], [4, 4], [4, 5], [5, 5]]
*/

 

(위 조합 공식과 비교하면서 봐도 좋을 것 같습니다.)

하지만 combinations가 생성된 이후는 아래와 같이 사용하면 됩니다.

let numbers = [10, 20, 30, 40]
for combo in numbers.combinations(ofCount: 2) {
    print(combo)
}
// [10, 20]
// [10, 30]
// [10, 40]
// [20, 30]
// [20, 40]
// [30, 40]

요소의 조합은 컬렉션의 원래 순서에 맞게 증가하는 순으로 표시됩니다.

let numbers2 = [20, 10, 10]
for combo in numbers2.combinations(ofCount: 2) {
    print(combo)
}
// [20, 10]
// [20, 10]
// [10, 10]

2...3과 같이 범위가 주어지면 combinations(ofCount: )메서드는 지정된 크기(2...3)에 대해서 시퀀스가 증가하는 순서로 조합들을 반환합니다.

let numbers = [10, 20, 30, 40]
for combo in numbers.combinations(ofCount: 2...3) {
    print(combo)
}
// [10, 20]
// [10, 30]
// [10, 40]
// [20, 30]
// [20, 40]
// [30, 40]
// [10, 20, 30]
// [10, 20, 40]
// [10, 30, 40]
// [20, 30, 40]

 

시간 복잡도
combinations(ofCount: )를 호출하면 컬렉션의 수만큼 접근합니다.
컬렉션에 랜덤 접근이면 O(1)이고 아니면 O(n)의 시간 복잡도를 가집니다.
combinations 이터레이터를 생성하고 각각을 Combinations.Iterator.next()를 통해서 호출하려면 O(n)의 시간 복잡도를 가집니다.

resource:
https://github.com/apple/swift-algorithms/blob/main/Guides/Combinations.md
https://www.raywenderlich.com/18517868-swift-algorithms-getting-started#toc-anchor-002