patternMinor
# of permutations satisfying special inequalties of each element0
Viewed 0 times
eachsatisfyingelement0specialinequaltiespermutations
Problem
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 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?
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
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?
Solution
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$.
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$.
Context
StackExchange Computer Science Q#63722, answer score: 2
Revisions (0)
No revisions yet.