Source code for tryalgo.subsetsum_divide
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""\
Subsetsum by splitting
christoph dürr et jill-jênn vie - 2014-2019
"""
# snip{
[docs]
def part_sum(x_table, i=0):
"""All subsetsums from x_table[i:]
:param x_table: table of values
:param int i: index_table defining suffix_table of x_table to be considered
:iterates: over all values, in arbitrary order
:complexity: :math:`O(2^{len(x_table)-i})`
"""
if i == len(x_table):
yield 0
else:
for s_idx in part_sum(x_table, i + 1):
yield s_idx
yield s_idx + x_table[i]
[docs]
def subset_sum(x_table, r_target):
"""Subsetsum by splitting
:param x_table: table of values
:param r_target: target value
:returns bool: if there is a subsequence of x_table with total sum r_target
:complexity: :math:`O(n^{\\lceil n/2 \\rceil})`
"""
k = len(x_table) // 2 # divide input
y_value = list(part_sum(x_table[:k]))
z_value = [r_target - v for v in part_sum(x_table[k:])]
y_value.sort() # test of intersection between y_value and z_value
z_value.sort()
i = 0
j = 0
while i < len(y_value) and j < len(z_value):
if y_value[i] == z_value[j]:
return True
if y_value[i] < z_value[j]: # increment index of smallest element
i += 1
else:
j += 1
return False
# snip}
# snip{ subset_sum2
[docs]
def part_sum2(x_table):
"""All subsetsums from a list x
:param x_table: list of values
:complexity: :math:`O(2^{len(x)})`
"""
answer = set([0]) # 0 = value of empty set
for xi in x_table:
answer |= set(value + xi for value in answer)
return answer
[docs]
def subset_sum2(x_table, r_target):
"""Subsetsum by splitting
:param x_table: table of values
:param r_target: target value
:returns bool: if there is a subsequence of x_table with total sum r_target
:complexity: :math:`O(n^{\\lceil n/2 \\rceil})`
"""
k = len(x_table) // 2 # divide input
y_set = part_sum2(x_table[:k])
z_set = set(r_target - value for value in part_sum2(x_table[k:]))
return len(y_set & z_set) > 0 # test intersection
# snip}