### 3 releases

0.1.2 | Dec 16, 2019 |
---|---|

0.1.1 | Dec 15, 2019 |

0.1.0 | Dec 15, 2019 |

#**1137** in Algorithms

**7,547** downloads per month

Used in **6** crates
(3 directly)

**Apache-2.0**

18KB

164 lines

# permutation-iterator

A Rust library for iterating over random permutations without fully materializing them into memory.

lets you iterate over a random permutation, for example the values `permutation-iterator`

in a
random order. It does so in constant space; it does not fully instantiate the values in memory then shuffle them.`[``0``,` `1``,` `2``,` `3``,` `4``,` `5``]`

## Usage

Add this to your

:`Cargo.toml`

`[``dependencies``]`
`permutation_iterator ``=` `"`0.1.2`"`

## Example

### Random, single integer range

Here is how to iterate over a random permutation of integers in the range

, i.e. `[``0``,` max)

inclusive to `0`

exclusive. Every time you run this you will get a different permutation.`max`

`use` `permutation_iterator``::`Permutor`;`
`fn` `main``(``)`` ``{`
`let` max `=` `10``;`
`let` permutor `=` `Permutor``::`new`(`max`)``;`
`for` permuted `in` permutor `{`
`println!``(``"``{}``"``,` permuted`)``;`
`}`
`}`

### Deterministic, single integer range

You can also pass in a

in order to iterate over a deterministically random permutation. Every time you run this
you will get the same permutation:`key`

`use` `permutation_iterator``::`Permutor`;`
`fn` `main``(``)`` ``{`
`let` max `=` `10``;`
`let` key`:` `[``u8``;` `32``]` `=` `[``0xBA``;` `32``]``;`
`let` permutor `=` `Permutor``::`new_with_slice_key`(`max`,` key`)``;`
`for` permuted `in` permutor `{`
`println!``(``"``{}``"``,` permuted`)``;`
`}`
`}`

### Random, pair of integers

If you have e.g. two vectors of integers and you want to iterate over a random permutation of pairs from these lists you can use:

`use` `permutation_iterator``::`RandomPairPermutor`;`
`fn` `main``(``)`` ``{`
`let` xs `=` `[``1``,` `2``,` `3``]``;`
`let` ys `=` `[``4``,` `5``,` `6``,` `7``,` `8``]``;`
`let` permutor `=` `RandomPairPermutor``::`new`(`xs`.``len``(``)` `as` `u32``,` ys`.``len``(``)` `as` `u32``)``;`
`for` `(`i`,` j`)` `in` permutor `{`
`println!``(``"`(`{}`, `{}`)`"``,` xs`[`i `as` `usize``]``,` ys`[`j `as` `usize``]``)``;`
`}`
`}`

## Implementation details

One way of generating a random permutation is to shuffle a list. For example, given input integers

,
one can shuffle it to e.g. `[``0``,` `1``,` `2``,` `3``,` `4``,` `5``]`

. Each input element maps to one and only one output element, and
vice versa (each output element maps to one and only one input element). As you consume the shuffled list from e.g.
left to right you're consuming this random permutation.`[``5``,` `3``,` `2``,` `0``,` `1``,` `4``]`

Shuffling is

time using the Fisher-Yates algorithm, however it is also `O (n)`

`O``(`n`)`

space. We need a copy of the
elements in-memory in order to shuffle them. This is inconvenient if the input range is large, or if the environment
you're running on is memory-constrained.Cryptography offers an alternative. Symmetric encryption boils down to mapping a given input to one and only one output,
where the mapping is varied by a single secret key, and vice-versa (each output element maps to one and only one input
element). If this **bijective** mapping did not exist we wouldn't be reliably able to retrieve the original input. One
specific kind of symmetric encryption uses a **block** cipher (operating on n-bits at a time) implemented using a
**Feistel network**.

A Feistel network is an extraordinary construct that allows you to use a simple, relatively weak **non-invertible**
function over and over again and become a complicated, relatively strong **invertible permutation**. Hence in
constant time we can *encrypt* inputs as a way of iterating over random permutations. We can similarly *decrypt*
the output as a way of *resuming* permutations.

Consider the example of a bank that is trying to generate unique credit card numbers. Actual credit card numbers need to be stored very securely and we would rather not have to look them in order to find the next available number. By storing just a key and the last credit card number generated we can securely and efficiently continue iterating over the random permutation of all credit card numbers, without risking repeats.

## License

is distributed under the terms of the Apache License (Version 2.0). See LICENSE for
details.`permutation-iterator`

#### Dependencies

~660KB

~12K SLoC