4
$\begingroup$

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.

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

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.