Ankündigung

Einklappen
Keine Ankündigung bisher.

Alle Kombinationen berechnen (vgl. Urne mit Zurücklegen)

Einklappen

Neue Werbung 2019

Einklappen
X
  • Filter
  • Zeit
  • Anzeigen
Alles löschen
neue Beiträge

  • Alle Kombinationen berechnen (vgl. Urne mit Zurücklegen)

    Guten Abend phpler

    Folgendes Problem: Ich habe eine Tabelle mit dynamischer Größe, deren Felder mit bestimmten Werten gefüllt werden können. Die selben Werte können mehrfach auftreten, vergleichbar mit dem Urnenmodell mit Zurücklegen. Nun geht es darum, einen Algorithmus zu finden, der mir alle Möglichkeiten ausgibt. Ungefähr so:

    [1|0|0] [2|0|0] [3|0|0] [1|0|0] [1|1|0]
    [0|0|0] [0|0|0] [0|0|0] [0|0|0] [0|0|0]
    [0|0|0] [0|0|0] [0|0|0] [0|0|0] [0|0|0]

    ..... (6561 Möglichkeiten)

    [3|3|3] [3|3|3] [3|3|3] [3|3|3]
    [3|3|3] [3|3|3] [3|3|3] [3|3|3]
    [3|3|0] [3|3|1] [3|3|2] [3|3|3]


    Das ganze Programm wird später warscheinlich in C/C++ umgesetzt um performanter zu sein und auf mehreren Rechnern (Kein richtiges Cluster) laufen. (Momentan in PHP, weil ich darin schneller entwickeln kann.) Deßhalb ist es wichtig, dass ich dem Algorithmus sagen kann, ab welchem Zustand er anfangen soll die folgenden Möglichkeiten zu berechnen.

    Im Endeffekt soll das ganze bei einer größeren Tabelle mit mehr Möglichkeiten geschehen, die ingesamt 78 886 090 522 101 180 541 172 856 528 278 622 967 320 643 510 902 300 477 027 893 066 406 250 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 Möglichkeiten erzeugt.


    Meine bisherige Überlegung ist, als Basis von allem die Felder von oben links nach unten recht durchzugehen:

    PHP-Code:
    for($w 0$w <= $width$w++) {
        
        for(
    $h 0$h <= $height$h++) {
        
        }

    Und genau jetzt fängt es an, dass mein Kopf abraucht... :/ Innerhalb des ganzen müssen alle Möglichkeiten abgedeckt werden, die ein Feld annehmen kann:

    PHP-Code:
    $width 3;
    $height 3;

    $modes = array(0123);
    $modeAmmount count($modes);

    $table = array();

    for(
    $w 0$w <= $width$w++) {
        
        for(
    $h 0$h <= $height$h++) {

            for(
    $m 0$m $modeAmmount$m++) {

                
            }
        }

    Damit werden aber halt nicht mal ansatzweise alle Möglichkeiten abgedeckt. Kann mir jemand damit helfen, egal ob ein Link zu einem ähnlichen Problem oder ein Stichwort, nachdem ich suchen kann?


    Dankeschön

    Gruß Rod

  • Geromel
    antwortet
    du kannst ja mal anfangen, und die Zeit stoppen. Wenn du dann durch bist, sagst du uns wie lang du gebraucht hast.

    Einen Kommentar schreiben:


  • Rodney McKay
    antwortet
    Zitat von tr0y Beitrag anzeigen
    nicht zu vergessen die energie die für das betreiben der rechner notwendig wäre, aber das ist wohl seine kleinste sorge. Die haben ja zpms auf atlantis.
    xD

    Einen Kommentar schreiben:


  • tr0y
    antwortet
    Zitat von lstegelitz Beitrag anzeigen
    Diese Zahl ist größer als die Anzahl der Atome im (sichtbaren) Universum, welche mit ca. 10^80 geschätzt wird.

    Das wird also ein enormes Platzproblem geben, ganz abgesehen davon, das für diese Anzahl Rechner gar nicht genug Material existiert
    Nicht zu vergessen die Energie die für das Betreiben der Rechner notwendig wäre, aber das ist wohl seine kleinste Sorge. Die haben ja ZPMs auf Atlantis.

    Einen Kommentar schreiben:


  • Gast-Avatar
    Ein Gast antwortete
    Zitat von lstegelitz Beitrag anzeigen
    Diese Zahl ist größer als die Anzahl der Atome im (sichtbaren) Universum, welche mit ca. 10^80 geschätzt wird.

    Das wird also ein enormes Platzproblem geben, ganz abgesehen davon, das für diese Anzahl Rechner gar nicht genug Material existiert
    na und, dann hohl ich mir halt die teile aus nen neuen universum, oder ich mach nen thread für teile auf, oder so.

    Einen Kommentar schreiben:


  • Blar
    antwortet
    Wäre es bei so einem geringen Umfang auch brauchbar die Kombinationen wie folgt zu ermitteln. Müsste natürlich noch entsprechend formatiert werden.

    PHP-Code:
    $modes 4;
    $fields 9;
    $count $modes ** $fields;

    for(
    $i=0$i<$count$i++) {
        
    $converted base_convert($i10$modes);
        
    $string sprintf('%-0'.$fields.'s'$converted);
        
    var_dump($string);

    Einen Kommentar schreiben:


  • lstegelitz
    antwortet
    E+155
    Diese Zahl ist größer als die Anzahl der Atome im (sichtbaren) Universum, welche mit ca. 10^80 geschätzt wird.

    Das wird also ein enormes Platzproblem geben, ganz abgesehen davon, das für diese Anzahl Rechner gar nicht genug Material existiert

    Einen Kommentar schreiben:


  • jspit
    antwortet
    Schlimm, immer wird mit blöden Fakten hier im Forum gestichelt.
    Wenn seine Berechnung auf 9.1303363E+155 Rechner verteilt wird, ist er an einem Tag durch.

    Einen Kommentar schreiben:


  • Geromel
    antwortet
    ich darf drauf aufmerksam machen, dass allein wenn du für pro 1 Million Abfragen 1 Millisekunde an Ausführungszeit hättest, es trotzdem unfassbare 2.501462e+153 Jahre dauert, bis du einmal durch bist. Wenn du so lang lebst, dann kannst du das ja machen.

    Einen Kommentar schreiben:


  • tr0y
    antwortet
    Klingt nach nem monumentalen Timewaste

    Einen Kommentar schreiben:


  • Rodney McKay
    antwortet
    Zitat von tr0y Beitrag anzeigen
    Dann kauf dir Festplatten die die Kapazität haben 78 886 090 522 101 180 541 172 856 528 278 622 967 320 643 510 902 300 477 027 893 066 406 250 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 zu speichern.
    Das ganze wird auf mehreren Rechnern laufen und nur die sinnvollen (ein Bruchteil davon) gespeichert.

    Einen Kommentar schreiben:


  • tr0y
    antwortet
    Dann kauf dir Festplatten die die Kapazität haben 78 886 090 522 101 180 541 172 856 528 278 622 967 320 643 510 902 300 477 027 893 066 406 250 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 zu speichern.

    Einen Kommentar schreiben:


  • Rodney McKay
    antwortet
    Nice, danke!

    Die Frage ist welchen Sinn es macht so eine große Maße an Daten zu aggregieren. Was ist denn das Ziel der Anwendung oder der Konkrete Anwendungsfall dieser Datensätze ?
    Es steckt kein großer Sinn dahinter, möchte nur was testen.

    Einen Kommentar schreiben:


  • tr0y
    antwortet
    http://php-de.github.io/jumpto/kombinatorik-loesungen/

    Die Frage ist welchen Sinn es macht so eine große Maße an Daten zu aggregieren. Was ist denn das Ziel der Anwendung oder der Konkrete Anwendungsfall dieser Datensätze ?

    Einen Kommentar schreiben:

Lädt...
X