Finding all additive orders Suppose there are $m$ items, and each item has a price. We order the subsets of items according to their price. For example, if the price of $x$ is 1 and the price of $y$ is 2, then the order is:

$$
\emptyset &lt; x &lt; y &lt; xy
$$

What is an algorithm for enumerating all orders of subsets that can be generated by such prices? For example, for two items the output should be two orders:

$$
\emptyset &lt; x &lt; y &lt; xy
\\
\emptyset &lt; y &lt; x &lt; xy
$$

For three items, the output should be 12 orders - 2 orders for each permutation of $x,y,z$. For example, for $x&lt;y&lt;z$ the two orders are:
$$
\emptyset &lt; x &lt; y &lt; z &lt; xy &lt; xz &lt; yz &lt; xyz
\\
\emptyset &lt; x &lt; y &lt; xy &lt; z &lt; xz &lt; yz &lt; xyz
$$

One solution is to generate all $(2^m)!$ orders and then check, for each order, whether it is compatible with some prices. However, it is not clear how to do this check, and even with a good algorithm for such a check, it will still very wasteful as most orders will be incompatible. For example, for 3 items we will need to check $8!$ orders to return only 12.

Note: I asked a similar question in math.SE, but the answer is apparently incorrect.
One approach is to recursively extend prefixes of the order. At each recursive call, we have a prefix $\phi$ of the order. We go over all remaining subsets, and for each subset $S$, we check whether the order $\phi &lt; S$ is consistent. For each consistent $S$, we make another recursive call.

How do we check whether $\phi &lt; S$ is consistent? This is a linear programming problem, whose solution we can speed up by starting the simplex algorithm from the "witness" showing that $\phi$ is feasible. There are two things to notice here: First, presumably you are assuming that all weights are positive. Second, we replace each constraints $A &gt; B$ by $A \geq B+1$ (since LPs don't have strict constraints).

There are many optimizations which can be done here. For example, $S$ is always inclusion-minimal among the remaining subsets. Another optimization is to assume that the weights are ordered in a specific way (in your example, $x &lt; y &lt; z$); if you are really interested in all possible orders, you can always go over all permutations later.