Kombinatorik Algorithmus - Denkblockade
-
Super
Vielen Dank, dass funktioniert perfekt.
Jetzt den Code mal genau anschaun und verstehen, wo meine Denkfehler waren.
Vielen Dank,Samu
-
Muss es denn in C oder C++ sein? Mir fallen da zwei Zeilen Haskellcode ein, kann sie aber grad nicht testen.
-
Es sollte schon sehr schnell laufen. Soweit ich weiß hat Python 3.1 das auch direkt implementiert.
Ich schreibe am liebsten in C++, da das natürlich nur ein Teil des gesamten Algorithmus ist, und ich nicht einfach so ausweichen kann.
Vielen Dank an alle
Viele Grüße,
Samu
-
volkard schrieb:
Weil ich sofort sah, daß next_permutation nicht paßt. Und ich hatte selber keine Lösung, das Problem löst nämlich tatsächlich Denkblockaden aus.
@Volkard
Hab vor Jahren hier mal ne next_permutation-ähnliche Variante von next_combination
geschrieben:
http://www.c-plusplus.net/forum/viewtopic-var-t-is-193087 (letzter Beitrag)Achtung: Ist aber etwas buggy, d.h. funktioniert so nicht, falls die Eingabesequenz Elemente doppelt enthält. Ich hatte den Code irgendwann auch
mal gefixed, finde es aber nicht mehr.
-
HumeSikkins schrieb:
Hab vor Jahren
In der Tat!
HumeSikkins schrieb:
next_permutation-ähnliche Variante von next_combination
Ja, die hatte ich auch im Auge. Aber ich dillematisierte furchtbar zwischen "n Elemente nehmen, wo nur k gebraucht werden" und "nur rekursiv gehen und die Nutzanwendung per Dingens bis runter reinschubsen"; ich habe mich für "bald gibt es ja alles, und reinschubsen tut nicht mehr so weh (vielleicht)" entschieden.
-
Hier der versprochene Zweizeiler in Haskell:
outOf 0 _ = [[]] outOf n xs = [ (a:as) | a <- xs, as <- outOf (n-1) $ tail $ dropWhile (/=a) xs ] *Main> 3 `outOf` [0..4] [[0,1,2],[0,1,3],[0,1,4],[0,2,3],[0,2,4],[0,3,4],[1,2,3],[1,2,4],[1,3,4],[2,3,4]]Diese Loesung funktioniert nur mit echten Mengen. Diese muessen aber nicht sortiert sein. Bei doppelten Eintraegen (Multiset) bildet man die Elemente auf ihre Indizes ab und wendet `outOf` auf die Indexmenge an. Da es in Haskell auch arrays gibt, laesst sich diese Abbildung effizient implementieren.
Aus dem obigen Code kann man auch eine Implementation fuer C++ (oder aehnliche ableiten). Dabei gewinnt man mittels a <- xs einen Iterator, den man direkt in `outOf` weiterverwenden kann. tail $ dropWhile (/=a) ... dient nur dafuer, den entsprechenden "Iterator" auf das Element hinter dem gerade ausgewaehlten zu setzen. Dadurch waere eine entsprechende Implementation mit Iteratoren effizienter.
Vielleicht werde ich es mal in C++ umsetzen.
-
knivil schrieb:
Hier der versprochene Zweizeiler in Haskell
[...]Gibt's in Haskell kein
amb?
-
Meinst du McCarthy's Ambiguous Operator? Und was sollte er besser machen? Der vorgestellte Zweizeiler benutzt kein backtracking.
-
knivil schrieb:
Meinst du McCarthy's Ambiguous Operator?
Ja.
knivil schrieb:
Und was sollte er besser machen? Der vorgestellte Zweizeiler benutzt kein backtracking.
Schon klar, aber ich versuch immer gern mal einen Ansatz, für den ich nicht nachdenken muss. Besser machen geht bekanntlich später immer noch.
-
Und wie wuerdest du es mittels amb formulieren, wenn dieser Operator zu Verfuegung steht?
Besser machen geht bekanntlich später immer noch.
Nur macht es kaum einer.