3
$\begingroup$

I have an array of integers T[N] indexed from 1. For example T[1] = 1, T[2] = 4, T[3] = 5, T[4] = 9. Let's enumerate all subsets of this set in a certain order: increasing sum of the elements. In case of a tie, we compare the sorted lists of indexes of numbers in subsets.

For example:

  1. {} = 0 indexes: 0

  2. {1} = 1 indexes: 1

  3. {4} = 4 indexes: 2

  4. {1, 4} = 5 indexes: 1, 2

  5. {5} = 5 indexes: 3

  6. {1, 5} = 6 indexes: 1, 3

  7. {4, 5} = 9 indexes: 2, 3

  8. {9} = 9 indexes: 4

  9. {1, 4, 5} = 10 indexes: 1, 2, 3

  10. {1, 9} = 10 indexes: 1, 4

  11. {4, 9} = 13 indexes: 2, 4

  12. {1, 4, 9} = 14 indexes: 1, 2, 4

  13. {5, 9} = 14 indexes: 3, 4

  14. {1, 5, 9} = 15 indexes: 1, 3, 4

  15. {4, 5, 9} = 18 indexes: 2, 3, 4

  16. {1, 4, 5, 9} = 19 indexes: 1, 2, 3, 4

There were 3 ties at: 7-8, 9-10, 12-13, so we compared lists of indexes lexicographically.

What I want to do, is to find $k$-th subset. What is the fastest way to do this, assuming that both N and K are less than $10^6$? I know how to do this in quadratic time.

I assume that all numbers are positive and some of them may be equal.

Question is inspired by this https://math.stackexchange.com/questions/89419/algorithm-wanted-enumerate-all-subsets-of-a-set-in-order-of-increasing-sums

Improve this question
$\endgroup$
2

2 Answers 2

Reset to default
6
$\begingroup$

Since this is MathOverflow I'll give you the mathematical answer rather than the practical answer. I'll assume all numbers are positive; otherwise minor modifications would be needed to handle negative numbers. Also, I'm taking literally your request for the $k$th subset alone, rather than for all subsets up to that one; otherwise just the time to write them all down could be quadratic.

  • Sort the input numbers
  • Define a tree on the nonempty subsets, where the root is the singleton consisting only of the first element, the left child of a set whose maximum element is $i$th in the sorted input list is obtained by replacing that element by element $i+1$, and the right child is obtained by including element $i+1$ without removing any existing element. This tree contains all nonempty subsets (exactly once each) and is heap-ordered.
  • To make tree operations fast, represent each set implicitly by a triple of (its parent, the operation that was used to create it, its sum). In this way each set can be represented in $O(1)$ space and it takes $O(1)$ time to find its children.
  • Find the $k$ smallest elements of the heap-ordered tree using the $O(k)$-time algorithm in "An optimal algorithm for selection in a min-heap", Frederickson, Inf. & Comput. 1993 (this is the part that's more theoretical than practical. In practice you could do a best-first search using a binary heap in time $O(k\log k)$, or maybe an integer priority queue if you know that the sums you're going to get are small).
  • If you need to, decode the $k$th set from its compact representation into an explicit list of elements, by backtracking through the tree to find the sequence of operations that created this set and then applying those operations to the initial singleton set.
Improve this answer
$\endgroup$
4
  • $\begingroup$ Store the original index of each element before sorting. Use the data structure from the appendix of my paper arxiv.org/abs/1504.04931 to break ties quickly. $\endgroup$
    – David Eppstein
    Commented Nov 1, 2015 at 18:19
  • $\begingroup$ In view of my answer below, please notice that the proposed algorithm is not polynomial in the size of the input. The input size here is a polynomial in $|T|$ and $\log k$ (not $k$). $\endgroup$
    – Max Alekseyev
    Commented Oct 11, 2016 at 14:45
  • $\begingroup$ Correct, of course. There's still a big gap between hardness for polylog$(k)$ and this $O(k)$ algorithm that it would be interesting to tighten. $\endgroup$
    – David Eppstein
    Commented Oct 11, 2016 at 17:15
  • $\begingroup$ Output all subset up to the $k$th one is only $O(k \log k)$, because output a set of size $t$ implies all its subsets are also in the output, so the largest set has size $\log k$. $\endgroup$
    – Chao Xu
    Commented Apr 21, 2017 at 7:28
3
$\begingroup$

I'm afraid solving your problem in polynomial time is not possible unless P=NP. (Notice that the input size here is a polynomial in $|T|$ and $\log k$, but not $k$.)

If one can solve your problem in polynomial time, then using such solution algorithm $P(T,k)$ and binary search (in the virtual array of subsets of $T$ sorted by their sums, where $k$-th element is accessed with $P(T,k)$), it would be possible to solve the Subset Sum Problem in polynomial time as well. But the latter problem is NP-complete.

Improve this answer
$\endgroup$
1
  • $\begingroup$ @D.W.: First, the question does not explicitly ask "for an algorithm whose running time is polynomial in $k$" (such algorithm would not be necessarily polynomial in the size of the input). Second, I proved that if there is a polynomial-time algorithm (in the size of the input, which is polynomial in $\log k$, not $k$), then there would be one for the subset sum problem. Third, the algorithm proposed in the other answer is not polynomial as it constructs a tree on all subsets of the input set. $\endgroup$
    – Max Alekseyev
    Commented Oct 11, 2016 at 14:20

Not the answer you're looking for? Browse other questions tagged .