Permutation Generator

Permutation Sequence Generator.swift

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
    }
}

Example PermutationSequenceGenerator.swift

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

Example PermutationSpaceGenerator.swift

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