# HackerRank Swap Permutation problem solution

In this HackerRank Swap Permutation problem solution we have given an array A = [1, 2, 3, ..., n]:

1. How many sequences (S1) can you get after exact k adjacent swaps on A?
2. How many sequences (S2) can you get after at most k swaps on A?

An adjacent swap can be made between two elements of the Array A, A[i] and A[i+1] or A[i] and A[i-1]. A swap otherwise can be between any two elements of the array A[i] and A[j] ∀ 1 ≤ i, j ≤ N, I ≠ j.

## Problem solution in Python.

```#!/bin/python3

import os
import sys

#
# Complete the swapPermutation function below.
#
def swapPermutation(n, k):
#
#
mod = 1000000007
s = [1] + [0] * k
t = [1] + [0] * k
for i in range(1, n):
temp = sum(s[max(k - i, 0):k]) % mod
for j in range(k, 0, -1):
s[j] = (s[j] + temp) % mod
if j > i:
temp = (temp + s[j - i - 1] - s[j - 1]) % mod
else:
temp = (temp - s[j - 1]) % mod
for j in range(k, 0, -1):
t[j] = (t[j] + i * t[j - 1]) % mod
return sum(s[k % 2::2]) % mod, sum(t) % mod

if __name__ == '__main__':
fptr = open(os.environ['OUTPUT_PATH'], 'w')

nk = input().split()

n = int(nk[0])

k = int(nk[1])

result = swapPermutation(n, k)

fptr.write(' '.join(map(str, result)))
fptr.write('\n')

fptr.close()
```

{"mode":"full","isActive":false}

## Problem solution in Java.

```import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.function.*;
import java.util.regex.*;
import java.util.stream.*;
import static java.util.stream.Collectors.joining;
import static java.util.stream.Collectors.toList;

class Result {

public static List<Integer> swapPermutation(int n, int k) {
long [][] dp0 = new long[n + 1][k + 1];
long [][] sum0 = new long[n + 1][k + 2];
int mod = 1000000007;
for(int i = 0; i < n + 1; i++) dp0[i][0] = 1L;
for(int i = 1; i < k + 2; i++) sum0[1][i] = sum0[1][i - 1] + dp0[1][i - 1];
for(int i = 1; i < n + 1; i++) sum0[i][1] = 1L;

for(int i = 2; i <= n; i++){
for(int j = 1; j <= k; j++){
int head = Math.max(0, j - i + 1);
dp0[i][j] = sum0[i - 1][j + 1] - sum0[i - 1][head];
sum0[i][j + 1] = (sum0[i][j] + dp0[i][j]) % mod;
}
}

long ans1 = 0L;
for(int i = k; i >= 0; i -= 2) ans1 = (ans1 + dp0[n][i]) % mod;

long [][] dp1 = new long[n + 1][k + 1];

for(int i = 0; i <= n; i++) dp1[i][0] = 1L;
for(int i = 2; i <= n; i++){
for(int j = 1; j <= k; j++){
dp1[i][j] = (dp1[i - 1][j] + ((i - 1) * dp1[i - 1][j - 1]) % mod) % mod;
}
}
long ans2 = 0L;

for(int i = 0; i <= k; i++) ans2 = (ans2 + dp1[n][i]) % mod;
List<Integer> ans = new ArrayList<>();

return ans;
}

}

public class Solution {
public static void main(String[] args) throws IOException {
BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

int n = Integer.parseInt(firstMultipleInput[0]);

int k = Integer.parseInt(firstMultipleInput[1]);

List<Integer> result = Result.swapPermutation(n, k);

bufferedWriter.write(
result.stream()
.map(Object::toString)
.collect(joining(" "))
+ "\n"
);

bufferedWriter.close();
}
}
```

{"mode":"full","isActive":false}

## Problem solution in C++.

```#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

uint64_t mod = 1000000007;
uint64_t **dyn_anyswap;

int nsz = 2550;
int ksz = 2550;

{

for(int n=2; n<nsz; n++)
{
if(n==2){
continue;
}
for(int k=0; k<ksz-1; k++)
{
}
}
}

void generate_anyswap()
{
dyn_anyswap = new uint64_t*[nsz];

for(int n=2; n<nsz; n++)
{
dyn_anyswap[n]=new uint64_t[ksz];
if(n==2){
for(int k=0; k<ksz;k++) dyn_anyswap[n][k]=1;
continue;
}
dyn_anyswap[n][0] = 1;
for(int k=1; k<ksz; k++)
{
dyn_anyswap[n][k] = dyn_anyswap[n-1][k] + (n-1)*dyn_anyswap[n-1][k-1];
dyn_anyswap[n][k] %= mod;
}
}
}

{
}

uint64_t anyswap_atmost(int n, int k)
{
return (dyn_anyswap[n][k]+dyn_anyswap[n][k-1]) % mod;
}

int main() {
/* Enter your code here. Read input from STDIN. Print output to STDOUT */
generate_anyswap();

int n, k;
cin >> n >> k;
cout << adjswap(n,k) << " " << anyswap_atmost(n,k) << endl;
}
```

{"mode":"full","isActive":false}

## Problem solution in C.

```#include <assert.h>
#include <limits.h>
#include <math.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define min(X,Y) (X>Y)?Y:X
#define f(i,a,b) for(int i = (a); i <= (b); i++)

typedef long long ll;

const ll MOD = 1000000007;
int N, K;
ll A[2505][2505], T[2505], B[2505][2505];

void update1(int x, ll v)
{
while(x <= 2501)
{
T[x] = (T[x]+v) % MOD;
x += x&-x;
}
}

void update2(int l, int r, ll v)
{
l++, r++;
update1(l,v), update1(r+1,-v);
}

ll query(int x)
{
x++;
ll ret = 0;
while(x>0)
{
ret = (ret+T[x]) % MOD;
x -= x&-x;
}
return ret;
}

int main()
{

A[1][0] = 1;
f(i,1,2499)
{
f(j,0,2500) update2(j,min(j+i,2500),A[i][j]);
f(j,0,2500) A[i+1][j] = query(j);
f(j,0,2501) T[j] = 0;
}

B[1][1] = 1;
f(i,1,2499) f(j,1,i)
{
B[i+1][j+1] = (B[i+1][j+1] + B[i][j]) % MOD;
B[i+1][j] = (B[i+1][j] + B[i][j]*i) % MOD;
}

int N;
int K;
scanf("%d",&N);
scanf("%d",&K);
ll ans = 0, ans2 = 0;
for(int j = K; j >= 0; j -= 2) ans += A[N][j];
f(i,0,min(K,N-1)) ans2 += B[N][N-i];
ll a1 = ans%MOD;
ll a2 = ans2%MOD;
printf("%lld %lld\n",a1,a2);
}
```

{"mode":"full","isActive":false}