std:: siguiente Explicación de la Implementación de la permutación
Tenía curiosidad por cómo se implementó std:next_permutation, así que extraje la versión gnu libstdc++ 4.7 y desinfecté los identificadores y el formato para producir la siguiente demostración...
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
template<typename It>
bool next_permutation(It begin, It end)
{
if (begin == end)
return false;
It i = begin;
++i;
if (i == end)
return false;
i = end;
--i;
while (true)
{
It j = i;
--i;
if (*i < *j)
{
It k = end;
while (!(*i < *--k))
/* pass */;
iter_swap(i, k);
reverse(j, end);
return true;
}
if (i == begin)
{
reverse(begin, end);
return false;
}
}
}
int main()
{
vector<int> v = { 1, 2, 3, 4 };
do
{
for (int i = 0; i < 4; i++)
{
cout << v[i] << " ";
}
cout << endl;
}
while (::next_permutation(v.begin(), v.end()));
}
La salida es la esperada: http://ideone.com/4nZdx
Mis preguntas son: ¿Cómo funciona? ¿Cuál es el significado de i, j y k? ¿Qué valor tienen en las diferentes partes de la ejecución? ¿Qué es un bosquejo de una prueba de su exactitud?
Claramente antes de entrar en el bucle principal simplemente comprueba los casos triviales de la lista de elementos 0 o 1. En la entrada del bucle principal i está apuntando al último elemento (no un extremo pasado) y la lista tiene al menos 2 elementos de largo.
¿Qué está pasando en el cuerpo del bucle principal?
5 answers
Veamos algunas permutaciones:
1 2 3 4
1 2 4 3
1 3 2 4
1 3 4 2
1 4 2 3
1 4 3 2
2 1 3 4
...
¿Cómo pasamos de una permutación a la siguiente? En primer lugar, veamos las cosas un poco diferente. Podemos ver los elementos como dígitos y las permutaciones como números. Viendo el problema de esta manera queremos ordenar las permutaciones/números en orden "ascendente" .
Cuando pedimos números queremos "aumentarlos en la cantidad más pequeña". Por ejemplo, cuando contamos no contamos 1, 2, 3, 10, ... porque todavía hay 4, 5, ... en el medio y aunque 10 es más grande que 3, hay números que faltan que se pueden conseguir aumentando 3 por una cantidad más pequeña. En el ejemplo anterior vemos que 1 permanece como el primer número durante mucho tiempo, ya que hay muchos reordenamientos de los últimos 3 "dígitos" que "aumentan" la permutación en una cantidad menor.
Entonces, ¿cuándo finalmente "usamos" el 1? Cuando solo no hay más permutaciones de los últimos 3 dígitos.
Y cuando no hay más permutaciones de los últimos 3 dígitos? Cuando los últimos 3 dígitos están en orden descendente.
Aha! Esto es clave para entender el algoritmo. Solo cambiamos la posición de un" dígito "cuando todo a la derecha está en orden descendente porque si no está en orden descendente, entonces todavía hay más permutaciones para ir (es decir, podemos "aumentar" la permutación en una cantidad menor).
Volvamos ahora al código:
while (true)
{
It j = i;
--i;
if (*i < *j)
{ // ...
}
if (i == begin)
{ // ...
}
}
Desde las primeras 2 líneas en el bucle, j es un elemento y i es el elemento anterior.
Entonces, si los elementos están en orden ascendente, (if (*i < *j)) haz algo.
De lo contrario, si todo está en orden descendente, (if (i == begin)) entonces esta es la última permutación.
De lo contrario, continuamos y vemos que j e i están esencialmente decrementados.
Ahora entendemos la parte if (i == begin) así que todo lo que necesitamos entender es la parte if (*i < *j).
También tenga en cuenta: "Entonces si los elementos están en orden ascendente ..." que apoya nuestra observación anterior de que solo necesitamos hacer algo a un dígito "cuando todo a la derecha está en orden descendente". La declaración de orden ascendente if es esencialmente encontrar el lugar más a la izquierda donde "todo a la derecha está en orden descendente".
Veamos de nuevo algunos ejemplos:
...
1 4 3 2
2 1 3 4
...
2 4 3 1
3 1 2 4
...
Vemos que cuando todo a la derecha de un dígito está en orden descendente, encontramos el siguiente dígito más grande y lo ponemos al frente y luego ponemos los dígitos restantes en orden ascendente .
Veamos el código:
It k = end;
while (!(*i < *--k))
/* pass */;
iter_swap(i, k);
reverse(j, end);
return true;
Bueno, ya que las cosas de la derecha están en orden descendente, para encontrar el "siguiente dígito más grande" solo tenemos que iterar desde el final, que vemos en las primeras 3 líneas de código.
A continuación, intercambiamos el "siguiente dígito más grande" al frente con la declaración iter_swap() y luego, como sabemos que ese dígito era el siguiente más grande, sabemos que los dígitos a la derecha todavía están en orden descendente, por lo que para ponerlo en orden ascendente, solo tenemos que reverse().
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2016-01-14 23:58:09
La implementación de gcc genera permutaciones en orden lexicográfico. Wikipedia lo explica de la siguiente manera:
El siguiente algoritmo genera la siguiente permutación lexicográficamente después de una permutación dada. Cambia lo dado permutación en el lugar.
- Encuentre el índice más grande k tal que a[k]
- Encuentre el índice más grande l tal que a[k]
- Intercambiar a[k] por a[l].
- Invertir la secuencia desde a[k + 1] hasta e incluyendo el elemento final a[n].
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2012-07-14 10:56:23
Knuth profundiza en este algoritmo y sus generalizaciones en las secciones 7.2.1.2 y 7.2.1.3 de El Arte de la Programación Informática. Lo llama "Algoritmo L" apparently aparentemente se remonta al siglo 13.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2014-08-25 17:05:48
Aquí hay una implementación completa usando otros algoritmos de biblioteca estándar:
template <typename I, typename C>
// requires BidirectionalIterator<I> && Compare<C>
bool my_next_permutation(I begin, I end, C comp) {
auto rbegin = std::make_reverse_iterator(end);
auto rend = std::make_reverse_iterator(begin);
auto next_unsorted = std::is_sorted_until(rbegin, rend, comp);
bool at_final_permutation = (next_unsorted == rend);
if (!at_final_permutation) {
auto next_permutation = std::upper_bound(
rbegin, next_unsorted, *next_unsorted, comp);
std::iter_swap(next_unsorted, next_permutation);
}
std::reverse(rbegin, next_unsorted);
return !at_final_permutation;
}
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2018-06-13 12:49:35
Existe una posible implementación que se explica por sí misma en cppreference usando <algorithm>.
template <class Iterator>
bool next_permutation(Iterator first, Iterator last) {
if (first == last) return false;
Iterator i = last;
if (first == --i) return false;
while (1) {
Iterator i1 = i, i2;
if (*--i < *i1) {
i2 = last;
while (!(*i < *--i2));
std::iter_swap(i, i2);
std::reverse(i1, last);
return true;
}
if (i == first) {
std::reverse(first, last);
return false;
}
}
}
Cambie el contenido a la siguiente permutación lexicográfica (in-place) y devuelva true si existe de otro modo sort y devuelva false si no existe.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2015-09-22 16:34:57