Skip to content

Instantly share code, notes, and snippets.

@jperras
Last active December 16, 2017 13:17
Show Gist options
  • Save jperras/64c210b6db8a4806506c to your computer and use it in GitHub Desktop.
Save jperras/64c210b6db8a4806506c to your computer and use it in GitHub Desktop.
Approximate Subset Sum
# -*- coding: utf-8 -*-
import itertools
import operator
def trim(data, delta):
"""Trims elements within `delta` of other elements in the list."""
output = []
last = 0
for element in data:
if element['value'] > last * (1 + delta):
output.append(element)
last = element['value']
return output
def merge_lists(m, n):
"""
Merges two lists into one.
We do *not* remove duplicates, since we'd like to see all possible
item combinations for the given approximate subset sum instead of simply
confirming that there exists a subset that satisfies the given conditions.
"""
merged = itertools.chain(m, n)
return sorted(merged, key=operator.itemgetter('value'))
def approximate_subset_sum(data, target, epsilon):
"""
Calculates the approximate subset sum total in addition to the items
that were used to construct the subset sum.
Modified to track the elements that make up the partial sums to then
identify which subset items were chosen for the solution.
"""
acc = [{'value': 0, 'partials': [0]}]
count = len(data)
# Prep data by turning it into a list of hashes
data = [{'value': d, 'partials': [d]} for d in data]
for key, element in enumerate(data, start=1):
augmented_list = [{
'value': element['value'] + a['value'],
'partials': a['partials'] + [element['value']]
} for a in acc]
acc = merge_lists(acc, augmented_list)
acc = trim(acc, delta=float(epsilon) / (2 * count))
acc = [val for val in acc if val['value'] <= target]
return acc[-1]
if __name__ == "__main__":
data = [650, 1200, 1350, 450, 2875, 1625, 1500, 1875]
target = 3450
epsilon = 0.2
print "input: {data}; target: {target}; epsilon: {epsilon}".format(
data=data, target=target, epsilon=epsilon)
print approximate_subset_sum(data, target, epsilon=epsilon)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment