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.

Improve this question
\$\endgroup\$
4
  • \$\begingroup\$ So we output the list and the number? \$\endgroup\$ Commented Oct 11, 2022 at 23:41
  • \$\begingroup\$ @DialFrost "You do not need to output the order it is included for your convenience." \$\endgroup\$ Commented Oct 12, 2022 at 0:05
  • \$\begingroup\$ So we have to find the theoretical complexity of our answer? \$\endgroup\$ 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\$ Commented Oct 12, 2022 at 12:15

1 Answer 1

Reset to default
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))
Improve this answer
\$\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\$ 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.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.