Permutations


(Daryle Walker) #1

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


(Erica Sadun) #2

If they were writing Swift from scratch today, it would not be on my personal list of types Swift should add in the standard library.

Permuting a collection's indices isn't that typical a task, and when it does apply I think there are better ways to do this than a dedicated stdlib type. It's easy to add shuffling and take by-n or take m copies with just a few lines of code that don't generalize well. There's also GameplayKit support for Cocoa/touch devs that work well w/ the new indexing model.

I know there's also been interest in striding over collections, not sure where that stands right now.

-- E

···

On Jun 17, 2016, at 10:42 AM, Daryle Walker via swift-evolution <swift-evolution@swift.org> wrote:

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:

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.)