0
$\begingroup$

A sequence of positive real numbers S1, S2, S3, …, SN is called a superincreasing sequence if every element of the sequence is greater than the sum of all the previous elements in the sequence. E.g: 1, 3, 6, 13, 27, 52.

Given a sorted list A, I want to iterate over all combinations of A, which are superincreasing.

How example:

A = [28, 34, 44, 60, 71, 150, 167, 212, 230, 239, 415, 431, 434, 559, 688]

Valid examples of subsequences:

34, 44, 239, 434
34, 212, 434, 688

Here is a simple brute force example:

def is_superincreasing(seq):
 total = 0
 test = True
 for n in seq:
    if n <= total:
        test = False
        break
    total += n
 return test

def combinations(A):
    N = len(A)
    for i in range(2**N):
        combo = []
        for j in range(N):
            if (i >> j) % 2 == 1:
                combo.append(A[j])
        if is_superincreasing(combo):
         yield combo

I'd like to know if there is a better algorithm than O(2^n).

$\endgroup$
7
  • $\begingroup$ 1. What's a "superincreasing combination of A"? 2. What is your question? What approaches have you already considered? Please edit the question to clarify. $\endgroup$
    – D.W.
    Aug 17, 2022 at 21:42
  • $\begingroup$ @D.W., thanks! I've updated the question. $\endgroup$ Aug 17, 2022 at 22:30
  • $\begingroup$ What is a "combination of A"? Do you mean "subsequence"? $\endgroup$
    – D.W.
    Aug 17, 2022 at 23:12
  • $\begingroup$ cs.stackexchange.com/tags/dynamic-programming/info $\endgroup$
    – D.W.
    Aug 18, 2022 at 0:29
  • 1
    $\begingroup$ Also, note that if $A = \{1,2,4,8,...,2^k,...,2^n\}$ you can't do better than $\Omega(2^n)$. However, like @D.W. says, I believe that dynamic programming and memoization will give you optimal results. $\endgroup$
    – Matt Groff
    Aug 18, 2022 at 13:59

1 Answer 1

0
$\begingroup$

May not be the best solution in terms of complexity, because of duplicate summation operations with further elements, but much better in the general case.

def superincreasing_combinations(g):
  ln = len(g) - 1
  operate = {}
  ret = set()

  for i, e in enumerate(g):
    operate[(e,)] = (i, e)

  while operate:
    o, v = operate.popitem()
    last_index, sumo = v

    while last_index < ln:
     last_index += 1
     next = g[last_index]
     if next > sumo:
      operate[(*o, next)] = (last_index, sumo + next)

    ret.add(o)
  return ret
$\endgroup$
1
  • 4
    $\begingroup$ We're not a coding site, and we discourage code-only answers. Instead, we're looking for ideas, concise pseudocode, algorithms, explanations, and/or proof of correctness. $\endgroup$
    – D.W.
    Aug 18, 2022 at 2:38

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.