Algorithm
Problem Name: Data Structures -
https://www.hackerrank.com/challenges/find-the-permutation/problem?isFullScreen=true
In this HackerRank in Data Structures -
In this HackerRank Find the Permutation problem solution we are given a permutation pi of integers from 1 to n. we need to generate a lexicographically sorted list of all permutations of length n having a maximal distance between all permutations of the same length. Print the lexicographically kth permutation.
Code Examples
#1 Code Example with C Programming
Code -
C Programming
#include<stdio.h>
#include<stdlib.h>
static const unsigned long long one = 1;
static unsigned long long * solution;
unsigned long long n, k;
void solve2I(unsigned long long r)
{
unsigned long long sf = n - 2 * r - 1;
unsigned long long sb = n - 1;
unsigned long long s2 = 2;
for( unsigned long long i = 0 ; i < r ; ++i )
{
unsigned long long p2 = ( one << ( r - i - 1 ) );
if( k < p2 )
{
solution[sf] = n / 2 + s2 + i;
solution[sf + 1] = s2 + i;
sf += 2;
}
else
{
k -= p2;
solution[sb] = n / 2 + s2 + i;
solution[sb - 1] = s2 + i;
sb -= 2;
}
}
solution[sf] = n / 2 + s2 + r;
}
void solveTwo()
{
unsigned long long m = ( one << ( n / 2 - 1 ) >;
if( k >= m )
{
k = 2 * m - 1 - k;
solveTwo();
for( size_t i = 0 ; i < n ; ++i )
{
solution[i] = n + 1 - solution[i];
}
return;
}
solution[0] = ( n / 2 ) + 1;
solution[1] = 1;
solve2I(n/2 - 1);
}
void SolveOne()
{
unsigned long long *used = (unsigned long long*)malloc(( n + 2 ) * sizeof(unsigned long long));
for( unsigned long long i = 0 ; i < n + 2 ; i++ )
{
used[i] = 0;
}
unsigned long long p = 0;
for( ; ; )
{
if( k == 0 >
{
solution[p++] = 1;
for( size_t i = n / 2 + 1 ; i > 1 ; --i )
{
if(!used[i])
{
solution[p++] = i;
solution[p++] = i + n / 2;
}
}
return;
}
if( k == 1 )
{
size_t i1 = 1;
size_t i2 = n / 2 + 2;
for( ; p < n - 1 ; )
{
for( ; used[i1] ; ++i1 );
for( ; used[i2] ; ++i2 );
solution[p++] = i1++;
solution[p++] = i2++;
}
solution[p++] = n / 2 + 1;
return;
}
unsigned long long s = 2;
k -= s;
for( unsigned long long i = 0 ; ; ++i )
{
if( k < s )
{
solution[p++] = i + 2;
solution[p++] = i + 2 + n / 2;
used[i + 2] = 1;
used[i + 2 + n / 2] = 1;
break;
}
k -= s;
size_t p2 = ( one << i );
if( k < p2 )
{
size_t i1 = i + 2;
size_t i2 = n / 2 + i1 + 1;
for( ; ; )
{
for( ; used[i1] ; ++i1 );
if( i1 == ( n / 2 + 1 ) )
{
break;
}
for( ; used[i2] ; ++i2 );
solution[p++] = i1++;
solution[p++] = i2++;
}
solution[p++] = i1;
solution[p++] = 1;
solve2I(i);
return;
}
k -= p2;
s = 2 * s + p2;
}
}
}
int AdjustPlace()
{
unsigned long long t = k;
unsigned long long n0 = 2;
if( t < n0 )
{
return 1;
}
unsigned long long s = n0;
t -= s;
for( unsigned long long i = 0 ; i < n / 2 - 1 ; ++i )
{
unsigned long long p2 = ( one << i );
if( t < ( s + p2 ) )
{
return 1;
}
t -= ( s + p2 );
s = 2 * s + p2;
}
unsigned long long p2 = ( one << ( n / 2 ) );
if( t < p2 )
{
k = t;
return 2;
}
t -= p2;
if( t < s )
{
k = s - 1 - t;
return 3;
}
return -1;
}
unsigned long long* solve()
{
unsigned long long *v;
if( n % 2 == 1 )
{
if( n == 1 )
{
if( k == 1 )
{
v = (unsigned long long*)malloc(1 * sizeof(unsigned long long));
v[0] = 1;
return v;
}
else
{
v = NULL;
return v;
}
}
k--;
int status = AdjustPlace();
if( status == -1 )
{
v = NULL;
return v;
}
solution = (unsigned long long*)malloc(n * sizeof(unsigned long long));
if( status == 1 )
{
SolveOne();
}
if( status == 2 )
{
solveTwo();
}
if( status == 3 )
{
SolveOne();
for( unsigned long long i = 0 ; i < n ; ++i >
{
solution[i] = n + 1 - solution[i];
}
}
return solution;
}
else
{
if( k > 2 )
{
v = NULL;
return v;
}
else
{
unsigned long long j = 0;
v = (unsigned long long*)malloc(n * sizeof(unsigned long long));
for( unsigned long long i = 0 ; i < n / 2 ; ++i )
{
if( k == 1 )
{
v[j++] = ( n / 2 - i );
v[j++] = ( n - i );
}
else
{
v[j++] = ( n / 2 + i + 1 );
v[j++] = ( i + 1 );
}
}
}
}
return v;
}
void print(unsigned long long *v)
{
for( unsigned long long i = 0 ; i < n - 1 ; i++ )
{
printf("%lld ", v[i]);
}
printf("%lld\n", v[n-1]);
}
int main()
{
unsigned long long t;
scanf("%lld", &t);
while(t--)
{
scanf("%lld %lld", &n, &k);
unsigned long long *t = solve();
if( t == NULL )
{
printf("%i\n", -1);
}
else
{
print(t>;
}
}
return 0;
}
#2 Code Example with C++ Programming
Code -
C++ Programming
#include <algorithm>
#include <assert.h>
#include <iostream>
#include <map>
#include <string>
#include <vector>
#include <unordered_set
using namespace std;
static const uint64_t one = 1;
void SolveSimple(uint64_t n, uint64_t k)
{
assert((n & 1) == 0);
if (k > 2)
{
cout << -1 << endl;
}
else
{
for (uint64_t i = 0; i < n / 2; ++i)
{
if (k == 1)
cout << (n / 2 - i) << " " << (n - i) << " ";
else
cout << (n / 2 + i + 1) << " " << (i + 1) << " ";
}
cout << endl;
}
}
class Solution
{
public:
vector < uint64_t> solution;
uint64_t n;
uint64_t k;
int AdjustPlace()
{
uint64_t t = k;
uint64_t n0 = 2;
if (t < n0)
return 1;
uint64_t s = n0;
t -= s;
for (uint64_t i = 0; i < n / 2 - 1; ++i)
{
uint64_t p2 = (one << i);
if (t < (s + p2))
return 1;
t -= (s + p2);
s = 2 * s + p2;
}
uint64_t p2 = (one << (n / 2));
if (t < p2)
{
k = t;
return 2;
}
t -= p2;
if (t < s)
{
k = s - 1 - t;
return 3;
}
return -1;
}
void Inverse()
{
for (size_t i = 0; i < solution.size(); ++i)
{
solution[i] = n + 1 - solution[i];
}
}
void Solve1()
{
vector<int> used(n + 2, 0);
uint64_t p = 0;
uint64_t mi = n / 2;
for (;;)
{
if (k == 0)
{
solution[p++] = 1;
for (size_t i = n / 2 + 1; i > 1; --i)
{
if (!used[i])
{
solution[p++] = i;
solution[p++] = i + n / 2;
}
}
return;
}
if (k == 1)
{
size_t i1 = 1;
size_t i2 = n / 2 + 2;
for (; p < n - 1; )
{
for (; used[i1]; ++i1);
for (; used[i2]; ++i2);
solution[p++] = i1++;
solution[p++] = i2++;
}
solution[p++] = n / 2 + 1;
return;
}
uint64_t s = 2;
k -= s;
for (uint64_t i = 0; ; ++i)
{
if (k < s)
{
solution[p++] = i + 2;
solution[p++] = i + 2 + n / 2;
used[i + 2] = 1;
used[i + 2 + n / 2] = 1;
break;
}
k -= s;
size_t p2 = (one << i);
if (k < p2)
{
size_t i1 = i + 2;
size_t i2 = n / 2 + i1 + 1;
for (; ;)
{
for (; used[i1]; ++i1);
if (i1 == (n / 2 + 1))
{
break;
}
for (; used[i2]; ++i2);
solution[p++] = i1++;
solution[p++] = i2++;
}
solution[p++] = i1;
solution[p++] = 1;
Solve2I(i);
return;
}
k -= p2;
s = 2 * s + p2;
}
}
}
void Solve2I(uint64_t r)
{
assert(k < (one << r));
uint64_t sf = n - 2 * r - 1;
uint64_t sb = n - 1;
uint64_t s2 = 2;
for (uint64_t i = 0; i < r; ++i)
{
uint64_t p2 = (one << (r - i - 1));
if (k < p2)
{
solution[sf] = n / 2 + s2 + i;
solution[sf + 1] = s2 + i;
sf += 2;
}
else
{
k -= p2;
solution[sb] = n / 2 + s2 + i;
solution[sb - 1] = s2 + i;
sb -= 2;
}
}
assert(sf == sb);
solution[sf] = n / 2 + s2 + r;
}
void Solve2()
{
uint64_t m = (one << (n / 2 - 1));
if (k >= m)
{
k = 2 * m - 1 - k;
Solve2();
Inverse();
return;
}
solution[0] = (n / 2) + 1;
solution[1] = 1;
Solve2I(n/2 - 1);
}
bool Solve(uint64_t _n, uint64_t _k)
{
n = _n;
k = _k - 1;
int status = AdjustPlace();
if (status == -1)
return false;
solution.resize(n);
if (status == 1)
Solve1();
if (status == 2)
Solve2();
if (status == 3)
{
Solve1();
Inverse();
}
return true;
}
};
class STest
{
public:
uint64_t count;
Solution S;
void PrintAllI(vector<int>& v, int k, int min_diff, vector < bool>& av)
{
if (k == v.size())
{
++count;
S.Solve(v.size(), count);
{
for (int i = 0; i < k; ++i)
{
cout << v[i] + 1 << " ";
}
cout << endl;
for (int i = 0; i < k; ++i)
{
cout << S.solution[i] << " ";
}
cout << endl;
}
}
else
{
int j = (k > 0) ? v[k - 1] : -min_diff;
for (int i = 0; i < int(av.size()); ++i)
{
if (av[i] && (abs(i - j) >= min_diff))
{
v[k] = i;
av[i] = false;
PrintAllI(v, k + 1, min_diff, av);
av[i] = true;
}
}
}
}
void PrintAll(int n)
{
count = 0;
vector<int> v(n, -1);
vector < bool> av(n, true);
PrintAllI(v, 0, n / 2, av);
}
};
void SSolve(uint64_t n, uint64_t k)
{
if (n == 1)
{
if (k == 1)
{
cout << 1 << endl;
}
else
{
cout << -1 << endl;
}
return;
}
Solution S;
if (S.Solve(n, k))
{
for (size_t i = 0; i < S.solution.size(); ++i)
{
cout << S.solution[i] << " ";
}
cout << endl;
}
else
{
cout << -1 << endl;
}
}
int main()
{
//STest t;
//t.PrintAll(11);
int T;
cin >> T;
for (; T; --T)
{
uint64_t n, k;
cin >> n >> k;
if (n & 1)
{
SSolve(n, k);
}
else
{
SolveSimple(n, k);
}
}
return 0;
}
#3 Code Example with Java Programming
Code -
Java Programming
import java.io.*;
import java.util.*;
public class Solution {
static String s = " ";
static long[] countSumms = new long[] {
0, 2, 5, 12, 28, 64, 144, 320, 704, 1536, 3328, 7168, 15360, 32768, 69632,
147456, 311296, 655360, 1376256, 2883584, 6029312, 12582912, 26214400,
54525952, 113246208, 234881024, 486539264, 1006632960, 2080374784,
4294967296l, 8858370048l, 18253611008l, 37580963840l, 77309411328l,
158913789952l, 326417514496l, 670014898176l, 1374389534720l, 2817498546176l,
5772436045824l, 11819749998592l, 24189255811072l, 49478023249920l,
101155069755392l, 206708186021888l, 422212465065984l, 862017116176384l,
1759218604441600l, 3588805953060864l, 7318349394477056l, 14918173765664768l,
30399297484750848l, 61924494876344320l, 126100789566373888l, 256705178760118272l,
522417556774977536l };
static int[] NOT_FOUND = new int[] { -1 };
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
for(int i = 0; i < t; i++) {
int n = sc.nextInt();
long k = sc.nextLong();
int[] res = solve(n, k);
StringBuilder b = new StringBuilder(countString(n));
for (int j = 0; j < res.length; j++) {
b.append(res[j]).append(s);
}
System.out.println(b.toString());
}
sc.close();
}
static int[] solve(int n, long k) {
if(n == 1) {
if(k == 1) {
return new int[] { 1 };
}
return NOT_FOUND;
}
int min = n >> 1;
/* even n */
if ((n & 1) == 0) {
if (k == 1) {
int[] ret = new int[n];
int ix = 0;
for (int i = 0; i < min; i++) {
ret[ix++] = min - i;
ret[ix++] = n - i;
}
return ret;
} else if (k == 2) {
int[] ret = new int[n];
int ix = 0;
for (int i = 0; i < min; i++) {
ret[ix++] = min + i + 1;
ret[ix++] = i + 1;
}
return ret;
} else {
return NOT_FOUND;
}
}
/* odd n */
long midCount = 1L << min;
boolean flip = false;
boolean middle = false;
int countSummIx = min;
long countsSumm;
k--;
/* k is before mid section */
if (countSumms.length < countSummIx || k < (countsSumm = countSumms[countSummIx])) {
}
/* k is inside of mid section */
else if (k < (countsSumm = countSumms[countSummIx]) + midCount) {
k = k - countsSumm;
middle = true;
}
/* k is after mid section but before end of last side */
else if (k < (countsSumm << 1) + midCount) {
k = Math.abs(k - (countsSumm << 1) - midCount + 1);
flip = true;
}
/* k out of range */
else {
return NOT_FOUND;
}
int[] arr = new int[n];
if (middle> {
arr[0] = min + 1;
arr[1] = 1;
if (k >= midCount >> 1) {
k = midCount - 1 - k;
flip = true;
}
solveRadius(n, k, min - 1, arr, min);
if (flip) {
int n_1 = n + 1;
for (int i = 0; i < arr.length; i++) {
arr[i] = n_1 - arr[i];
}
}
return arr;
}
solveSide(arr, n, k, min);
if (flip) {
int n_1 = n + 1;
for (int i = 0; i < arr.length; i++) {
arr[i] = n_1 - arr[i];
}
}
return arr;
}
static void solveSide(int[] arr, int n, long k, int min) {
boolean[] cache = new boolean[n + 1];
int ix = 0;
outer:while (true) {
if (k == 0) {
arr[ix++] = 1;
for (int i = min + 1; i > 1; i--) {
if (!cache[i]) {
arr[ix++] = i;
arr[ix++] = i + min;
}
}
break;
}
if (k == 1) {
for (int left = 1, right = min + 2, n_1 = n - 1; ix < n_1;) {
while (cache[left]) left++;
while (cache[right]) right++;
arr[ix++] = left++;
arr[ix++] = right++;
}
arr[ix++] = min + 1;
break;
}
k -= countSumms[1];
long next = 1L;
for (int i = 0, j = 2;; ++i, j++, next <<= 1) {
if (k < countSumms[i + 1]) {
arr[ix++] = j;
arr[ix++] = j + min;
cache[j] = cache[j + min] = true;
break;
}
k -= countSumms[i + 1];
if (k < next) {
int left = j;
int right = min + left + 1;
while (true) {
while (cache[left]) left++;
if (left == min + 1) {
break;
}
while (cache[right]) right++;
arr[ix++] = left++;
arr[ix++] = right++;
}
arr[ix++] = left;
arr[ix++] = 1;
solveRadius(n, k, i, arr, min);
break outer;
}
k -= next;
}
}
}
static int countString(int n) {
int ret = 0;
if(n < 10) { return n << 1; }
ret += 18;
if(n < 100) { ret += (n - 9) * 3; return ret;}
ret += 270;
if(n < 1000) { ret += (n - 99) << 2; return ret;}
ret += 3600;
if(n < 10000) { ret += (n - 999) * 5; return ret;}
ret += 45000;
if(n < 100000) { ret += (n - 9999) * 6; return ret;}
ret += 540000;
ret += (n - 99999) * 7;
return ret;
}
static void solveRadius(int n, long k, int radius, int[] arr, int min) {
int left = n - (radius << 1) - 1;
int right = n - 1;
int min_2 = min + 2;
for (int i = 0; i < radius; ++i) {
long next = (1L << (radius - (i + 1)));
if (k < next> {
arr[left] = min_2 + i;
arr[left + 1] = 2 + i;
left += 2;
} else {
arr[right] = min_2 + i;
arr[right - 1] = 2 + i;
right -= 2;
k -= next;
}
}
arr[left] = min_2 + radius;
}
}
#4 Code Example with Python Programming
Code -
Python Programming
from bisect import *
import collections
from time import time
import random
popdistr = collections.Counter()
def naive(n, k):
def gen(perm, nums):
if len(perm) == n:
perms.append(perm)
for i in sorted(nums):
if abs(perm[-1] - i) >= mindist:
gen(perm + [i], nums - {i})
perms = []
mindist = n // 2
for i in range(n):
gen([i], set(range(n)) - {i})
return perms[k] if k < len(perms) else -1
def smart(n, k):
if n < 5:
return naive(n, k)
half = n // 2
h = half
H = half + 1
# Even n cases
if not n & 1:
if k > 1:
return -1
perm = [None] * n
if k == 0:
# 4 9 3 8 2 7 1 6 0 5
perm[::2] = range(h - 1, -1, -1)
perm[1::2] = range(n - 1, h - 1, -1)
else:
# 5 0 6 1 7 2 8 3 9 4
perm[::2] = range(h, n)
perm[1::2] = range(h)
return perm
low = (h + 3) << (h - 2)
#low = 2 if n == 3 else (h + 3) << (h - 2)
lowmid = 1 << (h - 1)
#print(k, low, lowmid)
if k >= (low + lowmid) * 2:
return -1
if k >= low + lowmid:
merp = smart(n, (low + lowmid) * 2 - 1 - k)
if merp == -2:
return merp
return [n - 1 - m for m in merp]
if k >= low:
return binary(list(range(n)), k - low, h)
offset = [2]
for i in range(half - 1):
offset.append(offset[-1] * 2 + (1 << i))
if offset[-1] > 10 ** 30:
break
offset.append(offset[-1] + (1 << (i + 1)))
offset.append(0)
nums = list(range(n))
perm = []
pops = 0
while True:
# Cases k=0, k=1
if k < 2:
# n=11: 0 5 10 4 9 3 8 2 7 1 6
# 0 6 1 7 2 8 3 9 4 10 5
add = h + k
return perm + [nums[i * add % n] for i in range(n)]
i = bisect(offset, k)
k -= offset[i - 1]
# Binary cases
if k >= offset[i - 1]:# or i == h:
return perm + binary(nums, k - offset[i - 1], i)
# Ugly cases
perm += nums.pop(i), nums.pop(i + h - 1)
n -= 2
half -= 1
h -= 1
H -= 1
if pops:
popdistr[pops] -= 1
pops += 1
popdistr[pops] += 1
def binary(nums, k, i):
n = len(nums)
half = n // 2
H = half + 1
perm = [None] * n
ks, testbit = bin(k)[:1:-1], half - 1
left, right = 0, n - 1
for m in range(i, i + half):
if testbit < len(ks) and ks[testbit] == '1':
perm[right] = nums[m]
perm[right-1] = nums[(m + H) % n]
right -= 2
else:
perm[left] = nums[m]
perm[left+1] = nums[(m + H) % n]
left += 2
testbit -= 1
perm[left] = nums[i + half]
return perm
t = int(input())
for _ in range(t):
n, k = map(int, input().split())
perm = smart(n, k - 1)
print(-1 if perm == -1 else ' '.join(str(p+1) for p in perm))