función std :: next_permutation () con ejemplo en STL C ++

En este artículo, vamos a ver cuál es la función next_permutation STL () y cuál es el uso de la misma y cómo usarlo en un programa?

std :: next_permutation ()

next_permutation () es una función STL que busca la siguiente permutación lexicográfica class un determinado permutación.

una permutación es una disposición particular class un conjunto dado de números. Por ejemplo, tenemos un conjunto de n números donde n! permutaciones son posibles. for ejemplo, si el conjunto de números son {1, 2, 3} a continuación,

Las permutaciones ordenadas en orden lexicográfico serán,

Permutación 1: 1, 2, 3
Permutación 2: 1, 3, 2
Permutación 3: 2, 1, 3
Permutación 4: 2, 3, 1
Permutación 5: 3, 1, 2
Permutación 6: 3, 2, 1

los anteriores son seis permutaciones que se pueden generar a partir de la arriba mencionado set de ejemplo. También, las permutaciones están clasificadas lexicográfico que significa que el siguiente permutación de permutación 1 es permutación 2 y la permutación 6 no tiene próximo permutación ya que es el uno más alto.

La función STL next_permutation () nos ayuda a encontrar el siguiente permutación for una permutación dada. A continuación se muestra la sintaxis For next_permutation ()

bool next_permutation(
BidirectionalIterator first,
BidirectionalIterator last
);

Parámetros:

  • BidirectionalIterator primera – a partir iterador a la permutación de secuencia
  • BidirectionalIterator última – terminando iterador a la secuencia de permutación

for tipo: bool

Devuelve true si encuentra la siguiente permutación y cambia la secuencia de permutación actual en su lugar a la siguiente secuencia de permutación. Devuelve falso, si no se encuentra al lado de permutación.

Ejemplo y uso:

A continuación se muestra el programa de ejemplo donde hemos utilizado la función STL anteriormente para calcular siguiente permutación.

1) Buscar la siguiente permutación

En el siguiente programa vamos a encontrar la siguiente permutación usando la función STL recién discutido anteriormente.

#include <bits/stdc++.h>
using namespace std;
void print(vector<int>& nums)
{
for (auto it : nums)
cout << it << " ";
cout << endl;
}
int main()
{
cout << "Enter number of elements in the permutationn";
int n;
cin >> n;
cout << "Input the permutationsn";
vector<int> nums(n);
for (int i = 0; i < n; i++)
cin >> nums[i];
//next_permutation returns true if it's
//able to find the next permutation
//changes the permutation in place to the
//next permutation
if (next_permutation(nums.begin(), nums.end())) {
cout << "The next permutation is:n";
print(nums);
}
else
cout << "No next permutation foundn";
return 0;
}

Salida:

Enter number of elements in the permutation
3
Input the permutations
2 1 3
The next permutation is:
2 3 1

2) Encuentra todas las permutaciones lexicográfico

También podemos encontrar todas las permutaciones lexicográfico utilizando next_permutation (). for ejemplo, todas las permutaciones class n = 3 en orden lexicográfico será

Permutación 1: 1, 2, 3
Permutación 2: 1, 3, 2
Permutación 3: 2, 1, 3
Permutación 4: 2 , 3, 1
Permutación 5: 3, 1, 2
Permutación 6: 3, 2, 1

#include <bits/stdc++.h>
using namespace std;
void print(vector<int>& nums)
{
for (auto it : nums)
cout << it << " ";
cout << endl;
}
int main()
{
cout << "Enter number of elements in the permutationn";
int n;
cin >> n;
//first permutation is 1,2,3,4...,n
vector<int> nums(n);
for (int i = 0; i < n; i++)
nums[i] = i + 1;
int count = 1;
//the while loop will break when no more
//next Permutation is possible
//as the function next_permutation will
//return false then
do {
cout << "Permutation " << count++ << endl;
print(nums);
} //in places converts to next permutation if there exists the next permutation
while (next_permutation(nums.begin(), nums.end()));
return 0;
}

de salida:

Enter number of elements in the permutation
3
Permutation 1
1 2 3
Permutation 2
1 3 2
Permutation 3
2 1 3
Permutation 4
2 3 1
Permutation 5
3 1 2
Permutation 6
3 2 1

lo anterior next_permutation () se comparaban basado en la ‘& gt ;’ operador mientras que podemos extender la sintaxis mediante la adición de función de comparación definida por el usuario para el trabajo en los objetos definidos por el usuario también.

bool next_permutation(
BidirectionalIterator first,
BidirectionalIterator last,
Comparator comp);


Deja un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *