# Enumerate all valid orders of subset sums

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 such that $$\sum_{i\in S_1}x_i<\cdots<\sum_{i\in 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.

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.

• As far as I understand, you are asking about Boolean Lattice (please see: en.wikipedia.org/wiki/Boolean_algebra_(structure)), where you introduce a total order using an additional vector $X=(x_1,x_2,...,x_n)$. Your "valid order" is used to be called a chain. It's unclear why you define this total order using existence of $X$ only - it will depend on values in $X$. Also for totally ordered set there will be only one chain (provided that there are no pairwise equal elements). Feb 23 '20 at 23:10
• @HEKTO Yes, I'm essentially seeking for a method to enumerate all possible chains as the values of $x_1,\ldots,x_n$ vary. However, I don't understand how this problem is related to the Boolean algebra since this problem talks about orders of subsets. Feb 24 '20 at 1:51
• If you want to know what happens with chains when the vector $X$ varies - then you should clarify your question. The set of subsets of a finite set is Boolean algebra and Boolean lattice (= $n$-dimensional hypercube), where each node is a Boolean $n$-tuple Feb 24 '20 at 4:04
• @HEKTO I now understand the relation between subsets and Boolean algebra, but how can this help solve the problem? I don't know how to clarify since I don't know the definition of "chain" and I have a sense that your "chain" is not equivalent to my "valid order". Maybe it is more proper to say that I'm essentially seeking for a method to enumerate all possible total orders as the values of $x_1,\ldots,x_n$ vary. I think the question statement is clear though it does not mention any concept about boolean lattice. Feb 24 '20 at 5:47
• Chain is a totally ordered subset of a poset. Maximum chain is a chain, which is not contained in any other chain. Totally ordered set consists of a single maximum chain. Feb 24 '20 at 15:14

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.