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 < x < y < 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 < x < y < xy \\ \emptyset < y < x < xy$$

For three items, the output should be 12 orders - 2 orders for each permutation of $x,y,z$. For example, for $x<y<z$ the two orders are: $$\emptyset < x < y < z < xy < xz < yz < xyz \\ \emptyset < x < y < xy < z < xz < yz < 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.

• Do you just want a formula for this? – rus9384 Aug 26 '17 at 23:36

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 < S$ is consistent. For each consistent $S$, we make another recursive call.
How do we check whether $\phi < 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 > 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 < y < z$); if you are really interested in all possible orders, you can always go over all permutations later.