3. Kombinatorik Algorithmus - Denkblockade

Kombinatorik Algorithmus - Denkblockade

  • B

    volkard schrieb:

    Blue-Tiger schrieb:

    Was du machen koenntest: erstell alle Permutationen, merk dir aber immer nur die hintersten 3 Zahlen der aktuellen Permutation. (Damit erhaelst du Ergebnisse doppelt, aber die kannst du ja leicht eliminieren, z. B. durch std::unique oder std::set).

    Bei 3 aus 26 (3 Buchstaben) leider nicht doppelt, sondern 155112100433309859840000-fach.
    Ich glaube, da reicht mein RAM nicht. Ups, die Festplatte auch nicht, Mist, muß mit noch schnell (bei 26 Byte pro Zwischenergebnis) 10 Billiarden Terabyte-Platten kaufen und ein kleines Kraftwerk. Ich fürchte, Amazon hat beides nicht vorrätig. Was mache ich denn da jetzt?

    Ergebnis einfach gleich in ein std:set stopfen, und dann halt ganz lang warten bis die ganzen Permutationen durch sind. Aber ich seh schon, du willst drauf hinaus dass es 'ne bessere Loesung gibt, also warum nicht raus damit? 😉

    0
  • V

    Blue-Tiger schrieb:

    Aber ich seh schon, du willst drauf hinaus dass es 'ne bessere Loesung gibt,

    Nö, eigentlich wollte ich darauf hinaus, daß man sich nicht immer an die Standardbibliothek hängen muß.

    Blue-Tiger schrieb:

    also warum nicht raus damit? 😉

    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.

    #include <iostream>
using namespace std;

void print(int feld[],int anzahl){
	for(int i=0;i<anzahl;++i)
		cout<<feld[i]<<' ';
	cout<<'\n';
}

void test(int feld[],int n,int k,int pos,int val){
	if(pos==k)
		return print(feld,k);
	for(int i=val;i<n;++i){
		feld[pos]=i;
		test(feld,n,k,pos+1,i+1);
	}
}

int main(){
	int feld[3];
	test(feld,5,3,0,0);
	return 0;
}
    0
  • S

    Super 😃
    Vielen Dank, dass funktioniert perfekt.
    Jetzt den Code mal genau anschaun und verstehen, wo meine Denkfehler waren.
    Vielen Dank,

    Samu

    0
  • K

    Muss es denn in C oder C++ sein? Mir fallen da zwei Zeilen Haskellcode ein, kann sie aber grad nicht testen.

    0
  • S

    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

    0
  • H

    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.

    0
  • V

    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.

    0
  • K

    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.

    0
  • ?

    knivil schrieb:

    Hier der versprochene Zweizeiler in Haskell
    [...]

    Gibt's in Haskell kein amb ?
    🙂

    0
  • K

    Meinst du McCarthy's Ambiguous Operator? Und was sollte er besser machen? Der vorgestellte Zweizeiler benutzt kein backtracking.

    0
  • ?

    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.
    🙂

    0
  • K

    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.

    0
Anmelden zum Antworten