Dado un número positivo K, necesitamos permutar los primeros N números naturales de tal manera que la distancia absoluta de cada número permutado desde su posición original sea K y si no es posible reorganizarlos de esa manera, entonces no es posible imprimir.
Ejemplos:
Input : N = 12
K = 2
Output : [3 4 1 2 7 8 5 6 11 12 9 10]
Explanation : Initial permutation is
[1 2 3 4 5 6 7 8 9 10 11 12]
In rearrangement, [3 4 1 2 7 8 5 6 11
12 9 10] we have all elements at
distance 2.
Input : N = 12
K = 3
Output : [4 5 6 1 2 3 10 11 12 7 8 9]
Podemos resolver este problema encontrando el patrón en las soluciones. Si revisamos muchas soluciones manualmente, podemos ver que si dividimos N números en ranuras de tamaño 2K, entonces cada ranura se puede reorganizar en dos partes de tamaño K, donde la diferencia de posición con la posición real será 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
En el siguiente código, el caso cuando K = 0 se maneja por separado al imprimir todos los números en su orden real. Cuando N no es divisible por 2K, ‘no es posible’ se imprime directamente.
C++
// C++ program to rearrange permutations to make
// them K distance away
#include <bits/stdc++.h>
using namespace std;
/* Method prints permutation of first N numbers,
where each number is K distance away from its
actual position */
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] << " ";
}
// Driver code
int main()
{
int N = 12, K = 3;
printRearrangeNnumberForKDistance(N, K);
return 0;
}
Java
// Java program to rearrange permutations
// to make them K distance away
class GFG
{
/* Method prints permutation of first N numbers,
where each number is K distance away from its
actual position */
static 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++)
System.out.print(i + " ");
System.out.println();
return;
}
// If N doesn't divide (2K) evenly, then
// rearrangement is not possible
if (N % (2 * K) != 0)
{
System.out.print("Not Possible\n");
return;
}
// Copy first N numbers to an auxiliary
// array
int arr[]=new int[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++)
{
int temp = arr[i + j - 1];
arr[i + j - 1] = arr[K + i + j - 1];
arr[K + i + j - 1] = temp;
}
// Print the rearranged array
for (int i = 1; i <= N; i++)
System.out.print(arr[i] + " ");
}
// Driver code
public static void main (String[] args)
{
int N = 12, K = 3;
printRearrangeNnumberForKDistance(N, K);
}
}
// This code is contributed by Anant Agarwal.
Python3
# Python3 program to rearrange
# permutations to make them
# K distance away
'''
* Method prints permutation of
first N numbers, where each number
is K distance * away from its actual
position
'''
def printRearrangeNnumberForKDistance(N, K):
# If K = 0, then print numbers
# in their natural order
if (K == 0):
for i in range(1, N + 1):
print(i, end = " ");
print();
return;
# If N doesn't divide (2K) evenly,
# then rearrangement is not possible
if (N % (2 * K) != 0):
print("Not Possible");
return;
# Copy first N numbers to an
# auxiliary array
arr = [0] * (N + 1);
for i in range(1, N + 1):
arr[i] = i;
# Swap halves of each 2K
# sized slot
for i in range(1, N + 1,
2 * K):
for j in range(1, K + 1):
temp = arr[i + j - 1];
arr[i + j - 1] = arr[K + i + j - 1];
arr[K + i + j - 1] = temp;
# Print rearranged array
for i in range(1, N + 1):
print(arr[i], end = " ");
# Driver code
if __name__ == '__main__':
N = 12;
K = 3;
printRearrangeNnumberForKDistance(N, K);
# This code is contributed by 29AjayKumar
C#
// C# program to rearrange permutations
// to make them K distance away
using System;
class GFG
{
/* Method prints permutation of first N numbers,
where each number is K distance away from its
actual position */
static 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++)
Console.Write(i + " ");
Console.WriteLine();
return;
}
// If N doesn't divide (2K) evenly, then
// rearrangement is not possible
if (N % (2 * K) != 0)
{
Console.Write("Not Possible\n");
return;
}
// Copy first N numbers to an auxiliary
// array
int []arr=new int[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++)
{
int temp = arr[i + j - 1];
arr[i + j - 1] = arr[K + i + j - 1];
arr[K + i + j - 1] = temp;
}
// Print the rearranged array
for (int i = 1; i <= N; i++)
Console.Write(arr[i] + " ");
}
// Driver code
public static void Main ()
{
int N = 12, K = 3;
printRearrangeNnumberForKDistance(N, K);
}
}
// This code is contributed by nitin mittal.
Javascript
<script>
// JavaScript program for the above approach
/* Method prints permutation of first N numbers,
where each number is K distance away from its
actual position */
function printRearrangeNnumberForKDistance(N, K)
{
// If K = 0, then print numbers
// in their natural order
if (K == 0)
{
for (let i = 1; i <= N; i++)
document.write(i + " ");
document.write("<br/>");
return;
}
// If N doesn't divide (2K) evenly, then
// rearrangement is not possible
if (N % (2 * K) != 0)
{
document.write("Not Possible\n");
return;
}
// Copy first N numbers to an auxiliary
// array
let arr = [];
for (let i = 1; i <= N; i++)
arr[i] = i;
// Swap halves of each 2K sized slot
for (let i = 1; i <= N; i += 2 * K)
for (let j = 1; j <= K; j++)
{
let temp = arr[i + j - 1];
arr[i + j - 1] = arr[K + i + j - 1];
arr[K + i + j - 1] = temp;
}
// Print the rearranged array
for (let i = 1; i <= N; i++)
document.write(arr[i] + " ");
}
// Driver Code
let N = 12, K = 3;
printRearrangeNnumberForKDistance(N, K);
</script>
Producción :
4 5 6 1 2 3 10 11 12 7 8 9
Este artículo es una contribución de Utkarsh Trivedi . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA