cmd_queue.util.util_algo module

cmd_queue.util.util_algo.balanced_number_partitioning(items, num_parts)

Greedy approximation to multiway number partitioning

Uses Greedy number partitioning method to minimize the size of the largest partition.

Parameters:

• items (np.ndarray) – list of numbers (i.e. weights) to split between paritions.

• num_parts (int) – number of partitions

Returns:

A list for each parition that contains the index of the items assigned to it.

Return type:

List[np.ndarray]

References

https://en.wikipedia.org/wiki/Multiway_number_partitioning https://en.wikipedia.org/wiki/Balanced_number_partitioning

Example

>>> from cmd_queue.util.util_algo import balanced_number_partitioning
>>> items = np.array([1, 3, 29, 22, 4, 5, 9])
>>> num_parts = 3
>>> bin_assignments = balanced_number_partitioning(items, num_parts)
>>> # xdoctest: +REQUIRES(module:kwarray)
>>> import kwarray
>>> groups = kwarray.apply_grouping(items, bin_assignments)
>>> bin_weights = [g.sum() for g in groups]