[swift-evolution] Permutations

[Daryle Walker]

I’ve seen the WWDC 2016 Keynote and State of the Platforms videos.  I haven’t seen any others so I don’t spoil myself before typing my ideas down.  Apologies if this has already been covered.

I saw that the “PermutationGenerator” type is being retired in Swift 3.  It inspired me to see how I can implement such a type:

//=====
/// Permutations generator, adapted from a Java class that mentioned its source as <http://www.cut-the-knot.org/Curriculum/Combinatorics/JohnsonTrotter.shtml>.  Inspired by checking that Swift 3 will not have/retain such a type.
struct PermutationsGenerator<Index: ForwardIndexType>: GeneratorType {

    /// postconditions: The first `self.next` returns an array of the indices in order.
    init(indices: Range<Index>)

    mutating func next() -> [Index]?

}
//=====

Use like:

//=====
func doSomething<C: CollectionType>(collection: C) {
    var g = PermutationsGenerator(collection.indices)
    while let p = g.next() {
        doSomethingToo(p.map { collection[$0] })
    }
}
//=====

So the first call to “next” returns “Array(indices)” and subsequent calls return scrambled versions of that array.  There will be “factorial(indices.count)” versions returned.  (For an empty range or one with one valid element, there will be only 0! == 1! == 1 valid return.)

Then I looked further.  This is NOT what the existing “PermutationGenerator” does.  In fact, the type is being retired for this very reason.  The type actually returns a subset of collection, possibly in a scrambled order (i.e. a permutation).  Some questions:

1. Is the functionality of the existing “PermutationGenerator” being moved to another type?
2. Would my type be suitable to add to the standard library?  Would the name need to be changed?  (The name is appropriate, but it’s just one letter different from a depreciated type.)

— 
Daryle Walker
Mac, Internet, and Video Game Junkie
darylew AT mac DOT com 

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-evolution/attachments/20160617/9a29ba71/attachment.html>