Dados dos números enteros N y K , encuentre la secuencia de permutación Kth de números de 1 a N sin usar la función STL.
Nota: Suponga que las entradas son tales que la K-ésima permutación de N número siempre es posible.
Ejemplos:
Entrada: N = 3, K = 4
Salida: 231
Explicación:
La lista ordenada de la secuencia de permutación del entero 1 al 3 es: 123, 132, 213, 231, 312, 321. Entonces, la cuarta secuencia de permutación es «231».Entrada: N = 2, K = 1
Salida: 12
Explicación:
Para n = 2, solo son posibles 2 permutaciones 12 21. Entonces, la primera secuencia de permutación es «12».
Enfoque ingenuo:
para resolver el problema mencionado anteriormente, el enfoque simple es encontrar todas las secuencias de permutación y generar el k-ésimo de ellas. Pero este método no es tan eficiente y lleva más tiempo, por lo que se puede optimizar.
Enfoque eficiente:
para optimizar el método mencionado anteriormente, observe que el valor de k se puede usar directamente para encontrar el número en cada índice de la secuencia.
- La primera posición de una secuencia de longitud n está ocupada por cada uno de los números del 1 al n ¡exactamente n! / n que es (n-1)! número de veces y en orden ascendente. ¡Entonces la primera posición de la k-ésima secuencia estará ocupada por el número presente en el índice = k / (n-1)! (según indexación basada en 1).
- El número encontrado actualmente no puede volver a aparecer, por lo que se elimina de los n números originales y ahora el problema se reduce a encontrar la (k % (n-1)! )ésima secuencia de permutación de los n-1 números restantes.
- Este proceso se puede repetir hasta que solo nos quede un número que se colocará en la primera posición de la última secuencia de 1 longitud.
- Los valores factoriales involucrados aquí pueden ser muy grandes en comparación con k. Entonces, el truco usado para evitar el cálculo completo de factoriales tan grandes es que tan pronto como el producto n * (n-1) * … sea mayor que k , ya no necesitamos encontrar el valor factorial real porque:
k / n_valor_factorial_actual = 0
y k / n_valor_factorial_parcial = 0
cuando valor_factorial_parcial > k
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to Find the kth Permutation
// Sequence of first n natural numbers
#include <bits/stdc++.h>
using namespace std;
// Function to find the index of number
// at first position of
// kth sequence of set of size n
int findFirstNumIndex(int& k, int n)
{
if (n == 1)
return 0;
n--;
int first_num_index;
// n_actual_fact = n!
int n_partial_fact = n;
while (k >= n_partial_fact
&& n > 1) {
n_partial_fact
= n_partial_fact
* (n - 1);
n--;
}
// First position of the
// kth sequence will be
// occupied by the number present
// at index = k / (n-1)!
first_num_index = k / n_partial_fact;
k = k % n_partial_fact;
return first_num_index;
}
// Function to find the
// kth permutation of n numbers
string findKthPermutation(int n, int k)
{
// Store final answer
string ans = "";
set<int> s;
// Insert all natural number
// upto n in set
for (int i = 1; i <= n; i++)
s.insert(i);
set<int>::iterator itr;
// Mark the first position
itr = s.begin();
// subtract 1 to get 0 based indexing
k = k - 1;
for (int i = 0; i < n; i++) {
int index
= findFirstNumIndex(k, n - i);
advance(itr, index);
// itr now points to the
// number at index in set s
ans += (to_string(*itr));
// remove current number from the set
s.erase(itr);
itr = s.begin();
}
return ans;
}
// Driver code
int main()
{
int n = 3, k = 4;
string kth_perm_seq
= findKthPermutation(n, k);
cout << kth_perm_seq << endl;
return 0;
}
Java
// Java program to Find
// the kth Permutation
// Sequence of first
// n natural numbers
import java.util.*;
class GFG{
// Function to find the index of
// number at first position of
// kth sequence of set of size n
static int findFirstNumIndex(int k,
int n)
{
if (n == 1)
return 0;
n--;
int first_num_index;
// n_actual_fact = n!
int n_partial_fact = n;
while (k >= n_partial_fact && n > 1)
{
n_partial_fact = n_partial_fact *
(n - 1);
n--;
}
// First position of the
// kth sequence will be
// occupied by the number present
// at index = k / (n-1)!
first_num_index = k / n_partial_fact;
k = k % n_partial_fact;
return first_num_index;
}
// Function to find the
// kth permutation of n numbers
static String findKthPermutation(int n,
int k)
{
// Store final answer
String ans = "";
HashSet<Integer> s = new HashSet<>();
// Insert all natural number
// upto n in set
for (int i = 1; i <= n; i++)
s.add(i);
Vector<Integer> v = new Vector<>();
v.addAll(s);
// Mark the first position
int itr = v.elementAt(0);
// Subtract 1 to
// get 0 based
// indexing
k = k - 1;
for (int i = 0; i < n; i++)
{
int index = findFirstNumIndex(k,
n - i);
// itr now points to the
// number at index in set s
if(index < v.size())
{
ans += ((v.elementAt(index).toString()));
v.remove(index);
}
else
ans += String.valueOf(itr + 2);
// Remove current number
// from the set
itr = v.elementAt(0);
}
return ans;
}
// Driver code
public static void main(String[] args)
{
int n = 3, k = 4;
String kth_perm_seq = findKthPermutation(n, k);
System.out.print(kth_perm_seq + "\n");
}
}
// This code is contributed by Rajput-Ji
Python3
# Python3 program to find the kth permutation # Sequence of first n natural numbers # Function to find the index of number # at first position of kth sequence of # set of size n def findFirstNumIndex(k, n): if (n == 1): return 0, k n -= 1 first_num_index = 0 # n_actual_fact = n! n_partial_fact = n while (k >= n_partial_fact and n > 1): n_partial_fact = n_partial_fact * (n - 1) n -= 1 # First position of the kth sequence # will be occupied by the number present # at index = k / (n-1)! first_num_index = k // n_partial_fact k = k % n_partial_fact return first_num_index, k # Function to find the # kth permutation of n numbers def findKthPermutation(n, k): # Store final answer ans = "" s = set() # Insert all natural number # upto n in set for i in range(1, n + 1): s.add(i) # Subtract 1 to get 0 based indexing k = k - 1 for i in range(n): # Mark the first position itr = list(s) index, k = findFirstNumIndex(k, n - i) # itr now points to the # number at index in set s ans += str(itr[index]) # remove current number from the set itr.pop(index) s = set(itr) return ans # Driver code if __name__=='__main__': n = 3 k = 4 kth_perm_seq = findKthPermutation(n, k) print(kth_perm_seq) # This code is contributed by rutvik_56
C#
// C# program to Find
// the kth Permutation
// Sequence of first
// n natural numbers
using System;
using System.Collections.Generic;
class GFG{
// Function to find the index of
// number at first position of
// kth sequence of set of size n
static int findFirstNumIndex(int k,
int n)
{
if (n == 1)
return 0;
n--;
int first_num_index;
// n_actual_fact = n!
int n_partial_fact = n;
while (k >= n_partial_fact && n > 1)
{
n_partial_fact = n_partial_fact *
(n - 1);
n--;
}
// First position of the
// kth sequence will be
// occupied by the number present
// at index = k / (n-1)!
first_num_index = k / n_partial_fact;
k = k % n_partial_fact;
return first_num_index;
}
// Function to find the
// kth permutation of n numbers
static String findKthPermutation(int n,
int k)
{
// Store readonly answer
String ans = "";
HashSet<int> s = new HashSet<int>();
// Insert all natural number
// upto n in set
for (int i = 1; i <= n; i++)
s.Add(i);
List<int> v = new List<int>(s);
// Mark the first position
int itr = v[0];
// Subtract 1 to
// get 0 based
// indexing
k = k - 1;
for (int i = 0; i < n; i++)
{
int index = findFirstNumIndex(k, n - i);
// itr now points to the
// number at index in set s
if(index < v.Count)
{
ans += ((v[index].ToString()));
v.RemoveAt(index);
}
else
ans += String.Join("", itr + 2);
// Remove current number
// from the set
itr = v[0];
}
return ans;
}
// Driver code
public static void Main(String[] args)
{
int n = 3, k = 4;
String kth_perm_seq = findKthPermutation(n, k);
Console.Write(kth_perm_seq + "\n");
}
}
// This code is contributed by Rajput-Ji
Producción:
231
Publicación traducida automáticamente
Artículo escrito por nishita300601 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA