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).

Improve this question
$\endgroup$
6
  • $\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$ Commented Aug 17, 2022 at 21:42
  • $\begingroup$ What is a "combination of A"? Do you mean "subsequence"? $\endgroup$ Commented Aug 17, 2022 at 23:12
  • $\begingroup$ cs.stackexchange.com/tags/dynamic-programming/info $\endgroup$ Commented 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$ Commented Aug 18, 2022 at 13:59
  • $\begingroup$ By "combinations of A", do you mean "subsets of A"? $\endgroup$ Commented Sep 17, 2022 at 3:49

2 Answers 2

Reset to default
1
$\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
Improve this answer
$\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$ Commented Aug 18, 2022 at 2:38
0
$\begingroup$

Assuming values to be unique/strictly increasing:

superincreasing subsequences of A:

  1. initialise a collection extend to the empty sequence

  2. terminate if extend is empty

  3. take any sequence e out of extend

  4. for every value v greater than sum(e):
      longer ← e extend with v
      report longer
      if sum(longer) less than max(A):   
        add longer to extend
    continue with 1

Improve this answer
$\endgroup$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.