16
\$\begingroup\$

Given an array of \$n\$ positive integers we will say its self-sum order is the number of ways to add elements from it to make \$n\$. We will count ways as distinct up to associativity. So \$1+(2+3)\$ and \$(1+2)+3\$ are not counted as separate ways to make 6, but \$2+4\$ and \$4+2\$ are counted as separate. Two sums are the same if they are the same when written without parentheses.

You may not reuse elements of the array in your sum, but the same number can appear multiple times in the array. So if the array is [1,1,2,3], then \$1+1+2\$ should be counted, but \$2+2\$ should not.

As an example here's one array with all the distinct sums listed out:

[1,1,2,3]
1+3
3+1
1+1+2
1+2+1
2+1+1

It's self sum order is 5.

Task

Given a non-negative integer, \$n\$, as input, output the array of length \$n\$ with the highest self-sum order. Since there will be multiple arrays (often just permutations of the same array) with the highest self-sum order, you may output any one of them.

Your answer will be scored by it's big \$O\$ asymptotic time complexity in terms of \$n\$, with faster algorithms being better.

Example outputs:

You do not need to output the order it is included for your convenience.

0  -> 1    []
1  -> 1    [1]
2  -> 1    [1,1]
3  -> 3    [1,2,3]
4  -> 5    [1,1,2,3]
5  -> 9    [1,1,1,2,3]
6  -> 17   [1,1,2,2,3,4]
7  -> 37   [1,1,1,2,2,3,4]
8  -> 73   [1,1,1,1,2,2,3,4]
9  -> 138  [1,1,1,1,2,2,3,4,5]
10 -> 279  [1,1,1,1,2,2,2,3,4,5]
11 -> 578  [1,1,1,1,2,2,2,3,3,4,5]
12 -> 1228 [1,1,1,1,1,2,2,2,3,3,4,5]
13 -> 2475 [1,1,1,1,1,1,2,2,2,3,3,4,5]
14 -> 4970 [1,1,1,1,1,1,2,2,2,3,3,4,5,6]

These cases were generated by a computer program, there is a chance there is an error. If you believe that there is an error, just let me know.

\$\endgroup\$
4
  • \$\begingroup\$ So we output the list and the number? \$\endgroup\$
    – DialFrost
    Commented Oct 11, 2022 at 23:41
  • \$\begingroup\$ @DialFrost "You do not need to output the order it is included for your convenience." \$\endgroup\$
    – Wheat Wizard
    Commented Oct 12, 2022 at 0:05
  • \$\begingroup\$ So we have to find the theoretical complexity of our answer? \$\endgroup\$
    – Fatalize
    Commented Oct 12, 2022 at 7:53
  • \$\begingroup\$ @Fatalize Let me be explicit that we care about big \$O\$ notation. So you need to at least establish an upper bound. \$\endgroup\$
    – Wheat Wizard
    Commented Oct 12, 2022 at 12:15

1 Answer 1

2
\$\begingroup\$

Python3, seems like it might be o(3^n) or thereabouts

Tracks subsets and then counts the distinct permutations in closed form, merges together subsets with the same length, sum, and lowest run, and uses a bound to cut off unpromising states (it could be tighter).

import collections
import copy
import functools
import random
from fractions import Fraction
from math import factorial

class Subset:
    def __init__(self, n):
        self.high_size = Fraction(1, 1)
        self.high_count = 0
        self.n = n
        self.n_count = 0
        self.sum = 0
    def increment(self):
        self.sum += self.n
        self.n_count += 1
    def restrict(self, x):
        if x >= self.n:
            return
        self.high_size *= Fraction(1, factorial(self.n_count))
        self.high_count += self.n_count
        self.n = x
        self.n_count = 0
    def count_size(self):
        return factorial(self.n_count + self.high_count) * self.high_size * Fraction(1, factorial(self.n_count))
    def state_tuple(self):
        return (self.high_size, self.high_count, self.n, self.n_count, self.sum)
    def __eq__(self, other):
        return self.state_tuple() == other.state_tuple()
    def __hash__(self):
        return hash(self.state_tuple())

@functools.lru_cache(None)
def sum_partitions(k, n, l):
    if n == 0:
        return 1
    if l == 0:
        return 0
    t = 0
    for i in range(1, k + 1):
        if l * i >= n:
            t += sum_partitions(i, n - i, l - 1)
    return t

@functools.lru_cache(None)
def f(partial_sums, k, n, l):
    global best
    if l == 0:
        s = sum(u.count_size() for u in partial_sums)
        best = max(s, best)
        return s
    bound = sum(factorial(u.n_count + u.high_count + l) * u.high_size * sum_partitions(u.n, n - u.sum, l) * Fraction(1, factorial(u.n_count)) for u in partial_sums)
    if bound <= best:
        return 0
    c = 0
    for i in range(1, k + 1):
        a = [copy.deepcopy(u) for u in partial_sums if u.n >= i and u.sum + i <= n and u.sum + l * i >= n]
        b = [copy.deepcopy(u) for u in partial_sums if u.sum + (l - 1) * (i - 1) >= n]
        for u in a:
            u.restrict(i)
            u.increment()
        for u in b:
            u.restrict(i - 1)
        s = a + b
        q = collections.defaultdict(lambda: 0)
        for u in s:
            w = u.high_size
            u.high_size = 0
            q[u] += w
        s = set()
        for u, w in q.items():
            u.high_size = w
            s.add(u)
        c = max(c, f(frozenset(s), i, n, l - 1))
    return c

for n in range(20):
    best = 0
    print(n, f(frozenset([Subset(n)]), n, n, n))
\$\endgroup\$
3
  • \$\begingroup\$ BTW instead of creating a function to calculate factorials, use the math module function \$\endgroup\$ Commented Oct 14, 2022 at 4:59
  • \$\begingroup\$ @py3_and_c_programmer thanks. \$\endgroup\$ Commented Oct 17, 2022 at 1:19
  • \$\begingroup\$ I am very surprised there isn't a faster dynamic programming solution \$\endgroup\$
    – Simd
    Commented Jan 1, 2023 at 10:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.