Struct KarmarkarKarp 

pub struct KarmarkarKarp {
    pub part_count: usize,
}

Karmarkar-Karp algorithm

Also called the Largest Differencing Method.

Similar to the greedy number partitioning algorithm, but instead of puting the highest weight into the lowest part, it puts the two highest weights in two different parts and keeps their difference.

Example

use coupe::Partition as _;

let weights = [3, 5, 3, 9];
let mut partition = [0; 4];

coupe::KarmarkarKarp { part_count: 3 }
    .partition(&mut partition, weights)
    .unwrap();

Reference

Karmarkar, Narenda and Karp, Richard M., 1983. The differencing method of set partitioning. Technical report, Berkeley, CA, USA.

Fields

part_count: usize

Trait Implementations

impl<W> Partition<W> for KarmarkarKarp

where W: IntoIterator, W::IntoIter: ExactSizeIterator, W::Item: KkWeight,

type Metadata = ()

Diagnostic data returned for a specific run of the algorithm.

type Error = Error

Error details, should the algorithm fail to run.

fn partition( &mut self, part_ids: &mut [usize], weights: W, ) -> Result<Self::Metadata, Self::Error>

Partition the given data and output the part ID of each element in part_ids.