Last active
March 13, 2018 13:42
-
-
Save JadenGeller/5d49e46d4084fc493e72 to your computer and use it in GitHub Desktop.
Permutation Generator
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
struct PermutationSequenceGenerator<T> : GeneratorType { | |
var permutationSpaceGenerator: PermutationSpaceGenerator<Int> | |
let elements: [T] | |
init(elements: [T]) { | |
self.elements = elements | |
self.permutationSpaceGenerator = PermutationSpaceGenerator(objects: Array(indices(elements))) | |
} | |
mutating func next() -> SequenceOf<T>? { | |
if let indexPermuation = permutationSpaceGenerator.next() { | |
return SequenceOf({PermutationGenerator(elements: self.elements, indices: indexPermuation)}) | |
} | |
else { | |
return nil | |
} | |
} | |
} | |
struct PermutationSpaceGenerator<T> : GeneratorType { | |
let allObjects: [T] | |
var subGenerator: GeneratorOf<[T]>! | |
var index: Int = 0 | |
init(objects: [T]){ | |
self.allObjects = objects | |
self.subGenerator = nextSubgenerator(index++) | |
} | |
mutating func next() -> [T]? { | |
if let next = subGenerator.next() { | |
return next | |
} | |
else if index < allObjects.count { | |
subGenerator = nextSubgenerator(index++) | |
return next() | |
} | |
else { | |
return nil | |
} | |
} | |
private func nextSubgenerator(index: Int) -> GeneratorOf<[T]> { | |
if allObjects.count > 1 { | |
var copy = allObjects | |
let prepend = copy.removeAtIndex(index) | |
return GeneratorOf(PrependingGenerator(prepend: prepend, generator: GeneratorOf(PermutationSpaceGenerator(objects: copy)))) | |
} | |
else { | |
return GeneratorOf(GeneratorOfOne(allObjects)) | |
} | |
} | |
} | |
struct PrependingGenerator<T> : GeneratorType { | |
let prepend: T | |
var generator: GeneratorOf<[T]> | |
mutating func next() -> [T]? { | |
var copy = generator.next() | |
copy?.insert(prepend, atIndex: 0) | |
return copy | |
} | |
} |
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
// Example | |
var greetingPermutations = PermutationSequenceGenerator(elements: ["hi", "hey", "hello"]) | |
while let greetingSequence = greetingPermutations.next(){ | |
for greeting in greetingSequence { | |
print("\(greeting) ") | |
} | |
println() | |
} | |
/* | |
* hi hey hello | |
* hi hello hey | |
* hey hi hello | |
* hey hello hi | |
* hello hi hey | |
* hello hey hi | |
*/ | |
// Implementation |
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
var greetingPermutationsSpace = PermutationSpaceGenerator(objects: ["hi", "hey", "hello"]) | |
while let geetingArray = greetingPermutationsSpace.next() { | |
println(geetingArray) | |
} | |
/* | |
* [hi, hey, hello] | |
* [hi, hello, hey] | |
* [hey, hi, hello] | |
* [hey, hello, hi] | |
* [hello, hi, hey] | |
* [hello, hey, hi] | |
*/ | |
var numberSpace = PermutationSpaceGenerator(objects: Array(1...4)) | |
while let numberArray = numberSpace.next() { | |
println(numberArray) | |
} | |
/* | |
* [1, 2, 3, 4] | |
* [1, 2, 4, 3] | |
* [1, 3, 2, 4] | |
* [1, 3, 4, 2] | |
* [1, 4, 2, 3] | |
* [1, 4, 3, 2] | |
* [2, 1, 3, 4] | |
* [2, 1, 4, 3] | |
* [2, 3, 1, 4] | |
* [2, 3, 4, 1] | |
* [2, 4, 1, 3] | |
* [2, 4, 3, 1] | |
* [3, 1, 2, 4] | |
* [3, 1, 4, 2] | |
* [3, 2, 1, 4] | |
* [3, 2, 4, 1] | |
* [3, 4, 1, 2] | |
* [3, 4, 2, 1] | |
* [4, 1, 2, 3] | |
* [4, 1, 3, 2] | |
* [4, 2, 1, 3] | |
* [4, 2, 3, 1] | |
* [4, 3, 1, 2] | |
* [4, 3, 2, 1] | |
*/ |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment