Dados dos números enteros N y K, la tarea es generar una permutación de N números (Cada número de 1 a N ocurre exactamente una vez) tal que el número de índices donde a[i]>a[i+1] sea exactamente K. Escriba «No es posible» si no es posible tal permutación.
Ejemplos:
Input: N = 5, K = 3 Output: 5 4 3 1 2 Starting 3 indices satisfying the condition a[i] > a[i]+1 Input: N = 7, k = 4 Output: 7 6 5 4 1 2 3
Enfoque: Dado que la permutación debería ser lexicográficamente la más pequeña con la condición satisfecha para k índices, es decir, a[i] > a[i+1]. Entonces, para eso, los dígitos K + 1 iniciales deben estar en orden decreciente y los restantes deben estar en orden creciente. Así que simplemente imprima los números K de N a 1. Luego imprima los números de 1 a NK.
Por ejemplo: N = 6, K = 4
Imprime números K de N a 1, es decir, 6, 5, 4, 3
Imprime números NK de 1 a NK, es decir, 1, 2
La permutación será 654312, es decir, 4 índices iniciales satisfacen a[i] > a[i+1] para i = 1 a k.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the above approach #include <bits/stdc++.h> using namespace std; void printPermutation(int n, int k) { int i, mx = n; for (i = 1; i <= k; i++) // Decreasing part { cout << mx << " "; mx--; } for (i = 1; i <= mx; i++) // Increasing part cout << i << " "; } // Driver Code int main() { int N = 5, K = 3; if (K >= N - 1) cout << "Not Possible"; else printPermutation(N, K); return 0; }
Java
// Java implementation of the above approach import java.io.*; class GFG { static void printPermutation(int n, int k) { int i, mx = n; for (i = 1; i <= k; i++) // Decreasing part { System.out.print( mx + " "); mx--; } for (i = 1; i <= mx; i++) // Increasing part System.out.print( i + " "); } // Driver Code public static void main (String[] args) { int N = 5, K = 3; if (K >= N - 1) System.out.print( "Not Possible"); else printPermutation(N, K); } } // This code is contributed by inder_verma..
Python3
# Python3 implementation of the # above approach def printPermutation(n, k): mx = n for i in range(1, k + 1): # Decreasing part print(mx, end = " ") mx -= 1 for i in range(1, mx + 1): # Increasing part print(i, end = " ") # Driver Code if __name__ == "__main__": N, K = 5, 3 if K >= N - 1: print("Not Possible") else: printPermutation(N, K) # This code is contributed # by Rituraj Jain
C#
// C# implementation of the above approach using System; class GFG { static void printPermutation(int n, int k) { int i, mx = n; for (i = 1; i <= k; i++) // Decreasing part { Console.Write( mx + " "); mx--; } for (i = 1; i <= mx; i++) // Increasing part Console.Write( i + " "); } // Driver Code public static void Main () { int N = 5, K = 3; if (K >= N - 1) Console.WriteLine( "Not Possible"); else printPermutation(N, K); } } // This code is contributed by inder_verma..
PHP
<?php // PHP implementation of the above approach function printPermutation($n, $k) { $i; $mx = $n; for ($i = 1; $i <=$k; $i++) // Decreasing part { echo $mx , " "; $mx--; } for ($i = 1; $i <=$mx; $i++) // Increasing part echo $i , " "; } // Driver Code $N = 5; $K = 3; if ($K >= $N - 1) echo "Not Possible"; else printPermutation($N, $K); // This code is contributed by inder_verma.. ?>
Javascript
<script> // javascript implementation of the above approach function printPermutation(n , k) { var i, mx = n; for (i = 1; i <= k; i++) // Decreasing part { document.write( mx + " "); mx--; } for (i = 1; i <= mx; i++) // Increasing part document.write( i + " "); } // Driver Code var N = 5, K = 3; if (K >= N - 1) document.write( "Not Possible"); else printPermutation(N, K); // This code is contributed by 29AjayKumar </script>
5 4 3 1 2
Complejidad de tiempo: O(N)
Publicación traducida automáticamente
Artículo escrito por Abdullah Aslam y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA