Sha*_*ank 16 algorithm permutation dynamic-programming combinatorics discrete-mathematics
我正在努力有效地解决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).
这个问题的一个子问题以前问这里在计算器上.给出了使用合并排序的O(n log n)解决方案,其计算单个排列中的反转次数.但是,如果我使用该解决方案来计算每个排列的反转次数,我仍然会得到O(n!*n log n)的时间复杂度,在我看来这仍然很高.
之前在Stack Overflow上也提到了这个确切的问题,但它没有收到任何答案.
如果没有数学公式来解决这个问题(我有点怀疑),那么我也看到人们提示有效的动态编程解决方案是可能的.使用DP或其他方法,我真的想制定一个比O(n!*n log n)更有效的解决方案,但我不确定从哪里开始.
欢迎任何提示,评论或建议.
编辑:我已经用DP方法回答了下面的问题来计算Mahonian数.
Vin*_*uri 12
解决方案需要一些解释.让我们用I(n,k)表示n个项具有恰好k反转的排列数
现在我(n,0)总是1.对于任何n,存在一个且只有一个具有0个反转的排列,即,当序列越来越多地排序时
现在我(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(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) = 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;
}
这是一天后,我设法使用动态编程解决问题.我提交了它,我的代码被SPOJ接受了,所以我想我会在这里与任何对未来感兴趣的人分享我的知识.
在查看了关于离散数学反演的维基百科页面之后,我在页面底部找到了一个有趣的建议.
具有k个反转的n个元素的排列数; Mahonian数字:A008302
我点击了OEIS的链接,它向我展示了一个无限的整数序列,称为Mahonian数字的三角形.
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 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,3,1是Mahonian数字的第3行,如下表所示:
1
1 1
1 2 2 1
1 3 5 6 5 3 1
etc.
所以基本上计算我的答案归结为简单地计算第n个Mahonian行并且将k元素从k开始于0并且如果索引超出范围则打印0.这是一个简单的自下而上动态编程的情况,因为每个第i行可用于轻松计算第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()
我不知道时间复杂度,但我绝对肯定这个代码可以通过memoization来改进,因为有10个给定的测试用例,以前的测试用例的计算可以用来"欺骗"未来的测试用例.我将在未来进行优化,但希望今后这个答案将有助于任何人在未来尝试这个问题,因为它避免了生成和迭代所有排列的天真的因子复杂性方法.
如果存在动态编程解决方案,则可能有一种方法可以一步一步地使用长度为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反转的排列数.