patternMinor
Counting permutations whose elements are not exactly their index ± M
Viewed 0 times
countingwhoseelementsareexactlyindexnottheirpermutations
Problem
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.
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.
Solution
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.
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.
Context
StackExchange Computer Science Q#73681, answer score: 2
Revisions (0)
No revisions yet.