Last active
August 20, 2020 02:50
-
-
Save psksvp/8fb5c6fbfd6a2207e95638db95f55ae1 to your computer and use it in GitHub Desktop.
swift array extension that deals with generating combinations and permutations
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| /** | |
| translate from Scala by psksvp@gmail.com | |
| http://vkostyukov.ru/posts/combinatorial-algorithms-in-scala/ | |
| */ | |
| extension Collection | |
| { | |
| func combinations(_ n: Int) -> [[Element]] | |
| { | |
| guard self.count > 0 else {return [[Element]]()} | |
| guard n <= self.count else {return [[Element]]()} | |
| if 1 == n | |
| { | |
| return self.map {[$0]} | |
| } | |
| else | |
| { | |
| let head = self.first! // at this point head should be valid | |
| let tail = Array(self.dropFirst()) | |
| let car = tail.combinations(n - 1).map {[head] + $0} // build first comb | |
| let cdr = tail.combinations(n) // do the rest | |
| return car + cdr | |
| } | |
| } | |
| func variations(_ n:Int) -> [[Element]] | |
| { | |
| func mixone(_ i: Int, _ x: Element, _ ll: [Element]) -> [Element] | |
| { | |
| return Array( ll[0 ..< i] + ([x] + ll[i ..< ll.count]) ) | |
| } | |
| func foldone(_ x: Element, _ ll: [Element]) -> [[Element]] | |
| { | |
| let r:[[Element]] = (1 ... ll.count).reduce([[x] + ll]) | |
| { | |
| a, i in | |
| [mixone(i, x, ll)] + a | |
| } | |
| return r | |
| } | |
| func mixmany(_ x: Element, _ ll: [[Element]]) -> [[Element]] | |
| { | |
| guard ll.count > 0 else {return [[Element]]()} | |
| let head = ll.first! | |
| let tail = Array<Array<Element>>(ll.dropFirst()) | |
| return foldone(x, head) + mixmany(x, tail) | |
| } | |
| guard self.count > 0 else {return [[Element]]()} | |
| guard n <= self.count else {return [[Element]]()} | |
| if 1 == n | |
| { | |
| return self.map {[$0]} | |
| } | |
| else | |
| { | |
| let head = self.first! // at this point head should be valid | |
| let tail = Array(self.dropFirst()) | |
| return mixmany(head, tail.variations(n - 1)) + tail.variations(n) | |
| } | |
| } | |
| var permutations: [[Element]] | |
| { | |
| variations(self.count) | |
| } | |
| } | |
| print([1, 2, 3, 4].combinations(2)) | |
| print([1, 2, 3, 4].variations(2)) | |
| print([1, 2, 3, 4].permutations) | |
| print(Array("ABCD").permutations) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment