Counting permutations whose elements are not exactly their index ± M

I was recently asked this problem in an algorithmic interview and failed to solve it.

Given two values N and M, you have to count the number of permutations of length N (using numbers from 1 to N) such that the absolute difference between any number in the permutation and its position in the permutation is not equal to M.

Example - If N=3 and M=1 then, 1 2 3 and 3 2 1 are valid permutations but 1 3 2 is invalid as the number 3 is at position 2 and their difference is = M.

I tried NxM Dynamic programming but failed to form a recurrence that doesn't count repetitions.

• You can perhaps obtain a formula using inclusion-exclusion. The case $M=0$ is classically known as derangements. – Yuval Filmus Apr 8 '17 at 17:38
• This is a particular instance of counting perfect matchings in bipartite graphs, a problem which is $\mathsf{\#P}$-complete. Of course, this particular case could be easier. – Yuval Filmus Apr 8 '17 at 17:41
• I already tried Inclusion-exclusion but made no progress. – Gena Apr 9 '17 at 6:18
• You could try adapting the methods for counting derangements. I don't know whether that will take you anywhere. You could also try fixing M=1 (say), computing the number for small values of N (N=1,2,3,4,5,6,7,8) by brute force, and then looking up the corresponding sequence in OEIS in hopes that you find something useful. – D.W. Apr 9 '17 at 17:06
• What is the recursion you set up? What do you mean by "count repetitions"? – Raphael Apr 13 '17 at 6:07

The first thing I would ask when given this question would be

Do you want a polynomial time algorithm?

and then I'd hope the answer is 'no'. I suspect that this problem is NP-hard, for the following reason:

The natural approach to this problem is to consider the placement of the first number and derive a recursive formula to place the others. This works nicely for the $M=0$ case (i.e. counting the number of derangements), as it doesn't matter on what position you have placed the first number, since there is only one 'illegal' position of every number. In other words, this approach leads to independent subproblems.

For $M>0$, this is not so simple, as we now can have $2$ illegal positions for some numbers. Which of these positions remain in the subproblem is now relevant to the solution of the subproblem. Only considering the number of 'illegal' positions is not sufficient, as the 'chains' of numbers that share an illegal position are required to determine the structure of the subproblems of that subproblem. So, this approach essentially leads to the following subproblem:

Given a set $A \subseteq \mathbb{N}$, a set $B \subseteq \mathbb{N}$ both of size at most $N$ and a natural number $M$, count the number of perfect matchings on the bipartite graph $(A,B,E)$, where $(a,b)\in E$ if and only if $|a-b|\neq M$.

This problem looks hard. The only approach to this problem I see is inclusion/exclusion, which will not lead to a polynomial time algorithm.

We can consider approaches that do not rely on the iterative placement of the numbers, but I have no clue how you would do this. (especially during an interview!)

Of course, all this is mere speculation and it is still possible that a clever trick can give a polynomial time solution, but I hope I have made convincing argument that this trick has to be very clever indeed.

Perhaps it is possible to show NP-hardness by reducing this problem to #2-SAT (the 'chains' of numbers that share illegal positions seem a non-trivial choice that could be matched with the selection of a truth-value), but I haven't seen an obvious way to do that as of now.

In case the interviewer would actually be satisfied with an exponential time algorithm, I'd simply generate all possible solutions by adapting a recursive backtracking algorithm to generate a permutation to exclude this particular case.

• I did say that I can give an exponential-time algorithm, but was asked for a polynomial time solution that works when N is <= 1000. – Gena Apr 14 '17 at 6:38
• Well, unless you mis-remembered/misinterpreted the question as the answer from PPenguin suggests, I think that this question is either asked by very demanding interviewers, interviewers who themselves misunderstood the question or perhaps even as a question they do not expect anyone to solve. Even if this question would turn out not to be computationally hard, it is most likely interview-hard. – Discrete lizard Apr 14 '17 at 8:36
• It appears that M=1 is likely doable (and therefore possibly the others), so there is something we missed. Can you help me understand/evaluate the M=1 case? I made a separate question for it cs.stackexchange.com/questions/74674/… – PPenguin Apr 28 '17 at 20:49

Is it possible you remembered the specific details wrong or misinterpreted the question?

In your description, element $a$ in position $b$ is restricted to $a-b \ne \pm M$.
But if they just meant the difference was restricted: $a-b \ne M$,
Then the problem appears tractable.

I worked out that simpler problem, and I tried to generalize in a way that I hoped might give some freedom in working out the larger problem. But this just clarified for me why a recursive approach is very unlikely to work, which I discuss at the end.

Consider the function $f(N,M,P)$ which gives the number of permutations of a list of elements labeled 1 to $N$, where the element $a$ in position $b$ (first position is 1) satisfies $a-b \ne M$, and $b-a \ne P$.

To visualize this, separating it into two constraints allows $M$ and $P$ to shift those restrictions around separately.

1 2 3 4 5  M=0, restricted values for each position
. . . . .  (positions in list)
1 2 3 4 5  P=0, restricted values for each position

3 4 5      M=2, restricted values for each position
. . . . .  (positions in list)
1 2 3 4  P=1, restricted values for each position


For convenience, when $P \ge N$ so that it doesn't place restrictions on the permutations, define $g(N,M) = f(N,M,P)$. Similarly, $g(N,P) = f(N,M,P)$ when $M \ge N$ so that it places no restriction on the permutations.

In the special case $M=P=0$ the constraint from $M$ and $P$ are equivalent, so one can be ignored, allowing us to write $f$ in terms of $g$: $$f(N,0,0) = g(N,0).$$

From the symmetry of the problem: $$f(N,M,P) = f(N,P,M)$$

Let's first solve for $g(N,M)$, and then tackle the more general $f(N,M,P)$.

For $M=0$, each element has one placement restriction (and the restrictions are distinct). So choosing some element $i$, we will place it in some position $j$. There are $N-1$ different possibilities for the choice of $j$.

This selection removed the restricted position for element $j$, while the other $(N-2)$ elements still have one restriction. We can break the placement of $j$ into two options:

1. Place in $i$. This leaves all other elements with one restriction, so the remaining placement problem is now reduced to $g(N-2,0)$.

2. Place in a position $\ne i$. This now gives one placement restriction for $j$, and so each element has one restriction, and the remaining placement problem is reduced to $g(N-1,0)$

So this gives the recursive formula: $$g(N,0) = (N-1) \left[ g(N-2,0) + g(N-1,0) \right]$$

And by looking at the simple situations by hand, can get the base cases. $$g(1,0) = 0, \ \ g(2,0) = 1$$

This is the usual derangement recursive formula.

While I can't imagine someone coming up with this on the spot, it also turns out there is a closed form solution for this (see the derangement wiki article for details).

$$g(N,0) = \left\lfloor \frac{n!}{e} + \frac{1}{2} \right\rfloor$$

For $M \ge N$, there is no restriction on any of the placements:

$$(M \ge N) \implies g(N,M) = N!$$

With $0<M<N$, the first $M$ elements will have no restrictions and the remaining elements will have one placement restriction. It terms of the positions, the last $M$ positions will allow all numbers.

For the last position, select an element $i$. There are two possibilities for what the remaining placement looks like:

1. If $i<M$, then $i$ had no placement restrictions, so using $i$ does not change the restrictions on any position. We have also removed one position with no restriction, so the remaining placement looks like $g(N-1,M-1)$.

2. If $i>=M$, then $i$ had a placement restriction, and we removed one position with no restriction. Because $i$ is placed, the position it was restricted from now can accept any of the remaining numbers. So the remaining placement looks like $g(N-1,M)$.

So this gives the recursive formula: $$(0<M<N) \implies g(N,M) = (M-1) g(N-1,M-1) + (N-M+1) g(N-1,M)$$

This finishes the recursive solution for $g$.

When $M+P \ge N$, the first $N-M$ positions have a single number restriction on them, the last $N-P$ positions have a single number restriction on them, and the middle $M+P-N$ positions have no restrictions. This is just like the $g(N,M+P-N)$ case.

$$(M+P)\ge N \implies f(N,M,P) = g(N,M+P-N)$$

We have handled all cases currently except $0<M<N$ and $0<P<N$ such that $M+P<N$. This is where some elements have multiple restrictions. Because of the symmetry in $f$, we can consider $0<M\le P<N$ without loss of generality.

The first $P$ positions will have a single restriction, then $N-M-P$ positions with two restrictions, then the last $M$ positions have a single restriction.

Looking at the elements, the first $M$ elements will have a single restriction, then $N-M-P$ elements have two restrictions, then the last $P$ elements have a single restriction.

However this is where we must end. As there is no way forward with this method.

I separated the two constraints because I could see that placing a number in a selected position could unbalance how many single constrained positions there were for the "+" constraint and the "-" constraint of $a-b \ne \pm M$.

But in the more general problem, removing a position by placing a number in it, does not always result in a subproblem that is described with $f(N,M,P)$.

To visualize these constraints on the permutation, consider a directed graph with $2N$ nodes, one set of $N$ labeled $\{A_1,A_2,...,A_N\}$ and another labelled $\{B_1,B_2,...,B_N\}$. A directed edge $(A_i,B_j)$ exists if $i - j = M$, and directed edge $(B_j,A_i)$ exists if $j - i = M$ and $M \ne 0$.

The set of $A$ nodes can be considered the numbers we are permuting in some list, and $B$ nodes their possible positions. This graph represents the constraints. There will be no cycles in the graph. It will always be disjoint nodes or chains of length one or more.

So we want a function which takes as input this constraint graph, and outputs the number of permutations that satisfy the constraints.

In the case where $M+P\ge N$, the graph is just disjoint nodes and single edges. So removing an A and B node will give a subgraph that is also disjoint nodes and single edges.

However for $0<M \le P<N$, the graph can have long chains. To place a number in an available position, regardless of whether we fix the node or the position, we need to consider all the subgraphs of possible ways to build that. All the different ways of breaking up the chains will result in a "recursion" that is on the order of $N$ parts each round, and thus can't expect much if any savings compared to checking all $N!$ permutations.

Because there are so many possible subgraphs once chains are allowed, I really don't see how this can be solved with the usual recursive methods unless there is a clever relation saying how non-isomorphic constraint graphs are somehow equivalent for the number of permutations.

I think most likely, the question was misinterpreted. Possibly even by the interviewer (who may have forgotten the answer details themselves).

• Why is your constraint graph directed? What do the directions mean? – Discrete lizard Apr 14 '17 at 9:09
• @Discretelizard The two directions (a->b vs b->a) distinguish between where the constraint came from (the '+' or the '-' version of the constraint). It's not really needed, because it doesn't matter the origin of the constraint, it just made it easier for me to visualize what was going on. – PPenguin Apr 14 '17 at 16:12