20

我正在尝试有效地解决SPOJ 问题 64：排列。

令 A = [a1,a2,...,an] 是整数 1,2,...,n 的排列。如果 ai>aj，则一对索引 (i,j) 1<=i<=j<=n 是排列 A 的反转。我们得到整数 n>0 和 k>=0。恰好包含 k 个反转的 n 元素排列的数量是多少？

例如，恰好有 1 个反转的 4 元素排列的数量等于 3。

为了使给定的示例更易于查看，这里是三个 4 元素排列，正好有 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) 更有效的解决方案，但我不确定从哪里开始。

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

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

4

5 回答 5

17

解决方案需要一些解释。让我们用 I(n, k) 来表示 n 项恰好有 k 个反转的排列数

现在 I(n, 0) 始终为 1。对于任何 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（4，k）推导出递归 I（5，k）先前的排列，因此得到的反转次数为 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(4,k) 的 I(5,5)

|___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) = sum of I(n-1, k-i) such that 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;
}
于 2014-09-09T14:33:22.520 回答
9

一天后，我设法使用动态编程解决了这个问题。我提交了它，我的代码被 SPOJ 接受了，所以我想我会在这里为任何对未来感兴趣的人分享我的知识。

在查看讨论离散数学中的反演的 Wikipedia 页面后，我在页面底部发现了一个有趣的建议。

具有 k 个反转的 n 个元素的排列数；马洪数字：A008302

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

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)。我查看了这个子序列两边的内容，惊讶地发现对于 n < 4 和 n > 4，它们都是有效的（即大于 0 个排列）答案。

序列的公式如下：

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

对于 k = 0、1、2、3， x k项的最终展开系数分别为 1、2、2 和 1。这恰好是 3 元素排列的所有有效反转数。1 + 2x + 2x2 + x3

1, 2, 2, 1 是 Mahonian 数的第 3 行，当它们按如下方式排列时：

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

所以基本上计算我的答案归结为简单地计算第 n 个 Mahonian 行，并从 k 开始取第 k 个元素，如果索引超出范围，则打印 0。这是一个自底向上动态规划的简单案例，因为每一行都可以用来轻松计算第 i+1 行。

下面给出的是我使用的 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 个给定的测试用例，并且以前的测试用例的计算可以用来“欺骗”未来的测试用例。我将在未来进行优化，但希望当前状态下的这个答案将帮助任何人在未来尝试这个问题，因为它避免了生成和迭代所有排列的天真的阶乘复杂性方法。

于 2013-10-16T00:48:37.340 回答
6

如果有动态规划解决方案，可能有一种方法可以逐步完成，使用长度为 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 个位置上具有 Kj 反转的排列。

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

于 2013-10-15T04:53:31.630 回答
0

我们可以利用动态规划来解决这个问题。我们有 n 个地方可以填充从 1 到 n 的数字，_ _ _ _ _ _ 取 n=7，那么在第一个地方我们可以实现最多 n-1 反转和至少 0 ，同样对于第二个地方我们可以实现最多 n-2 次反转且至少为 0，一般而言，我们可以在第 i 个索引处实现最多 ni 次反转，而与我们之前放置的数字的选择无关。我们的递归公式将如下所示：

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)) 无反演 1 反演 2 反演 n-1 反演 我们可以通过将集合 (1,n) 中剩余数字中的最小值放入 1 反演来实现 0 反演通过放置第二小的等等，

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

if( i==0 && k==0 ) 返回 1（有效排列）

if( i==0 && k!=0 ) 返回 0（无效排列）。

如果我们绘制递归树，我们将看到子问题重复多次，因此使用记忆化将复杂度降低到 O(n*k)。

于 2018-10-28T18:18:49.473 回答
-1

计算这些系数的一个主要问题是结果乘积的阶数。多项式积 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-1 的 Product 的先前结果用于计算 n 的 Product 的过程，我们正在查看 (n-1)*n 整数的存储。可以使用递归过程，这将慢得多，并且再次限制为小于整数公共大小的平方根的整数。以下是针对此问题的一些粗略且现成的递归代码。函数 mahonian(r,c) 返回第 r 个产品的第 c 个系数。但是对于大于 100 左右的大型产品来说，它又是极其缓慢的。运行这个可以看出递归显然不是答案。

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++ 版本，它比我的递归示例快得多。注意我使用犰狳库。

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);
 }
于 2017-08-31T23:28:52.110 回答