permute 0.2.1

Generate permutations of vectors and slices in a memory-efficient and deterministic manner, using Heap's algorithm.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88

// SPDX-FileCopyrightText: 2020 Leonora Tindall <nora@nora.codes>
//
// SPDX-License-Identifier: AGPL-3.0-or-later WITH LicenseRef-AppStore

//! Combining ATCI and permute() to create efficient permutations
use crate::arbitrary_tandem_control_iter::ArbitraryTandemControlIterator;
use crate::permutations::permute;

/// Produce an iterator over iterators, each one of which yields one permutation of the
/// provided slice. No copying of elements of the slice occurs.
///
/// # Complexity
///
/// This function is `O(n!)` in both space and time, though with a lower constant than
/// `permute` for collections with large elements, since it does not copy elements of the
/// give slice, only indices.
///
/// # Determinism
///
/// The order of the permutations is deterministic and can be found ahead of time by
/// consulting the OEIS sequence for reverse colexicographic ordering, using
/// the appropriate elements of [A280318](https://oeis.org/A280318) as indices into
/// [A055089](https://oeis.org/A055089).
///
/// # Example
///
/// For instance, printing all the permutations of the sequence
/// `["red", "green", "blue"]`:
/// ```
/// # use permute::permutations_of;
/// for permutation in permutations_of(&["red", "green", "blue"]) {
///     for element in permutation {
///         print!("{}, ", element);
///     }
///     println!("");
/// }
/// ```
///
/// Based on the ordering provided by Heap's algorithm, it's guaranteed that this
/// program will produce:
///
/// ```text
/// red, green, blue,
/// green, red, blue,
/// blue, red, green,
/// red, blue, green,
/// green, blue, red,
/// blue, green, red,
/// ```
pub fn permutations_of<T: Clone + Sized>(
    items: &[T],
) -> impl Iterator<Item = impl Iterator<Item = &T>> {
    let indices: Vec<usize> = (0..items.len()).collect();
    let permutations: Vec<Vec<usize>> = permute(indices);

    let mut atcis: Vec<_> = Vec::with_capacity(permutations.len());
    for permutation in permutations.into_iter() {
        atcis.push(ArbitraryTandemControlIterator::new(
            items,
            permutation.into_iter(),
        ));
    }
    atcis.into_iter()
}

#[test]
fn strings_nocopy() {
    let data = vec![
        String::from("red"),
        String::from("green"),
        String::from("blue"),
    ];
    let mut permutations: Vec<Vec<&String>> = Vec::new();
    for permutation_iter in permutations_of(&data) {
        permutations.push(permutation_iter.collect());
    }
    assert_eq!(
        vec![
            vec!["red", "green", "blue"],
            vec!["green", "red", "blue"],
            vec!["blue", "red", "green"],
            vec!["red", "blue", "green"],
            vec!["green", "blue", "red"],
            vec!["blue", "green", "red"]
        ],
        permutations
    );
}