4
$\begingroup$

Recently I was solving a counting problem, which needed this subproblem to be solved:

Given integers $n$ and $t$ (where $1 \le t \le n$) and a decreasing function $f$, find the number of permutations $p_1, p_2, \cdots, p_n$ which satisfy:

  • for all $1 \le i \le t$, $p_i \le f(i)$, and
  • for all $t < j \le n$, $p_j \ge f(j)$.

For my problem, $n$ is quite big (about 40, which enabled me to think of meet-in-the-middle), but $t$ is quite small (about 10-15). So I tried to solve the problem with an algorithm regarding $t$, but failed.

I tried to exploit the fact that, if we consider only one of the conditions, the problem becomes super-easy. So I allocated first $t$ elements of the permutation(tried all possible cases), and then calculated # of possible permutations of the remaining $n-t$ elements. This method could give an answer reasonably faster than iterating all possible $n!$ permutations. However it is still really slow, maybe using an $2^n n^2$ dp approach would be faster than this.

I believe that iterating first $t$ elements is not required to solve the problem, but couldn't find any way. Could you please help me solve this problem?

$\endgroup$
1
  • $\begingroup$ 1. Do you have $f(1)=n$ and $f(n)=1$? If not, we might be able to make use of that. 2. Do you need an exact count, or would an approximate count be OK? 3. You could express this as an instance of #SAT and try applying a #SAT solver -- I don't know if it would work, but you could try it. $\endgroup$ – D.W. Sep 21 '16 at 15:09
2
$\begingroup$

A faster approach

It's possible to solve this in $O(\binom{n}{t} \cdot n)$ operations, i.e., at most $O(n^{t+1})$ operations. This is faster than the algorithm you describe in your question by about a factor of $t!$, but probably still not fast enough to be feasible for your parameters.

The idea is to enumerate all possible subsets of $t$ elements. We'll try all possible choices for $S$, the set of elements that occur in positions $1,2,\dots,t$ (without regard to what order they appear in). There are $\binom{n}{t}$ such choices for $S$.

For each choice of $S$, we separately (i) count the number of ways to order the elements of $S$ so that the first $t$ elements satisfy the first condition, and (ii) count the number of ways to order the elements of $\{1,2,\dots,n\}\setminus S$ so that the last $n-t$ elements satisfy the second condition. Then, we multiply these two counts.

Each of those counts can be computed efficiently. For instance, to compute count (i), we compute

$$g(t) \times (g(t-1)-1) \times (g(t-2)-2) \times \dots \times (g(1)-(t-1)),$$

where $g(i) = |S \cap \{1,2,\dots,f(i)\}|$ counts the number of elements of $S$ that could potentially be used at position $i$ without violating the first condition (i.e., the number of elements of $S$ that are $\le f(i)$). Similarly, to compute count (ii), we compute

$$h(t+1) \times (h(t+2)-1) \times (h(t+3)-2) \times \dots \times (h(n)-(n-t+1)),$$

where $h(i) = |\overline{S} \cap \{f(i),\dots,n\}|$.

These two counts can be computed using $O(n)$ operations, leading to the claimed running time.

A further optimization

You can further optimize this, by splitting $S$ into two parts. Decompose $S$ into

$$S = S_1 \cup S_2,$$

where $S_1 \cap S_2 = \emptyset$, by defining

$$\begin{align*} S_1 &= S \cap \{f(t+1),f(t+1)+1,\dots,n-1,n\}\\ S_2 &= S \cap \{1,2,3,\dots,f(t+1)-1\}. \end{align*}$$

Now notice that to count (ii), we don't actually need to know both $S_1$ and $S_2$: it's enough to know $|S_1|$ and $S_2$: the exact elements in $S_1$ don't change the count (by a relabelling argument), since they're all $\ge f(j)$ for all $j>t$.

Furthermore, since $|S|=t$ and $|S|=|S_1|+|S_2|$, it suffices to know $S_2$. Once we know $S_2$, we can compute $|S_1|=t-|S_2|$ and then compute count (ii).

Similarly, once we know $S_2$, we can also compute count (i).

So, we're going to enumerate all possible values for $S_2$, i.e., all subsets of $\{1,2,3,\dots,f(t+1)-1\}$ of size $\le t$. There are

$$Q = \binom{f(t+1)-1}{t} + \dots + \binom{f(t+1)-1}{1} + \binom{f(t+1)-1}{0}$$

possible choices for $S_2$. Then we obtain an algorithm whose running time is $O(Q \cdot n)$. The exact value of $Q$ depends on $f(t+1)$, but we have $Q = O(f(t+1)^t)$.

In this way we obtain an algorithm whose running time is $O(f(t+1)^t \cdot n)$. For many choices of $f$, this will be even faster than the basic approach sketched at the beginning of this answer.

Also, it's easy to see that we must have $f(t+1) \ge n-t+1$ (otherwise the count is 0). It follows that there is an algorithm whose worst-case running time is $O((n-t)^t \cdot n)$, regardless of $f$.

$\endgroup$
2
  • $\begingroup$ Thanks for your suggestion! I have a question. In the further optimization part, you said that it is possible to count (i) just knowing $S_2$. However, to count (i) in the similar manner calculating count (ii), seems impossible as we don't know $S_1$ we cannot decide $g(i)$ efficiently. I tried to calculate the sum of all permutations satisfying $|S_1|$, but it seems hard. I could only manage to get $O(\sum H(t, t-k))$ algorithm (iterating all possible frequencies), and not sure it's correct. Could you please elaborate more? $\endgroup$ – user1743455 Sep 21 '16 at 23:20
  • $\begingroup$ @user1743455, yes, you're right, I think a more involved method is needed to count (i) in that case. I think it suffices to use dynamic programming, where for each $i \in \{1,2,\dots,t\}$ and each $k \in \{1,2,\dots,|S_2|\}$ we have a subproblem to count the number of ways to pick $p_i,p_{i+1},\dots,p_t$ such that $|\{p_i,\dots,p_t\} \cap S_2|=k$. That should be solvable by dynamic programming in $O(n^2)$ time. I think. I haven't checked the details carefully -- please check them yourself. There might be other similar issues in the answer -- please proofread and test carefully! :) $\endgroup$ – D.W. Sep 21 '16 at 23:48

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.