next_permutationen
-
hi,
wie funktioniert next_permutation?
-
-
edith: wie schreibe ich eine eigene next_permutation - funktion?
-
Aso...
Ändere die letzte Stelle von A bis Z.
Setze die zweite eins weiter.
Ändere die letzte Stelle von A bis Z.
Setze die zweite eins weiter.
...
Setze die dritte eins weiter.
...
...
...
...
Oder so ähnlich...Grüsse
Edith Piaf
(was sollte der Link?)
-
äh, jo, das ist aber keine permutation sondern normalse "zählen"...
ich brauche einen algo, der mir zu einer gegebenen permutation die "nächste" gibt, (wobei die nummerierung egal ist.) google gibt irgendwie nur hingefrickelte quelltexte ohne schöne erklärung her...1310-Logik schrieb:
Edith Piaf
(was sollte der Link?)nichts, nur so.
-
Schau dir doch den Quelltest von next_permutation in deiner STL-Lib an. Erklärung gibt es da auch keine aber du hast einen Algorithmus.
Hier hast du ja einen Algorithmus. Du mußt ihn nur noch programmieren.
http://www.wiwi.uni-bielefeld.de/~wolf/lehre/ws0304/aud0304/nextperm/nextperm.html
-
Kannst dir ja mal die Implementierung vom vc anschauen, die haben die funktionen immer mit ein paar Kommentaren versehen, allerdings sollte man zum tieferen Verständnis auch ruhig mal mit dem Debugger durch den Code durchgehen.
// TEMPLATE FUNCTION next_permutation template<class _BidIt> inline bool next_permutation(_BidIt _First, _BidIt _Last) { // permute and test for pure ascending, using operator< _BidIt _Next = _Last; if (_First == _Last || _First == --_Next) return (false); for (; ; ) { // find rightmost element smaller than successor _BidIt _Next1 = _Next; if (*--_Next < *_Next1) { // swap with rightmost element that's smaller, flip suffix _BidIt _Mid = _Last; for (; !(*_Next < *--_Mid); ) ; std::iter_swap(_Next, _Mid); std::reverse(_Next1, _Last); return (true); } if (_Next == _First) { // pure descending, flip all std::reverse(_First, _Last); return (false); } } }