Dadas dos arrays P[] y Q[] que permutan los primeros N números naturales. Si P[] y Q[] son las a -ésimas y b -ésimas permutaciones lexicográficamente más pequeñas de [1, N] respectivamente, la tarea es encontrar | un – segundo | .
Ejemplos:
Entrada: P[] = {1, 3, 2}, Q[] = {3, 1, 2}
Salida: 3
Explicación: 6 permutaciones de [1, 3] ordenadas lexicográficamente son {{1, 2, 3}, {1, 3, 2}, {2, 1, 3}, {2, 3, 1}, {3, 1, 2}, {3, 2, 1}}. Por lo tanto, el rango de P[] es 2 y el rango de Q[] es 5. Por lo tanto, la diferencia es |2 – 5| = 3.Entrada: P[] = {1, 2}, Q[] = {1, 2}
Salida: 0
Explicación: 2 permutaciones de [1, 2] dispuestas lexicográficamente son {{1, 2}, {2, 1}} . Por lo tanto, el rango de P[] es 1 y el rango de Q[] es 1. Por lo tanto, la diferencia es |2-2| = 0.
Enfoque: siga los pasos a continuación para resolver el problema:
- Utilice la función next_permutation() para encontrar los rangos de ambas permutaciones.
- Inicialice una array temp[] para almacenar la permutación más pequeña de los primeros N números naturales. Además, inicialice dos variables a y b con 0 para almacenar los rangos lexicográficos de las dos permutaciones.
- Compruebe si temp[] es igual a P[] o no. Si se determina que es cierto, salga del bucle. De lo contrario, incremente a en 1 y verifique la siguiente permutación
- De manera similar, encuentre el rango lexicográfico de la permutación Q[] y guárdelo en b .
- Finalmente, imprima la diferencia absoluta entre a y b como respuesta.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function the print the difference
// between the lexicographical ranks
void findDifference(vector<int>& p,
vector<int>& q, int N)
{
// Store the permutations
// in lexicographic order
vector<int> A(N);
// Initial permutation
for (int i = 0; i < N; i++)
A[i] = i + 1;
// Initial variables
bool IsCorrect;
int a = 1, b = 1;
// Check permutation
do {
IsCorrect = true;
for (int i = 0; i < N; i++) {
if (A[i] != p[i]) {
IsCorrect = false;
break;
}
}
if (IsCorrect)
break;
a++;
} while (next_permutation(A.begin(),
A.end()));
// Initialize second permutation
for (int i = 0; i < N; i++)
A[i] = i + 1;
// Check permutation
do {
IsCorrect = true;
for (int i = 0; i < N; i++) {
if (A[i] != q[i]) {
IsCorrect = false;
break;
}
}
if (IsCorrect)
break;
b++;
} while (next_permutation(A.begin(),
A.end()));
// Print difference
cout << abs(a - b) << endl;
}
// Driver Code
int main()
{
// Given array P[]
vector<int> p = { 1, 3, 2 };
// Given array Q[]
vector<int> q = { 3, 1, 2 };
// Given size
int n = p.size();
// Function call
findDifference(p, q, n);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Function the print the difference
// between the lexicographical ranks
static void findDifference(int[] p,
int[] q,
int N)
{
// Store the permutations
// in lexicographic order
int[] A = new int[N];
// Initial permutation
for(int i = 0; i < N; i++)
A[i] = i + 1;
// Initial variables
boolean IsCorrect;
int a = 1, b = 1;
// Check permutation
do
{
IsCorrect = true;
for(int i = 0; i < N; i++)
{
if (A[i] != p[i])
{
IsCorrect = false;
break;
}
}
if (IsCorrect)
break;
a++;
} while (next_permutation(A));
// Initialize second permutation
for(int i = 0; i < N; i++)
A[i] = i + 1;
// Check permutation
do
{
IsCorrect = true;
for(int i = 0; i < N; i++)
{
if (A[i] != q[i])
{
IsCorrect = false;
break;
}
}
if (IsCorrect)
break;
b++;
} while (next_permutation(A));
// Print difference
System.out.print(Math.abs(a - b) + "\n");
}
static boolean next_permutation(int[] p)
{
for(int a = p.length - 2; a >= 0; --a)
if (p[a] < p[a + 1])
for(int b = p.length - 1;; --b)
if (p[b] > p[a])
{
int t = p[a];
p[a] = p[b];
p[b] = t;
for(++a, b = p.length - 1;
a < b; ++a, --b)
{
t = p[a];
p[a] = p[b];
p[b] = t;
}
return true;
}
return false;
}
// Driver Code
public static void main(String[] args)
{
// Given array P[]
int[] p = { 1, 3, 2 };
// Given array Q[]
int[] q = { 3, 1, 2 };
// Given size
int n = p.length;
// Function call
findDifference(p, q, n);
}
}
// This code is contributed by Rajput-Ji
Python3
# Python3 program for the above approach # Function the print the difference # between the lexicographical ranks def findDifference(p, q, N): # Store the permutations # in lexicographic order A = [0] * N # Initial permutation for i in range(N): A[i] = i + 1 # Initial variables IsCorrect = False a, b = 1, 1 # Check permutation while True: IsCorrect = True for i in range(N): if (A[i] != p[i]): IsCorrect = False break if (IsCorrect): break a += 1 if (not next_permutation(A)): break # Initialize second permutation for i in range(N): A[i] = i + 1 # Check permutation while True: IsCorrect = True for i in range(N): if (A[i] != q[i]): IsCorrect = False break if (IsCorrect): break b += 1 if (not next_permutation(A)): break # Print difference print(abs(a - b)) def next_permutation(p): for a in range(len(p) - 2, -1, -1): if (p[a] < p[a + 1]): b = len(p) - 1 while True: if (p[b] > p[a]): t = p[a] p[a] = p[b] p[b] = t a += 1 b = len(p) - 1 while a < b: t = p[a] p[a] = p[b] p[b] = t a += 1 b -= 1 return True b -= 1 return False # Driver Code # Given array P[] p = [ 1, 3, 2 ] # Given array Q[] q = [ 3, 1, 2 ] # Given size n = len(p) # Function call findDifference(p, q, n) # This code is contributed by divyeshrabadiya07
C#
// C# program for the above approach
using System;
class GFG{
// Function the print the difference
// between the lexicographical ranks
static void findDifference(int[] p,
int[] q,
int N)
{
// Store the permutations
// in lexicographic order
int[] A = new int[N];
// Initial permutation
for(int i = 0; i < N; i++)
A[i] = i + 1;
// Initial variables
bool IsCorrect;
int a = 1, b = 1;
// Check permutation
do
{
IsCorrect = true;
for(int i = 0; i < N; i++)
{
if (A[i] != p[i])
{
IsCorrect = false;
break;
}
}
if (IsCorrect)
break;
a++;
} while (next_permutation(A));
// Initialize second permutation
for(int i = 0; i < N; i++)
A[i] = i + 1;
// Check permutation
do
{
IsCorrect = true;
for(int i = 0; i < N; i++)
{
if (A[i] != q[i])
{
IsCorrect = false;
break;
}
}
if (IsCorrect)
break;
b++;
} while (next_permutation(A));
// Print difference
Console.Write(Math.Abs(a - b) + "\n");
}
static bool next_permutation(int[] p)
{
for(int a = p.Length - 2; a >= 0; --a)
if (p[a] < p[a + 1])
for(int b = p.Length - 1;; --b)
if (p[b] > p[a])
{
int t = p[a];
p[a] = p[b];
p[b] = t;
for(++a, b = p.Length - 1;
a < b; ++a, --b)
{
t = p[a];
p[a] = p[b];
p[b] = t;
}
return true;
}
return false;
}
// Driver Code
public static void Main(String[] args)
{
// Given array P[]
int[] p = { 1, 3, 2 };
// Given array Q[]
int[] q = { 3, 1, 2 };
// Given size
int n = p.Length;
// Function call
findDifference(p, q, n);
}
}
// This code is contributed by Amit Katiyar
Javascript
<script>
// javascript program for the above approach
// Function the print the difference
// between the lexicographical ranks
function findDifference(p, q , N)
{
// Store the permutations
// in lexicographic order
var A = Array(N).fill(0);
// Initial permutation
for (var i = 0; i < N; i++)
A[i] = i + 1;
// Initial variables
var IsCorrect;
var a = 1, b = 1;
// Check permutation
do {
IsCorrect = true;
for (i = 0; i < N; i++) {
if (A[i] != p[i]) {
IsCorrect = false;
break;
}
}
if (IsCorrect)
break;
a++;
} while (next_permutation(A));
// Initialize second permutation
for (i = 0; i < N; i++)
A[i] = i + 1;
// Check permutation
do {
IsCorrect = true;
for (i = 0; i < N; i++) {
if (A[i] != q[i]) {
IsCorrect = false;
break;
}
}
if (IsCorrect)
break;
b++;
} while (next_permutation(A));
// Print difference
document.write(Math.abs(a - b) + "\n");
}
function next_permutation(p) {
for (a = p.length - 2; a >= 0; --a)
if (p[a] < p[a + 1])
for (b = p.length - 1;; --b)
if (p[b] > p[a]) {
var t = p[a];
p[a] = p[b];
p[b] = t;
for (++a, b = p.length - 1; a < b; ++a, --b) {
t = p[a];
p[a] = p[b];
p[b] = t;
}
return true;
}
return false;
}
// Driver Code
// Given array P
var p = [ 1, 3, 2 ];
// Given array Q
var q = [ 3, 1, 2 ];
// Given size
var n = p.length;
// Function call
findDifference(p, q, n);
// This code is contributed by umadevi9616
</script>
Producción:
3
Complejidad temporal: O(N * max(a, b)) donde N es el tamaño dado de las permutaciones y ayb son los rangos lexicográficos de las permutaciones.
Espacio Auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por grand_master y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA