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
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162

//! Efficiently enumerate integer partitions.
//!
//! This is an implementation of a method described by
//! [Jerome Kelleher](http://jeromekelleher.net/generating-integer-partitions.html),
//! which takes a constant amount of time for each partition.

#![deny(missing_docs)]

/// Iterates over the partitions of a given positive integer.
pub struct Partitions {
    a: Vec<usize>,
    k: usize,
    y: usize,
    next: State,
}

enum State {
    A,
    B { x: usize, l: usize },
}

impl Partitions {
    /// Makes a new iterator.
    ///
    /// # Panics
    ///
    /// Panics if `n < 1`.
    #[inline]
    pub fn new(n: usize) -> Partitions {
        assert!(n >= 1);

        Partitions {
            a: vec![0; n + 1],
            k: 1,
            y: n - 1,
            next: State::A,
        }
    }

    /// Advances the iterator and returns the next partition.
    #[inline]
    pub fn next(&mut self) -> Option<&[usize]> {
        let Partitions {
            ref mut a,
            ref mut k,
            ref mut y,
            ref mut next
        } = *self;

        match *next {
            State::A => {
                if *k == 0 {
                    None
                } else {
                    *k -= 1;
                    let x = a[*k] + 1;

                    while 2 * x <= *y {
                        a[*k] = x;
                        *y -= x;
                        *k += 1;
                    }

                    let l = *k + 1;

                    if x <= *y {
                        a[*k] = x;
                        a[l] = *y;
                        *next = State::B { x, l };
                        Some(&a[..*k + 2])
                    } else {
                        a[*k] = x + *y;
                        *y = x + *y - 1;
                        Some(&a[..*k + 1])
                    }
                }
            },
            State::B { mut x, l } => {
                x += 1;
                *y -= 1;

                if x <= *y {
                    a[*k] = x;
                    a[l] = *y;
                    *next = State::B { x, l };
                    Some(&a[..*k + 2])
                } else {
                    a[*k] = x + *y;
                    *y = x + *y - 1;
                    *next = State::A;
                    Some(&a[..*k + 1])
                }
            },
        }
    }

    /// Makes a new iterator, trying to avoid allocations.
    ///
    /// Any vector can be passed to this function, since its contents
    /// will be cleared and it will be filled with zeroes, but note
    /// that the vector will still reallocate if its capacity is less
    /// than `n + 1`.
    ///
    /// # Panics
    ///
    /// Panics if `n < 1`.
    #[inline]
    pub fn recycle(n: usize, mut vec: Vec<usize>) -> Partitions {
        assert!(n >= 1);

        vec.clear();
        vec.reserve(n + 1);
        for _ in 0..(n + 1) {
            vec.push(0);
        }

        Partitions {
            a: vec![0; n + 1],
            k: 1,
            y: n - 1,
            next: State::A,
        }
    }

    /// Destroys the iterator and returns a vector for further use.
    ///
    /// You only need to call this function if you want to reuse the
    /// vector for something else. Its contents will be in an undefined
    /// state, and so cannot be relied upon.
    #[inline]
    pub fn end(self) -> Vec<usize> {
        self.a
    }
}

#[test]
fn oeis() {
    //! Tests the first few entries of A000041.

    let tests: &[usize] = &[
        1, 2, 3, 5, 7, 11, 15, 22,
        30, 42, 56, 77, 101, 135, 176, 231,
        297, 385, 490, 627, 792, 1002, 1255, 1575,
        1958, 2436, 3010, 3718, 4565, 5604, 6842, 8349,
        10143, 12310, 14883, 17977, 21637, 26015, 31185, 37338,
        44583, 53174, 63261, 75175, 89134, 105558, 124754, 147273,
        173525,
    ];

    for (i, &n) in tests.iter().enumerate() {
        let mut p = Partitions::new(i + 1);
        let mut c = 0;

        while let Some(x) = p.next() {
            let sum: usize = x.iter().cloned().sum();
            assert_eq!(sum, i + 1);
            c += 1;
        }

        assert_eq!(c, n);
    }
}