Swift) Factorial, Combination, Permutation
본 블로그는 개인적인 공부 및 저장의 용도 작성됐습니다.
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
func factorial(_ n: Int) -> Int {
var n = n
var result = 1
while n > 1 {
result *= n
n -= 1
}
return result
}
factorial(5) // returns 120
//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
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"]
*/
//combination numbers
func combinations(_ n: Int, choose k: Int) -> Int {
return permutations(n, k) / factorial(k)
}
combinations(28, choose: 5) // prints 98280
//가능한 모든 경우의 수
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
Author And Source
이 문제에 관하여(Swift) Factorial, Combination, Permutation), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@hansangjin96/Swift-Factorial-Combination-Permutation저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)