derangements

Generate derangements and variants in line with permutations in the itertools crate.

Get started

To get started:

• add derangements = 0.2.0 to your Cargo.toml
• add use derangements::derangements or one of the other functions to your Rust file
• output will be an iterable containing all derangements or (restricted) permutations

For more options, including more derangement variants and also other restricted permutations, see https://docs.rs/derangements

Methodology

There will be three main algorithms included in this package:

• a distinct permutations algorithm, based on this paper by Aaron Williams as suggested in PR 1003 in the rust-itertools project.
• a fast permutations algorithm - this still needs to be implemented
  • currently the distinct permutations algorithm is (ab)used for this, which is already faster than itertools::permutations (but with different requirements)
• a range-specific derangements generator, custom developed for this and other contributions by me
  • this used to be faster than the non-range-specific derangements generator before switching to the faster algorithm above to generate the permutations; but now the range-specific generator can be best used to more concisely generate derangements based on a range
  • I hope that converting this into an Iterator generator will also improve its speed

Note that (except the above-mentioned range-specific derangements) the derangements in this package are generated by filtering permutations to keep only the items that meet the restriction.

Future plans

Ideally the following would be added or explored:

• generalize inputs to allow for non-usize inputs (even non-integer) -> partially now done, can be negative
  • note: if this is needed for generating a k-length derangement, you can always map the non-integers to values outside 0..k and then map them back afterwards
• add random_derangement, at least for the default derangement types
• add examples/use cases of how/when to use this
• Explore creating an iterable for a faster derangement_range as well (if that is faster) - or otherwise just remove
• Consider introducing derangements_by_value here as well to keep naming consistent with Python's more_itertools
  • I will only consider this after a release of more_itertools with that naming in it as well
• Investigate alternative method to speed up when we don't want to drop duplicates
  • Intuitively, it should be faster to not account for it, with the right algorithm
  • Alternative, we could "repeat" items that need to be duplicated by calculating a "duplication" metric
• Make usize parameter any generic integer (or at least any unsigned integer)

If you have more ideas, let me know!

License

Licensed under either of Apache License, Version 2.0 or MIT license at your option.

Unless you explicitly state otherwise, any contribution intentionally submitted for inclusion in this crate by you, as defined in the Apache-2.0 license, shall be dual licensed as above, without any additional terms or conditions.