6
$\begingroup$

I have an interesting function. It takes subsets of {1,...,N} to positive integers, i.e. $f:P([N]) \rightarrow Z^+$. I know that if S is a subset of S', $f(S) < f(S')$. Also, if S and S' have the same cardinality, the ordering induced by f is lexicographic, so for example $f(\{1,2,4\}) < f(\{1,3,4\})$. Given a value z, I'd like to find S such that $f(S) <= z$ and $f(S) <= f(T) <= z$ implies $f(S)=f(T)$ -- that is, I want to do a search on the lattice of subsets of [N].

If I knew the ordering were perfectly lexicographic, I'd use a simple binary search. I don't know that, and I believe it is not (e.g., $f(\{1,2,3,4,5,6\})$ is possibly greater than $f(\{7\})$). Is there a good O(N) algorithm to do this search on the poset? Obviously for N of any appreciable size I have to compute f on-the-fly and can't rely on in-memory storage.

Clarification after a discussion in the comments: The particular $f$ I am dealing with is additive -- specifically, $f(S) = \sum_{k\in S} g(k) + f(\emptyset)$, with $g$ a monotonically increasing function. This may be easier than the general case (which is also interesting, but not my particular problem).

$\endgroup$
15
  • $\begingroup$ There is an O(N^2 log N) algorithm; basically do a binary search on subsets of size K using the lexicographic order, for each K from 0 to N. Retain the one with the best value of f. Can I do better? $\endgroup$ – Craig Jul 8 '20 at 16:03
  • $\begingroup$ "the ordering induced by f is lexicographic" After sorting the sets I presume? Because $\{1,2\} = \{2, 1\}$. $\endgroup$ – orlp Jul 8 '20 at 18:38
  • $\begingroup$ Also what is your unit of measurement here. Are queries to $f$ relatively expensive or cheap? E.g. would a hypothetical algorithm that makes $O(N)$ queries to $f$ but takes $O(N^3)$ time in total be preferable to an algorithm that has total time of and makes $O(N^2)$ queries to $f$? $\endgroup$ – orlp Jul 8 '20 at 18:46
  • $\begingroup$ Yes, lex after sorting the sets. Think of it this way; if N = 40, I can represent a subset by a 40-bit number, with the highest bit representing whether 40 is in the subset and the lowest representing whether 1 is in the subset. $\endgroup$ – Craig Jul 8 '20 at 20:04
  • $\begingroup$ Queries to f take O(N) time, but it's independent of the subset, so for N = 40, f({1}) takes the same amount of time as f({1,2,...,39,40}) $\endgroup$ – Craig Jul 8 '20 at 20:06
4
$\begingroup$

Here is a simple algorithm that runs in $O(N^2)$ time and $O(N)$ space, assuming that $f(\emptyset)$, $f(\{1\})$, $f(\{2\})$, $\cdots$, $f(\{N\})$ are given in an array.

The starting idea is about the same as what has been given by the OP in his comment. "We will search on subsets of size K using the lexicographic order, for each $K$ from $0$ to $N$. Retain the one with the best value of $f$."

The problem is then how to search the best value of $f$ on subsets of size $K$, named $b_K$, in $O(N)$ time. Instead of binary search, we will check whether $N$, $N-1$, \cdots, $1$ should be included in the best subset one by one, by taking the real advantage of the lexicographic order on subsets.

  1. Initialize $b_K = f(\emptyset)$. $\ b_K$ will be the best value on subsets of size $K$ at the end of this procedure.
  2. Initialize $count = 0.$ $\ count$ is the number of elements that we have included in the best subset so far.
  3. Check $f(\{N\})$. If $b_K + f(\{N\}) + f(\{1, 2, \cdots, K-count -1\})\le z$, $N$ must be included. Add $f(\{N\})$ to $b_K$ and add 1 to $count$.
  4. Check $f(\{N-1\})$. If $b_K + f(\{N-1\}) + f(\{1, 2, \cdots, K-count-1\})\le z$, $N-1$ must be include. Add $f(\{N-1\})$ to $b_K$ and add 1 to $count$.
  5. And so on.
  6. Until either we have checked $f(\{1\})$ or $count == K$.

We might wonder, if it will take $O(N)$ to compute each $f(\{1,2, \cdots, K-count-1\})$, computing each $b_K$ alone will take $O(N * N)$ time. However, since $f$ is additive, we can compute all prefix sums of $f(\{1\})$, $f(\{2\})$, $\cdots$, $f(\{N\})$ upfront in $O(N)$ time. Then it takes $O(1)$ to access each prefix sum.

Since searching $b_K$ takes $O(N)$ time, for each $K$ from $0$ to $N$, the total running time is $O(N^2)$.


The description above of the algorithm skips the easiest case when $f(\emptyset)\gt z$. In that case, the algorithm should return that there is no such subset.

$\endgroup$
2
  • $\begingroup$ Modulo minor corrections due to the fact that $f(\emptyset)$ is not 0, this does solve it. Thanks! $\endgroup$ – Craig Jul 11 '20 at 3:21
  • $\begingroup$ Indeed. I just updated answer so that $f(\emptyset)\not=0$ is treated properly. $\endgroup$ – John L. Jul 11 '20 at 4:43

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.