http://www.geeksforgeeks.org/rearrange-first-n-numbers-make-k-distance/
Given a positive number K, we need to permute first N natural numbers in such a way that absolute distance of each permuted number from its original position is K and if it is not possible to rearrange them in such manner then print not possible.
Given a positive number K, we need to permute first N natural numbers in such a way that absolute distance of each permuted number from its original position is K and if it is not possible to rearrange them in such manner then print not possible.
We can solve this problem by finding the pattern in solutions. If we go through many solutions manually, we can see that if we partition N numbers into slots of size 2K, then each slot can be rearranged in two parts of size K, where the difference of position with actual position will be K.
Example 1 : N = 12 and K = 2 First 12 numbers are partitioned into 2*2 = 4 sized 12/4 = 3 slots as shown below, [[1 2 3 4] [5 6 7 8] [9 10 11 12]] Now each half of the slot is swapped so that, every number will go at K position distance from its initial position as shown below, [[3 4 1 2] [7 8 5 6] [11 12 9 10]] Example 2 : N = 12 and K = 3, [1 2 3 4 5 6 7 8 9 10 11 12] [[1 2 3 4 5 6] [7 8 9 10 11 12]] [[4 5 6 1 2 3] [10 11 12 7 8 9]] [4 5 6 1 2 3 10 11 12 7 8 9] Which is the final rearrangement for N = 12 and K = 3
In below code, the case when K = 0 is handled separately by printing all numbers in their actual order. When N is not divisible by 2K, ‘not possible’ is printed directly.
void
printRearrangeNnumberForKDistance(
int
N,
int
K)
{
// If K = 0, then print numbers in their natural
// order
if
(K == 0)
{
for
(
int
i = 1; i <= N; i++)
cout << i <<
" "
;
cout << endl;
return
;
}
// If N doesn't divide (2K) evenly, then
// rearrangement is not possible
if
(N % (2 * K) != 0)
{
cout <<
"Not Possible\n"
;
return
;
}
// Copy first N numbers to an auxiliary
// array
int
arr[N + 1];
for
(
int
i = 1; i <= N; i++)
arr[i] = i;
// Swap halves of each 2K sized slot
for
(
int
i = 1; i <= N; i += 2*K)
for
(
int
j = 1; j <= K; j++)
swap(arr[i+j-1], arr[K+i+j-1]);
// Print the rearranged array
for
(
int
i = 1; i <= N; i++)
cout << arr[i] <<
" "
;
}