Aufteilung

Implements the Karmarkar-Karp differencing algorithm in Typescript. It can be used to evenly partition a list into two lists, while keeping their difference minimal.

Also offers a greedy partitioning algorithm, mostly for comparison.

Install

npm install aufteilung

Usage

const KK = require('karmarkar-karp');

Both functions accept an array (of integers or objects). If an object array is passed, you have to specify the property key in the object to use for comparison.

KK.greedy({ value, key}): Implements the greedy algorithm

KK.LDM({ value, key}): Implements the least differencing method

Returns an object:

var result = { 
   A: [],
   Asum: 0,
   B: [],
   Bsum: 0,
   distance: 0
};

where A and B are the two partitioned arrays from the input array, as well as metadata on the partitioning (A's sum, B's sum, and the final distance between sets).

See src/kk.test.ts for examples.