본 블로그는 개인적인 공부 및 저장의 용도 작성됐습니다.

Swift는 cpp등에서 지원해주는 순열 조합 라이브러리가 존재하지 않는다.
왜 안 만들어주는거지?
따라서 코딩테스트에 응시할 때 직접 구현해야한다.

Algorithms 라는 Library에서 Permutation 과 Combination을 지원해준다. (OCTOBER 7, 2020)
다만 아직 코딩테스트와 같은 환경에서는 적용이 불가능하다.

https://swift.org/blog/swift-algorithms/

Factorial

func factorial(_ n: Int) -> Int {
  var n = n
  var result = 1
  while n > 1 {
    result *= n
    n -= 1
  }
  return result
}

factorial(5)   // returns 120

Combination

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

// 모든 조합 구하기
func allCombos<T>(elements: Array<T>) -> [[T]] {
    var answer: [[T]] = []
    for i in 1...elements.count {
        answer.append(contentsOf: combos(elements: elements, k: i))
    }
    return answer
}

let numbers = [1,2,3]
print(allCombos(elements: numbers))

// prints [[1], [2], [3], [1, 1], [1, 2], [1, 3], [2, 2], [2, 3], [3, 3]]

Unique Combination

출처 : https://stackoverflow.com/questions/50264717/get-all-possible-combination-of-items-in-array-without-duplicate-groups-in-swift/50265976

extension Array {
    var combinationsWithoutRepetition: [[Element]] {
        guard !isEmpty else { return [[]] }
        return Array(self[1...]).combinationsWithoutRepetition.flatMap { [$0, [self[0]] + $0] }
    }
    
    var combinationsWithoutRepetitionRemoved: [[Element]] {
        var result = self.combinationsWithoutRepetition
        result.removeFirst()
        return result
    }
}

//combinationsWithoutRepetition는 [] 빈 배열까지 들어감~
print([1, 2, 3, 4].combinationsWithoutRepetitionRemoved)
// prints [[1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3], [4], [1, 4], [2, 4], [1, 2, 4], [3, 4], [1, 3, 4], [2, 3, 4], [1, 2, 3, 4]]

Number of Combination

//combination numbers
func combinations(_ n: Int, choose k: Int) -> Int {
  return permutations(n, k) / factorial(k)
}

combinations(28, choose: 5)    // prints 98280

Permutation

//가능한 모든 경우의 수
func permuteWirth<T>(_ a: [T], _ n: Int) {
    if n == 0 {
        print(a)   // display the current permutation
    } else {
        var a = a
        permuteWirth(a, n - 1)
        for i in 0..<n {
            a.swapAt(i, n)
            permuteWirth(a, n - 1)
            a.swapAt(i, n)
        }
    }
}

let letters = ["a", "b", "c"]
permuteWirth(letters, letters.count - 1)

/* returns
["a", "b", "c"]
["b", "a", "c"]
["c", "b", "a"]
["b", "c", "a"]
["a", "c", "b"]
["c", "a", "b"]
*/

출처
https://github.com/raywenderlich/swift-algorithm-club/tree/master/Combinatorics