Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
Fixed solution in Uncategorized category for Loading Cargo by macfreek
#!/usr/bin/env python
# -*- coding: utf-8 -*-
"""
Generalised Partition Problem.
See http://en.wikipedia.org/wiki/Partition_problem
"""
def uniqueCombinations(items, n, max=None):
"""uniqueCombinations takes an unordered set of n distinct elements from the sequence.
combination without replacement
Example: Unique Combinations of 2 letters from 'ABCD':
AB AC AD BC BD CD
If max is specified, make sure that all items can be added, and the items are sorted.
"""
if n==0:
yield []
else:
for i in range(len(items)):
for cc in uniqueCombinations(items[i+1:],n-1):
if max and max < items[i] + sum(cc):
continue
yield [items[i]]+cc
def uniqueSubsets(items, max):
"""uniqueCombinations takes a subset of n distinct elements from the sequence.
Example: Unique Subsets from 'ABCD':
0 A B C D AB AC AD BC BD CD ABC ABD ACD BCD ABCD
"""
items = sorted(items)
for n in range(0,len(items)+1):
for cc in uniqueCombinations(items, n, max):
# assert sum(cc) <= max
yield cc
def checkio(stones):
'''
minimal possible weight difference between stone piles
Solution is brute force, as a greedy algorithm may fail.
See http://www.americanscientist.org/issues/pub/2002/3/the-easiest-hard-problem
Most "good" solution use the itertools.combinations iterator to find all
subsets. This works, but isn't optimal. Instead, this solution uses a custom
iterator that only yields subsets whose sum is less or equal than half the total.
'''
# print (stones)
total = sum(stones)
best = total
for subset in uniqueSubsets(stones, total//2):
diff = abs(total - 2*sum(subset))
# print subset, diff
if diff < best:
best = diff
if best == 0:
break
return best
#These "asserts" using only for self-checking and not necessary for auto-testing
if __name__ == '__main__':
assert checkio([10, 10]) == 0, "First, with equal weights"
assert checkio([10]) == 10, "Second, with a single stone"
assert checkio([5, 8, 13, 27, 14]) == 3, "3rd example"
assert checkio([5, 5, 6, 5]) == 1, "4th example"
assert checkio([12, 30, 30, 32, 42, 49]) == 9, "5th example"
assert checkio([1, 1, 1, 3]) == 0, "Six, don't forget - you can hold different quantity of parts"
assert checkio([771, 121, 281, 854, 885, 734, 486, 1003, 83, 62]) == 0, "Seventh, a notoriously hard example"
assert checkio([10,1,6,18,47,36,38]) == 4
May 2, 2013
Comments: