chicken_turtle_util.algorithms

Various algorithms, e.g. multi_way_partitioning to greedily divide weighted items equally across bins.

multi_way_partitioning	Greedily divide weighted items equally across bins (multi-way partition problem)
spread_points_in_hypercube	Place points in a unit hypercube such that the minimum distance between points is approximately maximal.
toset_from_tosets	Create totally ordered set (toset) from tosets.

chicken_turtle_util.algorithms.multi_way_partitioning(items, bin_count)

Greedily divide weighted items equally across bins (multi-way partition problem)

This approximately minimises the difference between the largest and smallest sum of weights in a bin.

Parameters:

items : iterable((item :: any)

Weighted items

bin_count : int

Number of bins

Returns:

bins : bag(bin :: frozenbag(item :: any))

Bins with the items

References

[R4]	http://stackoverflow.com/a/6855546/1031434 describes the greedy algorithm

[R5]	http://ijcai.org/Proceedings/09/Papers/096.pdf defines the problem and describes algorithms

chicken_turtle_util.algorithms.spread_points_in_hypercube(point_count, dimension_count)

Place points in a unit hypercube such that the minimum distance between points is approximately maximal.

Euclidean distance is used.

Note

Current implementation simply puts the points in a hypergrid

Parameters:

point_count : int

Number of points to pick

dimension_count : int

Number of dimensions of the hypercube

Returns:

np.array(shape=(point_count, dimension_count))

Points spread approximately optimally across the hypercube.

Raises:

ValueError

When point_count < 0 or dimension_count < 1

Notes

The exact solution to this problem is known for only a few n.

References

[R6]	http://stackoverflow.com/a/2723764/1031434

chicken_turtle_util.algorithms.toset_from_tosets(*tosets)

Create totally ordered set (toset) from tosets.

These tosets, when merged, form a partially ordered set. The linear extension of this poset, a toset, is returned.

Warning

untested

Parameters:

tosets : iterable of setlist

Tosets to merge

Returns:

setlist

Totally ordered set

Raises:

ValueError

If the tosets (derived from the lists) contradict each other. E.g. [a, b] and [b, c, a] contradict each other.