Skip to content

The Karmarkar-Karp differncing algorithm in Typescript

License

Notifications You must be signed in to change notification settings

boredland/aufteilung

 
 

Repository files navigation

Aufteilung

npm npm npm bundle size (version) GitHub test Coverage Status

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.

About

The Karmarkar-Karp differncing algorithm in Typescript

Topics

Resources

License

Stars

Watchers

Forks

Sponsor this project

 

Languages

  • TypeScript 99.5%
  • JavaScript 0.5%