6
\$\begingroup\$

I've tried to implement integer partition algorithm as described in blogpost below (author implemented it in Python): Generating integer partitions

I'm still trying to learn best practices in producing clean code. I would also be thankful for any performance tips.

My code:

struct NumberPartition {
    a: Vec<i32>,
    k: i32,
    y: i32,
    x: i32,
    l: i32,
}

impl NumberPartition {
    pub fn new(n: i32) -> Self {
        NumberPartition {
            a: vec![0; (n + 1) as usize],
            k: 1,
            y: n - 1,
            x: 0,
            l: 0
        }
    }


    fn partition(&mut self) -> Option<Vec<Vec<i32>>> {
        let mut buf: Vec<Vec<i32>> = Vec::new();
        while self.k != 0 {
            self.x = self.a[(self.k - 1) as usize] + 1;
            self.k -= 1;
            while 2 * self.x <= self.y {
                self.a[self.k as usize] = self.x;
                self.y -= self.x;
                self.k += 1;
            }
            self.l = self.k + 1;
            while self.x <= self.y {
                self.a[self.k as usize] = self.x;
                self.a[self.l as usize] = self.y;
                buf.push(self.a[..(self.k + 2) as usize].to_vec());
                self.x += 1;
                self.y -= 1;
            }
            self.a[self.k as usize] = self.x + self.y;
            self.y = self.x + self.y - 1;
            buf.push(self.a[..(self.k + 1) as usize].to_vec());
        }
        Some(buf)
    }
}


fn main() {
    let b = NumberPartition::new(6).partition();
    for i in b.iter() {
        println!("{:?}", i);
    }
}
\$\endgroup\$
  • 1
    \$\begingroup\$ a double yield is painful to implement as an iterator: play.integer32.com/…. \$\endgroup\$ – Stargateur Mar 27 '19 at 9:12
  • \$\begingroup\$ @Stargateur yes indeed, i tried it and had to think of something else. Your code is great! Thank you! \$\endgroup\$ – Kamil Niski Mar 27 '19 at 9:34
  • 1
    \$\begingroup\$ Various small changes on that iterator: play.integer32.com/… \$\endgroup\$ – JayDepp Mar 27 '19 at 19:03
  • 1
    \$\begingroup\$ Since partitions only deal with positive integers, you should probably use an unsigned type like u32 or u64, and also add a check against NumberPartiton::new(0). \$\endgroup\$ – JayDepp Mar 27 '19 at 19:06
  • 1
    \$\begingroup\$ I tried to simplify it further: play.integer32.com/… \$\endgroup\$ – Tim Vermeulen Apr 2 '19 at 5:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.