Permutation Cycles in 2D Grid

Правка en3, от BumbleBee, 2020-05-08 15:55:56

I have a 2D grid containing $$$n$$$ rows and $$$m$$$ columns. I can swap any two rows or any two columns any number of times (possibly zero). By swapping some rows or columns I can get different permutations of this grid. Lets's call permutations that can be achieved this way valid permutations. You can see that there are $$$n!m!$$$ valid permutations.

We know that each permutation can be represented as a product of $$$1$$$ or more disjoint cycles. For each integer $$$k$$$ in the range $$$[1, nm]$$$, I want to calculate the number of valid permutations that have exactly $$$k$$$ cycles. The bruteforce approach is iterating over all $$$n!m!$$$ possible permutations of the grid and counting cycles in each of them, which is a very slow solution and takes $$$O(n!m!nm)$$$ time. I want to find a more efficient solution (maybe dynamic programming or some combinatorial formula).

Constraints on $$$n$$$ and $$$m$$$ are not fixed. How to calculate this in a more efficient way?

Теги #dp, #combinatorics, #grid, #permutation, #cycle

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en3 Английский BumbleBee 2020-05-08 15:55:56 45
en2 Английский BumbleBee 2020-05-08 15:46:40 3 Tiny change: 'es $O(n!m!(n+m))$ time. I' -> 'es $O(n!m!nm)$ time. I'
en1 Английский BumbleBee 2020-05-08 15:17:19 983 Initial revision (published)