Fixes #285.

This implementation is based on the Python implementation specified in the issue. There are quite a few points which should be considered.

## Method name, *k*-less form

The adaptor function is called `permutations`

, for user familiarity. However, since the size of the output can be specified, a more mathematically accurate name would probably be `k_permutations`

. Perhaps two adaptor functions would be better: `.k_permutations(k: usize)`

and `.permutations()`

(which just sets `k = vals.len()`

)?

## Item value ordering/distinctness

Input items are not inspected in any way; they are treated purely by their initial index. This means that:

- Permutations are yielded in lexicographical order of the index, not by any
`PartialOrd`

implementation of the items.
- Identical items will not be detected, and will result in some identical permutations.

**1** can be achieved by the user by collecting-and-sorting their input.

**2** is a little trickier, but can be achieved by filtering the output. However, I think there is a more efficient algorithm to avoid duplicated. Maybe we should provide this option?

## Permutations from source buffer/indices

In addition to the iterator adaptor, I've added `Permutations::from_vals`

, to create directly from a `Vec`

or a slice. This saves some cloning compared to using `source.[into_]iter().permutations(k)`

.

There is also `Permutations::new(n, k)`

, which is functionally equivalent to `(0..n).permutations(k)`

, but a little faster (about 0.6x the run time).

But perhaps you would consider these unnecessary additions to the API?

`PermutationSource`

trait

These different implementations (from `Vec`

/slice/just indices) are achieved with the trait `PermutationSource`

. It's visible to the user to implement for other structures if they wish, but this is probably of limited value. There's not much harm in allowing the user to access it, but again, maybe it's just API bloat. (or a future breaking change when it's removed/changed...)

On the other hand, perhaps there are other places in the library which could benefit from taking a source generically? Any adaptor where input elements are used more than once will need to store them, and it might be more efficient to allow users to supply the memory directly. This could be done in another PR.

For completeness, I also made full implementations of the three variations, without the trait, for benchmarking. The pure-indices implementation is about 10% slower using the trait, but `Vec`

s and slices are unaffected (or even a little faster...).

`Combinations`

changes

I've made small changes to the `Combinations`

documentation to match `Permutations`

- most significantly, replacing the letter `n`

with `k`

. I've also changed all uses of the variable `n`

to `k`

in the implementation... but maybe this is considered commit noise :)

There are some other potential changes which would bring `Combinations`

and `Permutations`

more in line with one another.

As mentioned above, `Combinations`

might benefit from using a `_____Source`

trait, to allow direct memory buffers.

My `Permutations`

implementations doesn't make use of `LazyBuffer`

. Perhaps the buffer is useful for iterators which never complete, and have a very small `k`

value. Has any benchmarking been done?

Either way, it makes sense for both adaptors to either use or not use `LazyBuffer`

. Maybe it could be integrated into the `_______Source`

trait if it's useful?

Let me know what you think when you have the chance. (Sorry for submitting two reasonably big PRs at once. I hope you get a chance to go through it all eventually!)

waiting-on-author