Dados dos enteros n y k. Considere la primera permutación de n números naturales, P = “1 2 3 … n”, imprima un “Resultado” de permutación tal que abs(Resultado i – P i ) = k donde P i denota la posición de i en la permutación P. El valor de P i varía de 1 a n. Si hay varios resultados posibles, imprima el más pequeño desde el punto de vista lexicográfico.
Input: n = 6 k = 3
Output: 4 5 6 1 2 3
Explanation:
P = 1 2 3 4 5 6
Result = 4 5 6 1 2 3
We can notice that the difference between
individual numbers (at same positions) of
P and result is 3 and "4 5 6 1 2 3" is
lexicographically smallest such permutation.
Other greater permutations could be
Input : n = 6 k = 2
Output : Not possible
Explanation: No permutation is possible
with difference is k
El enfoque ingenuo es generar todas las permutaciones de 1 an y elegir la más pequeña que satisfaga la condición de diferencia absoluta k. La complejidad de tiempo de este enfoque es Ω(n!) que definitivamente expirará para un gran valor de n.
El enfoque Eficiente es observar el patrón en cada posición del índice. Para cada posición del índice i, solo pueden existir dos candidatos, es decir, i + k e i – k. Como necesitamos encontrar la permutación lexicográficamente más pequeña, primero buscaremos el candidato i – k (si es posible) y luego el candidato i + k.
Illustration: n = 8, k = 2 P : 1 2 3 4 5 6 7 8 For any ith position we will check which candidate is possible i.e., i + k or i - k 1st pos = 1 + 2 = 3 (1 - 2 not possible) 2nd pos = 2 + 2 = 4 (2 - 2 not possible) 3rd pos = 3 - 2 = 1 (possible) 4th pos = 4 - 2 = 2 (possible) 5th pos = 5 + 2 = 7 (5 - 2 already placed, not possible) 6th pos = 6 + 2 = 8 (6 - 2 already placed, not possible) 7th pos = 7 - 2 = 5 (possible) 8th pos = 8 - 2 = 6 (possible)
Nota: si observamos la ilustración anterior, encontraremos que i + k e i – k se alternan después del k -ésimo intervalo consecutivo. Otra observación es que la permutación completa es solo cuando n es par tal que n se puede dividir en dos partes donde cada parte debe ser divisible por k.
C++
// C++ program to find k absolute difference
// permutation
#include<bits/stdc++.h>
using namespace std;
void kDifferencePermutation(int n, int k)
{
// If k is 0 then we just print the
// permutation from 1 to n
if (!k)
{
for (int i = 0; i < n; ++i)
cout << i + 1 << " ";
}
// Check whether permutation is feasible or not
else if (n % (2 * k) != 0)
cout <<"Not Possible";
else
{
for (int i = 0; i < n; ++i)
{
// Put i + k + 1 candidate if position is
// feasible, otherwise put the i - k - 1
// candidate
if ((i / k) % 2 == 0)
cout << i + k + 1 << " ";
else
cout << i - k + 1 << " ";
}
}
cout << "\n";
}
// Driver code
int main()
{
int n = 6 , k = 3;
kDifferencePermutation(n, k);
n = 6 , k = 2;
kDifferencePermutation(n, k);
n = 8 , k = 2;
kDifferencePermutation(n, k);
return 0;
}
Java
// Java program to find k absolute
// difference permutation
import java.io.*;
class GFG {
static void kDifferencePermutation(int n,
int k)
{
// If k is 0 then we just print the
// permutation from 1 to n
if (!(k > 0))
{
for (int i = 0; i < n; ++i)
System.out.print( i + 1 + " ");
}
// Check whether permutation is
// feasible or not
else if (n % (2 * k) != 0)
System.out.print("Not Possible");
else
{
for (int i = 0; i < n; ++i)
{
// Put i + k + 1 candidate
// if position is feasible,
// otherwise put the
// i - k - 1 candidate
if ((i / k) % 2 == 0)
System.out.print( i + k
+ 1 + " ");
else
System.out.print( i - k
+ 1 + " ");
}
}
System.out.println() ;
}
// Driver code
static public void main (String[] args)
{
int n = 6 , k = 3;
kDifferencePermutation(n, k);
n = 6 ;
k = 2;
kDifferencePermutation(n, k);
n = 8 ;
k = 2;
kDifferencePermutation(n, k);
}
}
// This code is contributed by anuj_67.
Python3
# Python 3 program to find k
# absolute difference permutation
def kDifferencePermutation(n, k):
# If k is 0 then we just print the
# permutation from 1 to n
if (k == 0):
for i in range(n):
print(i + 1, end = " ")
# Check whether permutation
# is feasible or not
elif (n % (2 * k) != 0):
print("Not Possible", end = "")
else:
for i in range(n):
# Put i + k + 1 candidate if position is
# feasible, otherwise put the i - k - 1
# candidate
if (int(i / k) % 2 == 0):
print(i + k + 1, end = " ")
else:
print(i - k + 1, end = " ")
print("\n", end = "")
# Driver code
if __name__ == '__main__':
n = 6
k = 3
kDifferencePermutation(n, k)
n = 6
k = 2
kDifferencePermutation(n, k)
n = 8
k = 2
kDifferencePermutation(n, k)
# This code is contributed by
# Surendra_Gangwar
C#
// C# program to find k absolute
// difference permutation
using System;
class GFG {
static void kDifferencePermutation(int n,
int k)
{
// If k is 0 then we just print the
// permutation from 1 to n
if (!(k > 0))
{
for (int i = 0; i < n; ++i)
Console.Write( i + 1 + " ");
}
// Check whether permutation is
// feasible or not
else if (n % (2 * k) != 0)
Console.Write("Not Possible");
else
{
for (int i = 0; i < n; ++i)
{
// Put i + k + 1 candidate
// if position is feasible,
// otherwise put the
// i - k - 1 candidate
if ((i / k) % 2 == 0)
Console.Write( i + k
+ 1 + " ");
else
Console.Write( i - k
+ 1 + " ");
}
}
Console.WriteLine() ;
}
// Driver code
static public void Main ()
{
int n = 6 , k = 3;
kDifferencePermutation(n, k);
n = 6 ;
k = 2;
kDifferencePermutation(n, k);
n = 8 ;
k = 2;
kDifferencePermutation(n, k);
}
}
// This code is contributed by anuj_67.
PHP
<?php
// PHP program to find k absolute
// difference permutation
function kDifferencePermutation( $n, $k)
{
// If k is 0 then we just print the
// permutation from 1 to n
if (!$k)
{
for($i = 0; $i < $n; ++$i)
echo $i + 1 ," ";
}
// Check whether permutation
// is feasible or not
else if ($n % (2 * $k) != 0)
echo"Not Possible";
else
{
for($i = 0; $i < $n; ++$i)
{
// Put i + k + 1 candidate
// if position is feasible,
// otherwise put the i - k - 1
// candidate
if (($i / $k) % 2 == 0)
echo $i + $k + 1 , " ";
else
echo $i - $k + 1 , " ";
}
}
echo "\n";
}
// Driver Code
$n = 6 ; $k = 3;
kDifferencePermutation($n, $k);
$n = 6 ; $k = 2;
kDifferencePermutation($n, $k);
$n = 8 ;$k = 2;
kDifferencePermutation($n, $k);
// This code is contributed by anuj_67.
?>
Javascript
<script>
// Javascript program to find k absolute difference permutation
function kDifferencePermutation(n, k)
{
// If k is 0 then we just print the
// permutation from 1 to n
if (!(k > 0))
{
for (let i = 0; i < n; ++i)
document.write( i + 1 + " ");
}
// Check whether permutation is
// feasible or not
else if (n % (2 * k) != 0)
document.write("Not Possible");
else
{
for (let i = 0; i < n; ++i)
{
// Put i + k + 1 candidate
// if position is feasible,
// otherwise put the
// i - k - 1 candidate
if (parseInt(i / k, 10) % 2 == 0)
document.write( i + k
+ 1 + " ");
else
document.write( i - k
+ 1 + " ");
}
}
document.write("</br>") ;
}
let n = 6 , k = 3;
kDifferencePermutation(n, k);
n = 6 ;
k = 2;
kDifferencePermutation(n, k);
n = 8 ;
k = 2;
kDifferencePermutation(n, k);
// This code is contributed by rameshtravel07.
</script>
Producción:
4 5 6 1 2 3 Not Possible 3 4 1 2 7 8 5 6
Complejidad temporal: O(n)
Espacio auxiliar: O(1)
Este artículo es una contribución de Shubham Bansal . 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 contribuir@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