n元素的排列数与k个反转 [英] Number of n-element permutations with exactly k inversions

问题描述

我试图有效地解决 SPOJ问题64：置换

设A = [A1，A2，...，一]是整数的一个排列1,2，...，N。一双   指数（I，J），1＆LT的; = I＆LT; = J＆LT; = N，是变位的，如果的反转   AI> AJ。我们给出整数n> 0和k> = 0。什么是数   正元含k个颠倒排列？

Let A = [a1,a2,...,an] be a permutation of integers 1,2,...,n. A pair of indices (i,j), 1<=i<=j<=n, is an inversion of the permutation A if ai>aj. We are given integers n>0 and k>=0. What is the number of n-element permutations containing exactly k inversions?

有关实例，4-元件排列与完全1数   反转等于3。

For instance, the number of 4-element permutations with exactly 1 inversion equals 3.

为使给出的例子更容易看到，这里有3个4元排列恰好有1反转：

To make the given example easier to see, here are the three 4-element permutations with exactly 1 inversion:

(1, 2, 4, 3)
(1, 3, 2, 4)
(2, 1, 3, 4)

在第一置换，4> 3和4的指数小于3的指数这是一个单翻转。由于置换都只有一个反转，这是我们正试图算排列之一。

In the first permutation, 4 > 3 and the index of 4 is less than the index of 3. This is a single inversion. Since the permutation has exactly one inversion, it is one of the permutations that we are trying to count.

有关任何给定的n个元素的序列，置换的数量是阶乘（n）的。因此，如果我用的是蛮力力N ^{计数反转为每个排列的号码，然后检查，看看它们是否等于k 2} 的方式，解决这一问题将有足够的时间复杂度为O（ N！* N ² ）。

---

For any given sequence of n elements, the number of permutations is factorial(n). Thus if I use the brute force n² way of counting the number of inversions for each permutation and then checking to see if they are equal to k, the solution to this problem would have the time complexity O(n! * n²).

---

此问题的一个子问题是previously问<一href="http://stackoverflow.com/questions/6523712/calculating-the-number-of-inversions-in-a-permutation">here在计算器。为O（n log n）的使用合并排序已经给它计算的倒在的单的置换数量的解决方案。不过，如果我使用的解决方案来算倒了每个排列的号码，我仍然会得到Ø的时间复杂度（N！* N日志N），这仍然是非常高的，我认为。

A subproblem of this problem was previously asked here on StackOverflow. An O(n log n) solution using merge sort was given which counts the number of inversions in a single permutation. However, if I use that solution to count the number of inversions for each permutation, I would still get a time complexity of O(n! * n log n) which is still very high in my opinion.

这<一href="http://stackoverflow.com/questions/17504758/number-of-permutation-with-exact-k-inversions">exact问题还要求pviously堆栈溢出$ P $，但没有得到任何答复。

---

我的目标是避免来自通过所有排列迭代的阶乘的复杂性。我非常希望能够产生这个问题的答案对任何n和k的数学公式，但我不确定如果存在的话。

---

My goal is to avoid the factorial complexity that comes from iterating through all permutations. Ideally I would like a mathematical formula that yields the answer to this for any n and k but I am unsure if one even exists.

如果没有数学公式来解决这个（这我有点怀疑），那么我也看到有人给出提示，一个有效的动态规划的解决方案是可能的。使用DP或另一种方法，我真的想制定一个解决方案，是为O效率更高（N！* N log n）的，但我不能确定从哪里开始。

If there is no math formula to solve this (which I kind of doubt) then I have also seen people giving hints that an efficient dynamic programming solution is possible. Using DP or another approach, I would really like to formulate a solution which is more efficient than O(n! * n log n), but I am unsure of where to start.

任何提示，意见或建议，欢迎。

Any hints, comments, or suggestions are welcome.

编辑：我刚才已经回答下面的问题，一个DP的计算方法 Mahonian号

I have answered the problem below with a DP approach to computing Mahonian numbers.

推荐答案

这是一天过去了，我已成功地解决了使用动态规划的问题。我提交了它和我的code的接受了SPOJ所以我想我会在这里分享我的知识的人谁是有兴趣在未来。

It's one day later and I have managed to solve the problem using dynamic programming. I submitted it and my code was was accepted by SPOJ so I figure I'll share my knowledge here for anyone who is interested in the future.

在看在维基百科页面，其中讨论了反向离散数学，我发现在页面底部一个有趣的建议。

After looking in the Wikipedia page which discusses inversion in discrete mathematics, I found an interesting recommendation at the bottom of the page.

n个元素用K反转的排列数; Mahonian   数字： A008302

Numbers of permutations of n elements with k inversions; Mahonian numbers: A008302

我点击链接OEIS 而事实证明，我的整数的无限序列称为Mahonian号的三角

I clicked on the link to OEIS and it showed me an infinite sequence of integers called the Triangle of Mahonian numbers.

1，1，1，1，2，2，1，1，3，5，6，5,3，1，1，4，9，15，20，22，20，15，   9，4，1，1，5，14，29，49，71，90，101，101，90，71，49，29，14，5，1，   1，6，20，49，98，169，259，359，455，531，573，573，531，455，359，   259，169，98，49，20，6，1。 。

1, 1, 1, 1, 2, 2, 1, 1, 3, 5, 6, 5, 3, 1, 1, 4, 9, 15, 20, 22, 20, 15, 9, 4, 1, 1, 5, 14, 29, 49, 71, 90, 101, 101, 90, 71, 49, 29, 14, 5, 1, 1, 6, 20, 49, 98, 169, 259, 359, 455, 531, 573, 573, 531, 455, 359, 259, 169, 98, 49, 20, 6, 1 . . .

我很好奇这些数字是因为它们似乎耳熟。后来我才意识到，我以前见过的序列1，3，5，6，5，3，1。事实上，这是的答案为几对的（N，K），即问题（4,0），（4,1），（4，2），（4，3），（4，4） ，（4,5），（4,6）。我看了看什么是在这个序列的两侧，很惊讶地看到，这是所有有效的（即大于0的排列）的答案对于n＆LT; 4和n> 4。

I was curious about what these numbers were since they seemed familiar to me. Then I realized that I had seen the subsequence 1, 3, 5, 6, 5, 3, 1 before. In fact, this was the answer to the problem for several pairs of (n, k), namely (4, 0), (4, 1), (4, 2), (4, 3), (4, 4), (4, 5), (4, 6). I looked at what was on both sides of this subsequence and was amazed to see that it was all valid (i.e. greater than 0 permutations) answers for n < 4 and n > 4.

的公式序列给出：

在扩张Product_系数{I = 0到n-1}（1 + X + ... + X ^ I）

coefficients in expansion of Product_{i=0..n-1} (1+x+...+x^i)

这是很容易让我了解和核实。我基本上可以采取任何n和插入公式。然后该系数用于x ^K 术语将是（N，K）的答案。

This was easy enough for me to understand and verify. I could basically take any n and plug into the formula. Then the coefficient for the x^k term would be the answer for (n, k).

我将展示对n为例= 3。

I will show an example for n = 3.

（X 0 ）（X 0 + 1 ）（X 0 + X 1 + X 2 ） =（1）（1 + X）（1 + X + X 2 ） =（1 + X）（1 + X + X 2 ） = 1 + X + X + X 2 + X 2 + X 3 = 1 + 2×2×+ 2 + X 3

(x0)(x0 + 1)(x0 + x1 + x2) = (1)(1 + x)(1 + x + x2) = (1 + x)(1 + x + x2) = 1 + x + x + x2 + x2 + x3 = 1 + 2x + 2x2 + x3

最后的扩张是 1 + 2X + 2X 2 + X 3 和的x <系数SUP> K 术语分别为1,2，2和1对于k = 0，1，2，3。这恰恰是反向的所有有效数为3元置换。

The final expansion was 1 + 2x + 2x2 + x3 and the coefficients of the x^k terms were 1, 2, 2, and 1 for k = 0, 1, 2, 3 respectively. This just happens to be all valid numbers of inversions for 3-element permutations.

1，2，2，1是Mahonian号码的第三行，当它们被布置在表中，如下所示：

1, 2, 2, 1 is the 3rd row of the Mahonian numbers when they are laid out in a table as follows:

1
1 1
1 2 2 1
1 3 5 6 5 3 1
etc.

所以基本上计算我的答案归结为简单地计算第n Mahonian行，并采取具有k从0开始打印0，如果该指数超出范围的第k个元素。这是自下而上动态编程的一个简单的例子，因为每个第i行可以用来很容易地计算第i + 1行

So basically computing my answer came down to simply calculating the nth Mahonian row and taking the kth element with k starting at 0 and printing 0 if the index was out of range. This was a simple case of bottom-up dynamic programming since each ith row could be used to easily compute the i+1st row.

下面给出了Python的解决方案，我用跑的只有0.02秒。的最大时间限制针对此问题为3秒，他们给出测试用例和我正在超时错误，所以我觉得这个优化是相当不错的。

Given below is the Python solution I used which ran in only 0.02 seconds. The maximum time limit for this problem was 3 seconds for their given test cases and I was getting a timeout error before so I think this optimization is rather good.

def mahonian_row(n):
    '''Generates coefficients in expansion of 
    Product_{i=0..n-1} (1+x+...+x^i)
    **Requires that n is a positive integer'''
    # Allocate space for resulting list of coefficients?
    # Initialize them all to zero?
    #max_zero_holder = [0] * int(1 + (n * 0.5) * (n - 1))

    # Current max power of x i.e. x^0, x^0 + x^1, x^0 + x^1 + x^2, etc.
    # i + 1 is current row number we are computing
    i = 1
    # Preallocate result
    # Initialize to answer for n = 1
    result = [1]
    while i < n:
        # Copy previous row of n into prev
        prev = result[:]
        # Get space to hold (i+1)st row
        result = [0] * int(1 + ((i + 1) * 0.5) * (i))
        # Initialize multiplier for this row
        m = [1] * (i + 1)
        # Multiply
        for j in range(len(m)):
            for k in range(len(prev)):
                result[k+j] += m[j] * prev[k]
        # Result now equals mahonian_row(i+1)
        # Possibly should be memoized?
        i = i + 1
    return result


def main():
    t = int(raw_input())
    for _ in xrange(t):
        n, k = (int(s) for s in raw_input().split())
        row = mahonian_row(n)
        if k < 0 or k > len(row) - 1:
            print 0
        else:
            print row[k]


if __name__ == '__main__':
    main()

我不知道的时间复杂度，但我肯定这code可以通过得到改善记忆化因为有10个给出测试用例和计算为previous测试用例可以用在未来的测试案例，以欺骗。我将在今后的优化，但希望在其当前状态这个答案将有助于任何人试图在未来的这个问题，因为它避免了产生，并通过所有排列迭代的天真的阶乘复杂性的方法。

I have no idea of the time complexity but I am absolutely certain this code can be improved through memoization since there are 10 given test cases and the computations for previous test cases can be used to "cheat" on future test cases. I will make that optimization in the future, but hopefully this answer in its current state will help anyone attempting this problem in the future since it avoids the naive factorial-complexity approach of generating and iterating through all permutations.

这篇关于n元素的排列数与k个反转的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！