Continuing on the C++ Standard Library tour....
I have a new Gist with copies of the various permutation functions.
I hope I have all the complexity time (and/or space) requirements right.
The main method,
Sequence.isPermutation(of: by:), is an adaptation of the C++ standard function
std::is_permutation, including the quadratic runtime. There is a compact
isPermutation(of:) method for
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
The main methods,
permuteBackward(by:), are adaptations of
std::prev_permutation. The receiving collection must allow bi-directional traversal. There are compact variants for
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.)
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 function; and
std::fill_n with proper Swift chaining; so it could be moved to being
public in a shared or separate proposal.
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).
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.