恰好具有k个逆序对的n元排列的数量

Question

我正在尝试高效地解决SPOJ Problem 64: Permutations。

设A = [a1,a2,...,an]是整数1,2,...,n的一个排列。若存在一对下标(i,j)，其中1≤i≤j≤n且ai>aj，则称(i,j)是排列A的一个逆序。给定正整数n>0和非负整数k，求包含恰好k个逆序的n元排列的数量。

例如，恰好有1个逆序的4元排列的数量为3。

为了更容易理解上面的示例，以下是恰好包含1个逆序的四元排列的三个例子：

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

在第一个排列中，4>3且4的索引小于3的索引。这是一个单个的逆序对。由于排列恰好有一个逆序对，它是我们要计算的排列之一。

对于任何给定的n个元素的序列，排列的数量是阶乘(n)。因此，如果我使用暴力n^2的方式来计算每个排列的逆序对的数量，然后检查它们是否等于k，那么这个问题的解决方案的时间复杂度将是O(n! * n^2)。

先前的研究

该问题的一个子问题曾在StackOverflow上这里提出过。使用归并排序的O(n log n)解决方案可以计算单个排列中的逆序对数。但是，如果我使用该解决方案来计算每个排列的逆序对数量，我仍然会得到O(n! * n log n)的时间复杂度，我认为这仍然非常高。

这个确切的问题之前也在Stack Overflow上被问过，但没有得到答案。

---

我的目标是避免通过迭代所有排列产生阶乘复杂度。理想情况下，我希望有一个数学公式，可以为任何n和k提供答案，但我不确定是否存在这样的公式。

如果没有数学公式来解决这个问题（我有点怀疑），那么我也看到人们给出了一些提示，表明可以使用高效的动态规划解决方案。使用DP或其他方法，我真的希望制定一种比O（n！* n log n）更有效的解决方案，但我不确定从哪里开始。

欢迎任何提示、评论或建议。

编辑：我已经用DP方法回答了下面的问题Mahonian numbers。

- Shashank

Answer 1

解决方案需要一些解释。我们用I(n, k)表示恰好有k个逆序对的n个项目的排列数。

现在，对于任何n，存在一个且仅存在一个具有0个逆序对的排列，即当序列按递增顺序排序时。

现在I(0, k)始终为0，因为我们没有序列本身。

现在，为了找到I(n, k)，让我们以包含4个元素{1,2,3,4}的序列为例。

对于n = 4，下面是枚举的并按逆序数分组的排列。

|___k=0___|___k=1___|___k=2___|___k=3___|___k=4___|___k=5___|___k=6___|
| 1234    | 1243    | 1342    | 1432    | 2431    | 3421    | 4321    |
|         | 1324    | 1423    | 2341    | 3241    | 4231    |         |
|         | 2134    | 2143    | 2413    | 3412    | 4312    |         |
|         |         | 2314    | 3142    | 4132    |         |         |
|         |         | 3124    | 3214    | 4213    |         |         |
|         |         |         | 4123    |         |         |         |
|         |         |         |         |         |         |         |
|I(4,0)=1 |I(4,1)=3 |I(4,2)=5 |I(4,3)=6 |I(4,4)=5 |I(4,5)=3 |I(4,6)=1 |
|         |         |         |         |         |         |         |

现在我们需要找到n=5时每个可能的k的排列数量。 通过将第n个（最大的）元素（5）插入到前面每个排列中的某个位置中，从而导出I(5, k)的递归公式。 例如，I(5,4)就是序列{1,2,3,4,5}的排列数，其中恰好有4个逆序对。 现在让我们观察I(4, k)，在列k = 4之前的逆序对数量<= 4。 现在让我们按下面所示放置元素5。

|___k=0___|___k=1___|___k=2___|___k=3___|___k=4___|___k=5___|___k=6___|
| |5|1234 | 1|5|243 | 13|5|42 | 143|5|2 | 2431|5| | 3421    | 4321    |
|         | 1|5|324 | 14|5|23 | 234|5|1 | 3241|5| | 4231    |         |
|         | 2|5|134 | 21|5|43 | 241|5|3 | 3412|5| | 4312    |         |
|         |         | 23|5|14 | 314|5|4 | 4132|5| |         |         |
|         |         | 31|5|24 | 321|5|4 | 4213|5| |         |         |
|         |         |         | 412|5|3 |         |         |         |
|         |         |         |         |         |         |         |
|    1    |    3    |    5    |    6    |    5    |         |         |
|         |         |         |         |         |         |         |

以上包含数字5的排列中，每个排列都恰好有4对逆序对。因此，具有4个逆序对的排列总数I(5,4) = I(4,4) + I(4,3) + I(4,2) + I(4,1) + I(4,0)。 = 1 + 3 + 5 + 6 + 5 = 20

同样地，对于I(5,5)，从I(4,k)得到。

|___k=0___|___k=1___|___k=2___|___k=3___|___k=4___|___k=5___|___k=6___|
|   1234  | |5|1243 | 1|5|342 | 14|5|32 | 243|5|1 | 3421|5| | 4321    |
|         | |5|1324 | 1|5|423 | 23|5|41 | 324|5|1 | 4231|5| |         |
|         | |5|2134 | 2|5|143 | 24|5|13 | 341|5|2 | 4312|5| |         |
|         |         | 2|5|314 | 31|5|44 | 413|5|2 |         |         |
|         |         | 3|5|124 | 32|5|14 | 421|5|3 |         |         |
|         |         |         | 41|5|23 |         |         |         |
|         |         |         |         |         |         |         |
|         |    3    |    5    |    6    |    5    |    3    |         |
|         |         |         |         |         |         |         |

因此，具有5个逆序对的总排列数I(5,5) = I(4,5) + I(4,4) + I(4,3) + I(4,2) + I(4,1) = 3 + 5 + 6 + 5 + 3 = 22

因此，I(n, k) = I(n-1, k-i)之和，其中i < n && k-i >= 0

此外，当序列按降序排序时，k可以达到n*(n-1)/2 https://secweb.cs.odu.edu/~zeil/cs361/web/website/Lectures/insertion/pages/ar01s04s01.html http://www.algorithmist.com/index.php/SPOJ_PERMUT1

#include <stdio.h>

int dp[100][100];

int inversions(int n, int k)
{
    if (dp[n][k] != -1) return dp[n][k];
    if (k == 0) return dp[n][k] = 1;
    if (n == 0) return dp[n][k] = 0;
    int j = 0, val = 0;
    for (j = 0; j < n && k-j >= 0; j++)
        val += inversions(n-1, k-j);
    return dp[n][k] = val;
}

int main()
{
    int t;
    scanf("%d", &t);
    while (t--) {
        int n, k, i, j;
        scanf("%d%d", &n, &k);
        for (i = 1; i <= n; i++)
            for (j = 0; j <= k; j++)
                dp[i][j] = -1;
        printf("%d\n", inversions(n, k));
    }
    return 0;
}

- Vineel

---

很好的解释 :) - Kaidul

有没有办法以n log n的时间复杂度来完成它？ - Yasharth Dubey

Answer 2

一天后，我使用动态规划解决了这个问题。我提交了代码，并被SPOJ接受，所以我想在这里分享我的知识，供将来有兴趣的人参考。

在查看离散数学中讨论逆序对的维基百科页面后，我发现了一个有趣的建议，位于页面底部。

n个元素的k个逆序排列的数量；Mahonian数：A008302

我点击了OEIS的链接，它向我展示了一个称为Mahonian数三角形的无限整数序列。

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<4和n>4的答案。

该序列的公式如下：

在展开Product_{i=0..n-1} (1+x+...+x^i)中的系数

这对我来说很容易理解和验证。基本上，我可以取任何n并将其插入到公式中。然后，x^k项的系数将是(n, k)的答案。

我将以n = 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 + 2x2 + x3，其中x的系数分别为0、1、2、1，对应k = 0、1、2、3。这恰好是三个元素排列的所有逆序数的有效数字。

1、2、2、1是Mahonian数的第三行，当它们按以下方式排列成表格时：

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

基本上，计算我的答案归结为简单地计算第n个Mahonian行并取kth元素，其中k从0开始，并在索引超出范围时打印0。这是一种简单的自下而上的动态规划情况，因为每个ith行可以用于轻松计算i + 1st行。

以下是我使用的Python解决方案，仅运行了0.02秒。对于他们给出的测试用例，此问题的最大时间限制为3秒，之前我一直遇到超时错误，因此我认为这种优化相当不错。

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()

我不知道时间复杂度，但我绝对确定这段代码可以通过记忆化进行优化，因为有10个给定的测试用例，先前测试用例的计算结果可以用来“欺骗”未来的测试用例。我将在未来进行该优化，但希望当前状态下的答案能够帮助任何尝试解决这个问题的人，因为它避免了生成并迭代所有排列的天真阶乘复杂度方法。

- Shashank

Answer 3

如果有一个动态规划的解决方案，那么可能有一种逐步完成的方法，利用长度为n的排列的结果来帮助长度为n+1的排列的结果。

给定长度为n的排列-值为1-n，您可以通过在n+1个可能的位置添加值（n+1）来获得长度为n+1的排列。(n+1)大于1-n中的任何一个值，因此当您这样做时创建反转的数量取决于您添加它的位置-在最后一个位置添加它不会创建反转，在倒数第二个位置添加它将创建一个反转，依此类推-回顾一下具有一个反转的n=4个情况以检查这一点。

因此，如果您考虑可以添加(n+1)的n+1个位置中的一个位置，如果您从右侧计数将其添加到位置j，则最后一个位置为位置0，那么创建K个反转的排列的数量就是n个位置上创建K-j个反转的排列的数量。

因此，如果在每个步骤中您计算具有k个反转的所有可能k的排列的数量，您可以使用长度为n的具有k个反转的排列的数量更新长度为n+1的具有k个反转的排列的数量。

- mcdowella

---

我认为你的答案相当于使用动态规划计算展开式Product_{i=0..n-1} (1+x+...+x^i)的系数，以便第n行的结果可以用来计算第n+1行的结果。如果您感兴趣，请随时查看我的答案。我给了你+1. :) - Shashank

我还没有检查过你的答案，但我一点也不会感到惊讶。在http://algo.inria.fr/flajolet/Publications/book.pdf上有一本可下载的书，声称可以通过生成函数教你解决大量像这样的问题，但我还没有找到时间或动力去学习它。 - mcdowella

Answer 4

计算这些系数的一个主要问题是结果乘积的阶数很大。多项式Product i=1,2,..,n {(1+x).(1+x+x^2)....(1+x+x^2+..+x^i)+...(1+x+x^2+...+x^n)} 的阶数相当于n*(n+1)。因此，这对过程施加了限制性的计算限制。如果我们使用一个过程，在计算n的Product的过程中使用n-1的Product的先前结果，我们需要存储(n-1)*n个整数。可以使用递归过程，但速度会慢得多，并且仍然受到小于整数公共大小平方根的限制。以下是一些粗略的递归代码。函数mahonian(r,c)返回r个Product的第c个系数。但是，对于大于100左右的大型Product，它非常缓慢。运行此代码可以看出，递归显然不是答案。

unsigned int numbertheory::mahonian(unsigned int r, unsigned int c)
  {
      unsigned int result=0;
      unsigned int k;

     if(r==0 && c==0)
       return 1;
     if( r==0 && c!=0)
      return 0;

   for(k=0; k <= r; k++)
       if(r > 0 && c >=k)
           result = result + mahonian(r-1,c-k);

   return result;

}

顺便提一下，我包含了以下内容，这是Sashank的C++版本，比我的递归示例快得多。请注意，我使用了armadillo库。

uvec numbertheory::mahonian_row(uword n){
 uword i = 2;
 uvec current;
 current.ones(i);
 uword current_size;
 uvec prev;
 uword prev_size;

 if(n==0){
   current.ones(1);
   return current;
 }

 while (i <= n){                  // increment through the rows
   prev_size=current.size();     // reset prev size to current size
   prev.set_size(prev_size);     // set size of prev vector
   prev= current;                //copy contents of current to prev vector
   current_size =1+ (i*(i+1)/2);      // reset current_size
   current.zeros(current_size);    // reset current vector with zeros

   for(uword j=0;j<i+1; j++)       //increment through current vector
      for(uword k=0; k < prev_size;k++)
         current(k+j) += prev(k);
   i++;                                        //increment to next row
}
return current;                                //return current vector
 }

 uword numbertheory::mahonian_fast(uword n, uword c) {
**This function returns the coefficient of c order of row n of
**the Mahonian numbers
    // check for input errors
    if(c >= 1+ (n*(n+1)/2)) {
        cout << "Error. Invalid input parameters" << endl;
   }
   uvec mahonian;
   mahonian.zeros(1+ (n*(n+1)/2));
   mahonian = mahonian_row(n);
   return mahonian(c);
 }

- Paul Mackenzie

Answer 5

我们可以利用动态规划来解决这个问题。我们有n个位置需要填入从1到n的数字，_ _ _ _ _ _ _ 以n=7为例，那么在第一个位置上，我们最多可以达到n-1个逆序对，最少为0个，同样地，在第二个位置上，我们最多可以达到n-2个逆序对，最少为0个，一般地，无论我们放置什么数字，我们都可以在第i个位置上最多达到n-i个逆序对。

我们的递归公式如下：

f(n,k) = f(n-1,k) + f(n-1,k-1) + f(n-1,k-2) ............. f(n-1,max(0,k-(n-1)) 无逆序对 一个逆序对 两个逆序对 n-1个逆序对 我们可以通过在剩余数字集合中放置最小的数字（1，n）来实现0个逆序对，通过放置第二小的数字等等来实现1个逆序对。

我们递归公式的基本条件是：

如果(i==0 && k==0)，则返回1（有效排列）

如果(i==0 && k!=0)，则返回0（无效排列）。

如果我们画出递归树，就会发现子问题被多次重复，因此使用记忆化来将复杂度降低到O(n*k)。

- Singh Ajaypal Attal