Swap Permutation

78 阅读 0 评论 52 点赞

我是靠谱客的博主秀丽草丛，最近开发中收集的这篇文章主要介绍Swap Permutation，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

给你一个数组A = [1, 2, 3, ..., n]:

对A进行好恰好k次相邻交换，你能得到多少个不同的序列 (S1)?
对A进行最多k次交换，你能得到多少个不同的序列 (S1)?

一次相邻交换是指交换数组A中两个相邻位置的元素，即A[i]和A[i+1]或者A[i]和A[i-1]。一次交换是指交换数组A中的任意两个位置不同的元素，即 A[i]和A[j] ∀ 1 ≤ i, j ≤ N, i ≠ j。

输入格式
仅有一行包含空格分隔的n和k。

输出格式
在一行中输出S1 % MOD 和 S2 % MOD，其中MOD = 1000000007。

约束条件
1 ≤ n ≤ 2500
1 ≤ k ≤ 2500

输入样例

3 2

输出样例

3 6

解释

原始数组: [1, 2, 3]
1. 经过两次相邻交换:
我们得到 [1, 2, 3], [2, 3, 1], [3, 1, 2] ==> S1 == 3

2. 经过最多两次交换:
1) 0次交换后: [1, 2, 3]
2) 1次交换后: [2, 1, 3], [3, 2, 1], [1, 3, 2].
3) 两次交换后: [1, 2, 3], [2, 3, 1], [3, 1, 2]
==> S2 == 6

https://www.hackerrank.com/challenges/swappermutation/problem

http://codeforces.com/blog/entry/47593

第一部分：交换相邻的k次，说明最后的逆序对可能是k,k-2,k-4,......，DP求解，dp[i][j]表示到使用1-i的数，有j个逆序，naive的状态转移写出来是NNN，

dp[i][j]=sum(dp[i-1][k]) k=0..i-1

因为有区间求和，用线段树可以NNlogN（又是可以用线段树优化，感觉ACM就是知道的数据结构多了，暴力不过，用个数据结构"暴力"优化下）。其实可以做到NN，就是写出dp[i][j]和dp[i][j+1]的状态转移方程，两者做差可以返现规律

dp1[i][j]=dp1[i][j-1]+dp1[i-1][j]
if j-i>=0: dp1[i][j]-=dp1[i-1][j-i]

LC有类似的题

第二部分：任意交换，逆序对就不work了，但是可以从环的角度思考，一开始有n个环，如果swap的2个数在同一个环内，则相当于把一个大环拆成2个小环；而如果swap的2个数不在同一个环内，相当于2个小环合并为1个大环，比如：

交换2,4，这样本来2指向的是3，变成了4指向的1

所以最后swap k次后最小有n-k个环，然后DP求解所有可能，dp[i][j]表示：使用1-i的数，有j个环，使用i时，i可以自成一环，也可以和1-i-1的数一起在一个环了，所以状态转移方程：

dp[i][j]=dp[i-1][j-1]+dp[i-1][j]*(i-1)

mod=10**9+7

def helper1(n, k):
    dp1=[[0 for _ in range(k+1)] for _ in range(n+1)]
    for i in range(1,n+1): dp1[i][0]=1
    for i in range(2,n+1):
        for j in range(1,k+1):
            dp1[i][j]=dp1[i][j-1]+dp1[i-1][j]
            if j-i>=0: dp1[i][j]-=dp1[i-1][j-i]
            dp1[i][j]%=mod
    return sum(dp1[n][kk] for kk in range(k,-1,-2))%mod
    
def helper2(n, k):
    dp2=[[0 for _ in range(n+1)] for _ in range(n+1)]
    dp2[1][1]=1
    for i in range(1,n):
        for j in range(1,i+1):
            dp2[i+1][j+1]=(dp2[i+1][j+1]+dp2[i][j])%mod
            dp2[i+1][j]=(dp2[i+1][j]+dp2[i][j]*i)%mod
    return sum(dp2[n][kk] for kk in range(max(n-k,0),n+1))%mod


def swapPermutation(n, k):
    return '%d %d'%(helper1(n,k), helper2(n,k))


if __name__ == '__main__':
    nk = input().split()
    n = int(nk[0])
    k = int(nk[1])
    result = swapPermutation(n, k)
    print(result)

Very nice problem. I'll explain my solution.

First part: When we swap adjacent elements, we are either creating a new inversion or removing one. If we make K adjacent swaps, we'll end up with at most K inversions and the total number of inversions will have the same parity as K. To calculate this, we can use bottom-up DP. Let Ai, j be the amount of arrays of length i with j inversions. Suppose we are at state i, j and we want to add element i + 1 to the current array. We have i + 1 positions to choose from, and each position will create one inversion more than the position to its right. If we push it to the back of the array, we won't create any new inversion, and if we push it to the front of the array, we'll be creating i new inversions. So we will need to add Ai, j to all elements Ai, k with k in the range [j, j + i]. This process is O(n3) if done naively, so if we want it to run in time, we will need to use a BIT to do range additions.
Second part: A permutation can be seen as a collection of cycles. The identity permutation (1,2,3,4,...,N) has N cycles. When we swap two elements, if they belong to the same cycle, we'll be dividing this cycle into two cycles, and if they belong to different cycles, we'll be merging them. So, we are either creating a new cycle or removing one cycle by merging two different cycles. If we make at most K swaps in total, we will have at least N - K cycles in the end. To calculate this, we can use bottom-up DP too. Let Bi, j be the amount of permutations of length i with j cycles. Suppose we are at state i, j and we want to add element i + 1. We have two choices here, the first one being to point it to itself, creating a new cycle, and the second choice to point it to some previous element (making that previous element point to the new one in the process), effectively extending one existing cycle's length by 1. We have i positions for the second choice, so we have to add Bi, j to Bi + 1, j + 1 and Bi, j * i to Bi + 1, j. This process is O(N2), so we don't need any special data structure.