3
$\begingroup$

Given a set of positive integers, I am looking for method to algorithmically generate all possible subsets in order of their sum. Because the the count of possible subsets is exponential ($2^n$), it is not feasible to brute-force them and then sort. Instead, the solution would generate one answer at a time, starting with smallest sum (i.e. an online algorithm).

Here's an example:

$$A=\{1,2,10\}$$

And the expected results:

$$S_1=\{\}$$ $$S_2=\{1\}$$ $$S_3=\{2\}$$ $$S_4=\{1,2\}$$ $$S_5=\{10\}$$ $$S_6=\{1,10\}$$ $$S_7=\{2,10\}$$ $$S_8=\{1,2,10\}$$

This problem seems to be related to the Knapsack problem and the Subset sum problem. It is also related to this question, to which there are unfortunately no answers. In my specific case the previous subsets are known and the overall time complexity is not the issue, but calculating the answers in the correct order. This is why I hope there is a solution that runs in polynomial time per iteration, but in $O(2^n)$ for all answers.

If someone could confirm whether it is possible or point me in the right direction it would be greatly appreciated.

Improve this question
$\endgroup$
7
  • 2
    $\begingroup$ It should be possible to get space complexity $O(2^{n/4})$ using the data structures suggested by Schroeppel and Shamir (1981). $\endgroup$
    – Max Alekseyev
    Commented Mar 19 at 21:44
  • 1
    $\begingroup$ Is $O(n)$ per iteration and $O(n 2^n)$ total acceptable? If so, you can achieve this by using any $O(1)$ insert time heap to store the candidate sets. You start with the empty set on the heap, and then any time you take a set $S$ out, you insert $S \cup \{a\}$ for all $a$ larger than all $s \in S$ back to the heap. en.wikipedia.org/wiki/… $\endgroup$
    – user1020406
    Commented Mar 20 at 13:14
  • 3
    $\begingroup$ See math.stackexchange.com/a/89453/752906 this Math Stack Exchange question and answer $\endgroup$
    – Daniel Weber
    Commented Mar 20 at 15:08
  • $\begingroup$ @CommandMaster Thank you, that seems to be exactly my problem and the answer I am looking for! Too bad I did not find this earlier. $\endgroup$
    – Ood
    Commented Mar 20 at 16:20
  • $\begingroup$ I'm not sure the answer at stackexchange satisfies "polynomial time per iteration". $\endgroup$
    – Brendan McKay
    Commented Mar 21 at 4:03

1 Answer 1

Reset to default
-1
$\begingroup$

I will give you the main idea in the following steps:

  1. You must put initially the empty set directly without counting (I'm assuming that the set contains only positive numbers).
  2. You construct the following mathematical program: $$ x_i = \begin{cases} 1 , & \ \text{if the element } i \text{ of the set } A \text{ is chosen;}\\ 0 , & \ \text{otherwise.} \end{cases}$$

$$\left\{\begin{aligned} & {\min \sum_{i=1}^{n} A_i x_i} \\ & \text{s.t.} \\ & \sum_{i=1}^{n} x_i \geq 1 \end{aligned}\right.\tag{$P$}\label{467374_P}$$ where $n=|A|$.

  1. You solve the problem \eqref{467374_P}, and let $B$ the set of the outer base variables of the optimal solution.

  2. Generate the constraint that excludes the current optimal solution from your domain: $$ \sum_{i\in B} x_i \geq 1.$$

  3. Add the new constraint to \eqref{467374_P}.

  4. Repeat the steps 3, 4 and 5 until \eqref{467374_P} becomes empty. Terminate.

Each solution you get is the minimal possible in the current domain, so you'll get your subsets in the wanted order.

By doing that, I'm assuming that we have only positive numbers, if you have negative numbers (and eventually the number zero) you must omit the step one and the constraint $\sum_{i=1}^{n} x_i \geq 1$ from \eqref{467374_P}.

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ Can you prove that this runs in polynomial time, as required by the OP? $\endgroup$
    – Alex M.
    Commented Mar 20 at 11:44
  • $\begingroup$ It's certainly not going to be amortised $O(1)$ per subset. $\endgroup$
    – Peter Taylor
    Commented Mar 20 at 11:57
  • $\begingroup$ We must choose a subset among others, it is a combinatoric problem which is NP-complete, the proposed method in the general case at the first step is $O(\sqrt n)$, by adding the constraint at step 4, it will be $O(2^n)$ in the general case, but practically, it will be really speed up because we begin from the optimal solution. The inconvenient here is the program must use the Branch and Bound procedure to resolve it. $\endgroup$
    – BADJARA Mohamed el Amine
    Commented Mar 20 at 12:15
  • $\begingroup$ How does \eqref{467374_P} become empty? You only add to it, never remove anything from it. I guess you mean the solution set is empty? In that case, although it probably doesn't much matter, since you know how many sets you're emitting, you can just keep track and stop when you've emitted them all. $\endgroup$
    – LSpice
    Commented Aug 17 at 22:55

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .