Question about the KK algorithm output

[csmoe]

I got partition = [1, 2, 1, 0] after running the example in the kk doc https://lihpc-computational-geometry.github.io/coupe/coupe/struct.KarmarkarKarp.html#example, how does the numbers inside partition array relate to weights? Seems not the index of them.

[hhirtz]

Hi, partition[i] is the part of weights[i]. So with weights = [3, 5, 3, 9] that'd mean you have 3 parts, [9], [3, 3] and [5].

Hope that helps!

[csmoe]

Thanks for your kind reply, does it means partition = vec![ part.len(),.. ]?
More specifically, how can I get the partition result like:

let partition = [1usize, 2, 1, 0];
let weights = [3u64, 5, 3, 9];

fn partition_result(partition: &[usize], weights: &[u64]) -> Vec<Vec<u64>> {
  // ?
}

assert_eq!(vec![vec![9], vec![3, 3],vec![5]], partition_result(&partition, &weight));

[hhirtz]

It would look like this:

partition
    .iter()
    .zip(weights)
    .fold(vec![Vec::new(); 3], |acc, (&part, &weight)| {
        acc[part].push(weight);
        acc
    })