Enumerate all valid orders of subset sums

Question

Given an positive integer $n$, we define an order of subset sums (or simply, an order, when there is no ambiguity) to be a sequence of all subsets of ${1,ldots,n}$. For example, when $n=2$, the sequence $emptyset,{1},{2},{1,2}$ is an order.

We call an order $S_1,ldots,S_{2^n}$ valid if there exist real numbers $0<x_1<cdots<x_n$ such that $sum_{iin S_1}x_i<cdots<sum_{iin S_{2^n}}x_i$. For example, when $n=2$, the sequence $emptyset,{1},{2},{1,2}$ is a valid order, but the sequence $emptyset,{1},{1,2},{2}$ is not because we cannot make $x_1+x_2<x_2$.

The question is, given $n$, how to enumerate all possible valid orders. To output an order $S_1,ldots,S_{2^n}$, it is sufficient to output an algorithm that generates this order, i.e., an algorithm with no input (the parameter $n$ is built-in) that outputs $S_1,ldots,S_{2^n}$ in order, as long as the algorithm runs in $O(n2^n)$ time. Even so, this problem still cannot be solved in time polynomial in $n$, because there may be exponentially many valid orders, thus an algorithm running in exponential time is welcome.

A trivial algorithm would be to iterate over all possible orders, and check for each one if it is valid. But I cannot even find an (efficient) way to check if an order is valid.

D.W. · Answer

Here is one algorithm that runs in doubly exponential time -- so probably useless.  In other words, this answer is probably not useful.

You can check whether an order is valid in $2^{O(n)}$ time (i.e., $text{poly}(2^n)$ time) by reducing to linear programming: you obtain $2^n+n-2$ linear inequalities in $n$ variables, and you can test for feasibility in time polynomial in the number of inequalities and variables.  Then, enumerating over all possible sums and checking if each is valid would yield a $(2^n)! 2^{O(n)} = 2^{n 2^n + O(2^n)}$ time algorithm.  This will be ridiculously slow in practice.

To improve this, you could use an iterative pruning / branch-and-bound style algorithm.  Given a prefix $S_1,dots,S_k$ of an order, we can test whether it is valid using linear programming as above.  If it is not, we don't consider any order that starts with this prefix.  In other words, do breadth-first search: first choose $S_1$, then choose $S_2$, then choose $S_3$, and so on, at each step checking whether the prefix obtained so far is valid.

This may still be extremely slow, as there is the possibility that a prefix $S_1,dots,S_k$ is valid but there is no way to complete it to a full order $S_1,dots,S_{2^n}$ that is valid, so this might do a lot of wasted work.

Enumerate all valid orders of subset sums

One Answer

Add your own answers!

Ask a Question