LHCO_reader

partition_problem

Introduction

Functions to solve the partition problem and non-standard partition problems.

We implement greedy, brute force and Karmarkar-Karp algorithms.

In the standard problem, we attempt to divide a set into two subsets, such that the difference between the sums of the subsets is minimised.

In the non-standard problem, the function to be minimised is arbitrary - it isn’t simply the difference between the sums of the two subsets.

partition_problem.CKK(list_, branch=False)

Preliminary aspects of complete Karmarkar-Karp algorithm, including checking whether to prune a branch.

Parameters:

• list (list) – List of elements
• branch (bool) – Whether a branch in a CKK search

Returns:

Result of branch() possibly halted

Return type:

float

Example:

>>> CKK(example_list)
0.13999999999998414
>>> CKK(example_list)
0.13999999999998414

partition_problem.KK(list_)

Divide elements into two approximately equal subsets with the Karmarkar-Karp algorithm also known as the Least Difference Method.

Warning

This algorithm may not return the optimal solution.

Parameters:list (list) – A list of positive numbers Returns:Minimum difference between sums of subsets Return type:float Example:

>>> KK(example_list)
0.14000000000001078

partition_problem.brute(list_)

Divide elements into two approximately equal subsets with a brute force algorithm.

Warning

This is complexity \(\mathcal{O}(2^n)\) - this could be very slow.

Parameters:list (list) – A list of positive numbers Returns:Minimum difference between sums of subsets Return type:float

>>> brute(example_list)
0.13999999999998636

partition_problem.greedy(list_)

Divide elements into two approximately equal subsets with a “greedy” algorithm. Order the elements then assign elements to the smallest subset.

Warning

A “greedy” algorithm may not return the optimal solution.

Parameters:list (list) – A list of positive numbers Returns:Minimum difference between sums of subsets Return type:float Example:

>>> greedy(example_list)
8.46

partition_problem.non_standard_brute(list_, measure_fn)

Solve a non-standard partition problem by brute force.

Parameters:

• list (list) – List of elements of any type
• measure_fn (function) – Function for measure to be minimised for two sub-sums

Returns:

Sums of two subsets, chosen such that measure minimised

Return type:

list

Example:

>>> non_standard_brute(example_list, example_fn)
[194.45, 194.31]

partition_problem.non_standard_greedy(list_, measure_fn)

Solve a non-standard partition problem with a “greedy” algorithm.

Warning

A “greedy” algorithm may not return the optimal solution.

Parameters:

• list (list) – List of elements of any type
• measure_fn (function) – Function for measure to be minimised for two sub-sums

Returns:

Sums of two subsets, chosen such that measure minimised

Return type:

list

Example:

>>> non_standard_greedy(example_list, example_fn)
[195.31, 193.45000000000002]

partition_problem.non_standard_solver(list_, measure_fn, algorithm='non_standard_brute')

Wrapper for possible non-standard partition solving algorithms.

Parameters:

• algorithm (string) – Choice of algorithm
• measure_fn (function) – Function for measure to be minimised for two sub-sums

Returns:

Sums of two subsets, chosen such that measure minimised

Return type:

list

Example:

>>> non_standard_solver(example_list, example_fn,
...                     algorithm="non_standard_brute")
[194.45, 194.31]

partition_problem.powerset(list_, half=False)

The set of all subsets, i.e. the powerset, of a set. See itertools and wiki.

Warning

A powerset of a set includes the empty subset and the set itself.

Parameters:

• list (list) – A list for which a powerset is desired
• half (bool) – Build half the powerset - the missing half is contained in the complement

Returns:

Powerset of original list

Return type:

itertools.chain

Example:

>>> list(powerset([1, 2, 3]))
[(), (1,), (2,), (3,), (1, 2), (1, 3), (2, 3), (1, 2, 3)]
>>> list(powerset([1, 2, 3], half=True))
[(), (1,), (2,), (3,)]

partition_problem.prune(CKK_branch)

Decorator that prunes search tree in the complete Karmarkar-Karp algorithm by stopping branches that cannot yield an improvement.

Parameters:CKK – A call for a branch in CKK algorithm

partition_problem.solver(list_, algorithm='CKK')

Wrapper for possible partition solving algorithms.

Parameters:algorithm (string) – Choice of algorithm Returns:Minimum difference between sums of subsets Return type:float Example:

>>> solver(example_list, algorithm="brute")
0.13999999999998636

kinetic_test