Special subset sums: optimum
Problem 103
Let S(A) represent the sum of elements in set A of size n. We shall call it a special sum set if for any two non-empty disjoint subsets, B and C, the following properties are true:
If S(A) is minimised for a given n, we shall call it an optimum special sum set. The first five optimum special sum sets are given below.
n = 1: {1}
n = 2: {1, 2}
n = 3: {2, 3, 4}
n = 4: {3, 5, 6, 7}
n = 5: {6, 9, 11, 12, 13}
n = 2: {1, 2}
n = 3: {2, 3, 4}
n = 4: {3, 5, 6, 7}
n = 5: {6, 9, 11, 12, 13}
It seems that for a given optimum set, A = {a1, a2, ... , an}, the next optimum set is of the form B = {b, a1+b, a2+b, ... ,an+b}, where b is the "middle" element on the previous row.
By applying this "rule" we would expect the optimum set for n = 6 to be A = {11, 17, 20, 22, 23, 24}, with S(A) = 117. However, this is not the optimum set, as we have merely applied an algorithm to provide a near optimum set. The optimum set for n = 6 is A = {11, 18, 19, 20, 22, 25}, with S(A) = 115 and corresponding set string: 111819202225.
Given that A is an optimum special sum set for n = 7, find its set string.
NOTE: This problem is related to Problem 105 and Problem 106.
def make_subset_sums(a):
b = [0] * 2**len(a)
for i in range(1, len(b)):
b[i] = make_subset_sum(a, i)
return b
def make_subset_sum(a, m):
s = 0
for i in range(len(a)):
if m & 1 == 1:
s += a[i]
# we just check whether each number should be in the given set
# by checking the binary representation of the index
m >>= 1
return s
def disjoint(n, m):
# Checks if the subsets are disjoint
return n & m == 0
def verify_rule_1(a, dim, t):
for i in range(len(a)):
k = i
while k != -1:
k += 1
if k >= len(a):
break
try:
k = a.index(a[i], k)
except:
k = -1
if k != -1 and disjoint(i, k):
return False
return True
def verify_rule_2(a):
# Assume that the array is sorted
sum1 = a[0]
sum2 = 0
for i in range(len(a) / 2):
sum1 += a[i + 1]
sum2 += a[len(a) - i - 1]
if sum1 <= sum2:
return False
return True
def update_pertubation_vector(a, min_check, max_check):
for i in range(len(a) - 1, -1, -1):
if a[i] != max_check:
for j in range(i + 1, len(a)):
a[j] = min_check
a[i] += 1
return a
return a
def run(base=[20, 31, 38, 39, 40, 42, 45], return_set_string=True):
# https://www.mathblog.dk/project-euler-103-special-subset-sum/
# base vector
a = base
check_range = [-5, 5]
result = ''
t = [0] * len(a)
dim = len(a)
# sum vector
s = []
# pertubation vector
# http://w.astro.berkeley.edu/~mwhite/polar/node5.html
# https://en.wikipedia.org/wiki/Perturbation_theory
c = [check_range[0]] * len(a)
tsum = 0
tmin = float('inf')
for i in range((check_range[1] - check_range[0] + 1)**dim):
for j in range(len(a)):
t[j] = a[j] + c[j]
tsum = sum(t)
if tsum <= tmin:
t.sort()
if verify_rule_2(t):
s = make_subset_sums(t)
if verify_rule_1(s, dim, t):
tmin = tsum
if return_set_string:
result = ''.join([str(x) for x in t])
else:
result = [x for x in t]
c = update_pertubation_vector(c, check_range[0], check_range[1])
return result
"""
n = 1: {1}
n = 2: {1, 2}
n = 3: {2, 3, 4}
n = 4: {3, 5, 6, 7}
n = 5: {6, 9, 11, 12, 13}
n = 6: {11, 18, 19, 20, 22, 25}
11, 17, 20, 22, 23, 24
"""
if __name__ == '__main__':
a = [1, 2]
for x in range(6):
t = run(a, return_set_string=False)
print len(t), t
m = a[len(a) / 2]
a = [m] + [m + x for x in a]