# How about detection and iteration of permutations **URL:** \ **Category:** Pitches\ **Created:** [December 6, 2019, 8:37am UTC](https://forums.swift.org/t/how-about-detection-and-iteration-of-permutations/31404 "2019-12-06T08:37:24Z")\ **Posts on this page:** 6\ **Page:** 1
**Author:** ![CTMacUser](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/ctmacuser/32/1802_2.png) [@CTMacUser](https://forums.swift.org/u/CTMacUser)\ **Post date:** [December 6, 2019, 8:37am UTC](https://forums.swift.org/t/how-about-detection-and-iteration-of-permutations/31404/1 "2019-12-06T08:37:24Z")
Continuing on the C++ Standard Library tour.... I have [a new Gist](https://gist.github.com/CTMacUser/363d04c127b738cd00aa05115795b0a3) with copies of the various permutation functions. I hope I have all the complexity time (and/or space) requirements right. ## IsPermutation.swift The main method, `Sequence.isPermutation(of: by:)`, is an adaptation of the C++ standard function [`std::is_permutation`](https://en.cppreference.com/w/cpp/algorithm/is_permutation), including the quadratic runtime. There is a compact `isPermutation(of:)` method for `Equatable` elements. There is also a version for `Hashable` elements, but that version works much better, approaching linear time, based on some blogs I read. Since a lot of types can be hashed, this version of the method probably will be used the most. (Then again, that will end up surprising some users when their usually linear calls to `is_permutation` suddenly be quadratic because their latest element type is not `Hashable`.) ## AdjacentPermutation.swift The main methods, `MutableCollection.permuteForward(by:)` and `permuteBackward(by:)`, are adaptations of [`std::next_permutation`](https://en.cppreference.com/w/cpp/algorithm/next_permutation) and [`std::prev_permutation`](https://en.cppreference.com/w/cpp/algorithm/prev_permutation). The receiving collection must allow bi-directional traversal. There are compact variants for `Comparable` elements. It is likely that a user wants to visit every potential permutation. If so, instead of stepping through with the methods above, just make a custom `Sequence` that does it all at once. Said sequence can be created with the `MutableCollection.permutations(by:)` method. The collection still needs to be bi-directional, and the method has a variant for `Comparable` elements. The hardest part of making the `DistinctPermutationSequence` was figuring out how many elements there will be. (It isn't `count`! if there are duplicates, and the `permute...` methods skip duplicates.) ## Copy.swift This file contains the `MutableCollection.copy(from:)` method, which transfers elements from another collection, but overwrites instead of inserts. Right here, it's listed as `internal`, because it's off-brand from the point of this library. However, it does match the C++ [`std::copy`](https://en.cppreference.com/w/cpp/algorithm/copy) function; and `std::copy_if`, [`std::copy_n`](https://en.cppreference.com/w/cpp/algorithm/copy_n), [`std::fill`](https://en.cppreference.com/w/cpp/algorithm/fill), and [`std::fill_n`](https://en.cppreference.com/w/cpp/algorithm/fill_n) with proper Swift chaining; so it could be moved to being `public` in a shared or separate proposal. ## Integer.swift Contains `internal` methods to compute the binomial and multinomial coefficients, needed to calculate permutation (with repeats) counts. It actually isn't easy to compute these values; humans can eyeball where to cancel denominator factors, but computers can't do that without either a table of prime factorizations or multiple greatest-common-divisor passes. I doubt we should add these to the public math library. (Maybe to our auxiliary numeric library?) ~~**To-do:** actually upload the files.~~ **Edit:** added the link (up top). * * * ## 2019-Dec-8 Update I updated the Gist to revision 2. It makes the permutation sequence type a lazy sequence, and moves its accessors to `LazySequenceProtocol`. I added an eager variant, including one for `Comparable` elements. I did make a permutation count method, but kept it private for now. ---
**Author:** ![cukr](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/cukr/32/889_2.png) [@cukr](https://forums.swift.org/u/cukr)\ **Post date:** [December 6, 2019, 10:09am UTC](https://forums.swift.org/t/how-about-detection-and-iteration-of-permutations/31404/3 "2019-12-06T10:09:20Z")
> [@CTMacUser](#): > > It is likely that a user wants to visit every potential permutation. If so, instead of stepping through with the methods above, just make a custom `Sequence` that does it all at once. Said sequence can be created with the `MutableCollection.permutations(by:)` method. Would this sequence be eager, or lazy? If it's eager, then is there a reason for it to be a custom sequence, instead of an array? And if it's lazy, shouldn't it be made with `foo.lazy.permutations(by: <)` like with `map`, `filter`, etc, and the eager version returning an Array? ---
**Author:** ![CTMacUser](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/ctmacuser/32/1802_2.png) [@CTMacUser](https://forums.swift.org/u/CTMacUser)\ **Post date:** [December 6, 2019, 6:51pm UTC](https://forums.swift.org/t/how-about-detection-and-iteration-of-permutations/31404/4 "2019-12-06T18:51:23Z")
Right now, it's lazy. I could make an eager version. Note that my trial collection: ``` [1, 2, 4, 8, 1, 3, 9, 27, 1, 4, 16, 64, 1, 5, 25, 125] ``` has 16 elements, with 1 repeated 4 times and 4 repeated twice. Naïvely, that's 16!, or nearly 21 trillion, permutations. The permutation sequence filters out repeats, so it's only nearly a half-trillion permutations. That's why I didn't even think about an array-returning version at first. Maybe I'll add a checking function to help. ---
**Author:** ![CTMacUser](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/ctmacuser/32/1802_2.png) [@CTMacUser](https://forums.swift.org/u/CTMacUser)\ **Post date:** [December 9, 2019, 2:28am UTC](https://forums.swift.org/t/how-about-detection-and-iteration-of-permutations/31404/5 "2019-12-09T02:28:06Z")
I updated the Gist to revision 2. There is now an eager variant. ---
**Author:** ![allevato](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/allevato/32/385_2.png) [@allevato](https://forums.swift.org/u/allevato)\ **Post date:** [December 9, 2019, 3:41am UTC](https://forums.swift.org/t/how-about-detection-and-iteration-of-permutations/31404/6 "2019-12-09T03:41:58Z")
Not only should permutation generation be lazy by default, but an eager variant shouldn't be provided at all—such an algorithm has factorial time complexity and returns a collection of factorial size, which would be a huge footgun for all but the tiniest data sets. If a user asks for an array of permutations, there are two answers: 1. You don't want that. Do you _really_ want that? 2. Fine, then pass the lazy sequence to the `Array(Sequence)` initializer, which acknowledges the potential harm of that operation. In-place permuting and lazy sequence generation is fine, but if this is a pitch for eventual addition to the standard library, the stdlib shouldn't be offering users a convenient factorial operation. ---
**Author:** ![CTMacUser](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/ctmacuser/32/1802_2.png) [@CTMacUser](https://forums.swift.org/u/CTMacUser)\ **Post date:** [December 9, 2019, 9:33am UTC](https://forums.swift.org/t/how-about-detection-and-iteration-of-permutations/31404/7 "2019-12-09T09:33:57Z")
That’s the way I originally had it, but the new eager variant allows a throwing predicate. I was uncomfortable moving my first version to the `lazy` interface, because I’m not sure that the `BidirectionalCollection` and/or `MutableCollection` will always carry over to the lazy wrapper. (It does if the main type passes itself as `Elements`.) Maybe use `lazilyGeneratedPermutations` as the method name? Or just accept `permutations` as a slightly inaccurate name (but mention the laziness in the docs).