Swift) Factorial, Combination, Permutation

hansangjin96·2020년 9월 15일
0

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

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

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

profile
iOS Developer

0개의 댓글