Byłem ciekawy, jak std:next_permutation
został zaimplementowany, więc wyodrębniłem gnu libstdc++ 4.7
wersję i wyczyściłem identyfikatory i formatowanie, aby utworzyć następujące demo ...
#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()));
}
Dane wyjściowe są zgodne z oczekiwaniami: http://ideone.com/4nZdx
Moje pytania to: jak to działa? Co to ma znaczyć i
, j
i k
? Jaką wartość mają w różnych częściach egzekucji? Czym jest szkic dowodu jego poprawności?
Najwyraźniej przed wejściem do głównej pętli sprawdza tylko trywialne przypadki z listą elementów 0 lub 1. Na wejściu głównej pętli i wskazuje na ostatni element (nie jeden poza koniec), a lista ma co najmniej 2 elementy.
Co się dzieje w głównej pętli?
c++
c++11
permutation
stl-algorithm
lexicographic
Andrew Tomazos
źródło
źródło
Odpowiedzi:
Spójrzmy na kilka permutacji:
Jak przechodzimy od jednej permutacji do drugiej? Po pierwsze, spójrzmy na to trochę inaczej. Możemy zobaczyć elementy jako cyfry, a permutacje jako liczby . Patrząc na problem w ten sposób , chcemy uporządkować permutacje / liczby w porządku „rosnącym” .
Zamawiając numery chcemy „zwiększyć je o najmniejszą ilość”. Na przykład podczas liczenia nie liczymy 1, 2, 3, 10, ... ponieważ nadal jest 4, 5, ... pomiędzy i chociaż 10 jest większe niż 3, brakuje liczb, które można uzyskać przez zwiększenie 3 o mniejszą kwotę. W powyższym przykładzie widzimy, że
1
pozostaje jako pierwsza liczba przez długi czas, ponieważ istnieje wiele zmian kolejności ostatnich 3 „cyfr”, które „zwiększają” permutację o mniejszą wartość.Kiedy więc w końcu „używamy”
1
? Gdy nie ma już tylko permutacji ostatnich 3 cyfr.A kiedy nie będzie już permutacji ostatnich 3 cyfr? Gdy ostatnie 3 cyfry są w porządku malejącym.
Aha! To klucz do zrozumienia algorytmu. Zmieniamy pozycję „cyfry” tylko wtedy, gdy wszystko po prawej stronie jest w porządku malejącym, ponieważ jeśli nie jest w porządku malejącym, to jest jeszcze więcej permutacji do przejścia (tj. Możemy „zwiększyć” permutację o mniejszą wartość) .
Wróćmy teraz do kodu:
Od pierwszych 2 wierszy w pętli
j
jest elementem ii
jest elementem przed nim.Następnie, jeśli elementy są w porządku rosnącym, (
if (*i < *j)
) zrób coś.W przeciwnym razie, jeśli całość jest w porządku malejącym (
if (i == begin)
), to jest to ostatnia permutacja.W przeciwnym razie kontynuujemy i widzimy, że j oraz i są zasadniczo dekrementowane.
Teraz rozumiemy
if (i == begin)
część, więc wszystko, co musimy zrozumieć, toif (*i < *j)
część.Zwróć również uwagę: „Wtedy, jeśli elementy są w porządku rosnącym…”, co potwierdza naszą poprzednią obserwację, że wystarczy zrobić coś z cyfrą, „gdy wszystko po prawej stronie jest w porządku malejącym”. Wyrażenie w kolejności rosnącej
if
zasadniczo polega na znajdowaniu skrajnego lewego miejsca, w którym „wszystko po prawej stronie jest w porządku malejącym”.Spójrzmy ponownie na kilka przykładów:
Widzimy, że gdy wszystko na prawo od cyfry jest w porządku malejącym, znajdujemy następną największą cyfrę i umieszczamy ją na początku, a pozostałe cyfry układamy rosnąco .
Spójrzmy na kod:
Cóż, ponieważ elementy po prawej stronie są w porządku malejącym, aby znaleźć „następną największą cyfrę”, musimy po prostu powtórzyć iterację od końca, co widzimy w pierwszych 3 wierszach kodu.
Następnie zamieniamy „następną największą cyfrę” na początek
iter_swap()
stwierdzeniem, a ponieważ wiemy, że ta cyfra była następną co do wielkości, wiemy, że cyfry po prawej stronie są nadal w porządku malejącym, więc ustawimy je w porządku rosnącym, po prostu musimy toreverse()
zrobić.źródło
Combinatorics
, ale jest to najbardziej klasyczny.Implementacja gcc generuje permutacje w porządku leksykograficznym. Wikipedia wyjaśnia to następująco:
źródło
Knuth szczegółowo omawia ten algorytm i jego uogólnienia w sekcjach 7.2.1.2 i 7.2.1.3 książki The Art of Computer Programming . Nazywa go „Algorytmem L” - podobno pochodzi z XIII wieku.
źródło
Oto pełna implementacja przy użyciu innych standardowych algorytmów bibliotecznych:
Próbny
źródło
is_final_permutation
zawiera więcej informacji niżbegin == end - 1
. Wywołanieis_sorted_until
/upper_bound
oddziela logikę permutacji od tych operacji i sprawia, że jest to znacznie bardziej zrozumiałe. Dodatkowo upper_bound jest wyszukiwaniem binarnym, podczas gdywhile (!(*i < *--k));
jest liniowe, więc jest bardziej wydajne.Istnieje oczywista możliwa implikacja dotycząca używania cppreference
<algorithm>
.Zmień zawartość na następną permutację leksykograficzną (lokalną) i zwróć wartość true, jeśli istnieje, w przeciwnym razie sortuj i zwróć false, jeśli nie istnieje.
źródło