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)[source]¶ 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 haltedReturn type: float
Example: >>> CKK(example_list) 0.13999999999998414 >>> CKK(example_list) 0.13999999999998414
-
partition_problem.
KK
(list_)[source]¶ 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_)[source]¶ 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_)[source]¶ 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)[source]¶ 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)[source]¶ 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')[source]¶ 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)[source]¶ 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)[source]¶ 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')[source]¶ 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