TransWikia.com

Enumerate all valid orders of subset sums

Computer Science Asked by xskxzr on December 6, 2021

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 S1,ldots,S2n valid if there exist real numbers 0<x1<cdots<xn such that sumiinS1xi<cdots<sumiinS2nxi. 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 x1+x2<x2.

The question is, given n, how to enumerate all possible valid orders. To output an order S1,ldots,S2n, 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 S1,ldots,S2n in order, as long as the algorithm runs in O(n2n) 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.

One 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 2O(n) time (i.e., textpoly(2n) time) by reducing to linear programming: you obtain 2n+n2 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 (2n)!2O(n)=2n2n+O(2n) 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 S1,dots,Sk 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 S1, then choose S2, then choose S3, 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 S1,dots,Sk is valid but there is no way to complete it to a full order S1,dots,S2n that is valid, so this might do a lot of wasted work.

Answered by D.W. on December 6, 2021

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP