integer_partitions/
lib.rs

1//! Efficiently enumerate integer partitions.
2//!
3//! This is an implementation of a method described by
4//! [Jerome Kelleher](http://jeromekelleher.net/generating-integer-partitions.html),
5//! which takes a constant amount of time for each partition.
6
7#![deny(missing_docs)]
8
9/// Iterates over the partitions of a given positive integer.
10pub struct Partitions {
11    a: Vec<usize>,
12    k: usize,
13    y: usize,
14    next: State,
15}
16
17enum State {
18    A,
19    B { x: usize, l: usize },
20}
21
22impl Partitions {
23    /// Makes a new iterator.
24    #[inline]
25    pub fn new(n: usize) -> Partitions {
26        Partitions {
27            a: vec![0; n + 1],
28            k: if n == 0 { 0 } else { 1 },
29            y: if n == 0 { 0 } else { n - 1 },
30            next: State::A,
31        }
32    }
33
34    /// Advances the iterator and returns the next partition.
35    #[inline]
36    pub fn next(&mut self) -> Option<&[usize]> {
37        let Partitions {
38            ref mut a,
39            ref mut k,
40            ref mut y,
41            ref mut next
42        } = *self;
43
44        match *next {
45            State::A => {
46                if *k == 0 {
47                    if a.len() == 1 {
48                        a.pop();
49                        Some(&[])
50                    } else {
51                        None
52                    }
53                } else {
54                    *k -= 1;
55                    let x = a[*k] + 1;
56
57                    while 2 * x <= *y {
58                        a[*k] = x;
59                        *y -= x;
60                        *k += 1;
61                    }
62
63                    let l = *k + 1;
64
65                    if x <= *y {
66                        a[*k] = x;
67                        a[l] = *y;
68                        *next = State::B { x, l };
69                        Some(&a[..*k + 2])
70                    } else {
71                        a[*k] = x + *y;
72                        *y = x + *y - 1;
73                        Some(&a[..*k + 1])
74                    }
75                }
76            },
77            State::B { mut x, l } => {
78                x += 1;
79                *y -= 1;
80
81                if x <= *y {
82                    a[*k] = x;
83                    a[l] = *y;
84                    *next = State::B { x, l };
85                    Some(&a[..*k + 2])
86                } else {
87                    a[*k] = x + *y;
88                    *y = x + *y - 1;
89                    *next = State::A;
90                    Some(&a[..*k + 1])
91                }
92            },
93        }
94    }
95
96    /// Makes a new iterator, trying to avoid allocations.
97    ///
98    /// Any vector can be passed to this function, since its contents
99    /// will be cleared and it will be filled with zeroes, but note
100    /// that the vector will still reallocate if its capacity is less
101    /// than `n + 1`.
102    #[inline]
103    pub fn recycle(n: usize, mut vec: Vec<usize>) -> Partitions {
104        vec.clear();
105        vec.reserve(n + 1);
106        for _ in 0..(n + 1) {
107            vec.push(0);
108        }
109
110        Partitions {
111            a: vec,
112            k: if n == 0 { 0 } else { 1 },
113            y: if n == 0 { 0 } else { n - 1 },
114            next: State::A,
115        }
116    }
117
118    /// Destroys the iterator and returns a vector for further use.
119    ///
120    /// You only need to call this function if you want to reuse the
121    /// vector for something else. Its contents will be in an undefined
122    /// state, and so cannot be relied upon.
123    #[inline]
124    pub fn end(self) -> Vec<usize> {
125        self.a
126    }
127}
128
129#[test]
130fn oeis() {
131    //! Tests the first few entries of A000041.
132
133    let tests: &[usize] = &[
134        1, 1, 2, 3, 5, 7, 11, 15, 22,
135        30, 42, 56, 77, 101, 135, 176, 231,
136        297, 385, 490, 627, 792, 1002, 1255, 1575,
137        1958, 2436, 3010, 3718, 4565, 5604, 6842, 8349,
138        10143, 12310, 14883, 17977, 21637, 26015, 31185, 37338,
139        44583, 53174, 63261, 75175, 89134, 105558, 124754, 147273,
140        173525,
141    ];
142
143    for (i, &n) in tests.iter().enumerate() {
144        let mut p = Partitions::new(i);
145        let mut c = 0;
146
147        while let Some(x) = p.next() {
148            let sum: usize = x.iter().cloned().sum();
149            assert_eq!(sum, i);
150            c += 1;
151        }
152
153        assert_eq!(c, n);
154    }
155}
integer_partitions/lib.rs

integer_partitions/
lib.rs
