Alle Werte die mit n Würfeln mit m Seiten geworfen werden können in ein n Dimensionales Array

[2XS]

Hallo und einen schönen Samstagabend,

da ich das letzte Mal vor ca 5 Jahren etwas in Java programmiert habe bin ich wohl etwas eingerostet. Also setzt bei den Antworten bitte nicht zu viel Wissen meinerseits voraus, das kommt alles erst ganz langsam wieder.

Mein Problem: Für ein Programm, welches diverse Spielmechaniken eines bekannten Tabletops simulieren soll bräuchte ich eine Klasse Die (Würfel). In dieser Klasse möchte ich Wahrscheinlichkeiten ausrechnen, z. B. wie wahrscheinlich es ist mit 2 W6 eine 7 oder mehr zu Würfeln. Und da ich ungern halbe Sachen mache würde ich auch gerne gleich die Möglichkeit haben das Ganze auch für z. B. 4 W8 berechnen zu können.

Meine ersten Ansätze sahen so aus, dass ich es mit einer Rekursion versucht habe, welche nur die Anzahl an Möglichkeiten für einen Zielwert berechnet hat. Alle Versuche dazu sind aber kläglich gescheitert. Und da ich diese Methode auch für alle möglichen Werte unterhalb des Zielwertes hätte aufrufen müssen habe ich mir gedacht, dass es wohl sinnvoll wäre direkt im Konstruktor ein n-Dimensionales Array mit allen Möglichkeiten zu füllen die man mit n Würfeln werfen kann.

Die Länge des Arrays ist ja einfach zu berechnen, bei n W6 wäre es 6 hoch n.

Mir fällt aber absolut nicht ein wie ich einem Array dynamisch Dimensionen hinzufügen kann.

Und die nächste Frage, wie befülle ich das Array am geschicktesten? Iterativ scheidet ja aus, da ich vorher nicht weiß wie viele Würfel gewünscht sind und ich somit auch nicht weiß wie viele Schleifen ich verschachteln muss.

Bleibt also nur eine Rekursion, kann mir da jemand Tipps geben? Ich habe immer noch Knoten von den bisherigen Versuchen im Kopf. Oder gibt es bereits eine Klasse die das kann?


Vielen Dank an alle, die das alles bis hierher gelesen haben. Und noch mehr Dank an diejenigen, welche mir konstruktive Antworten geben.


Grüße,

Andy

 

[kirax]

Eine Dimension hinzufügen geht zwar über Umwege, aber ich frage mich, warum du das willst.

Du kannst doch einfach zuerst "fragen", was du für Würfel werfen willst (z.B. 2 W6), dann ein zweidimensionales Array der Länge 6x6 erzeugen, und die Ergebnisse der jeweiligen Würfe eintragen.
Dann zählst du einfach ab, wie viele Ergebnisse über deinem Wunschwert liegen (z.B. 7) oder wie viele Ergebnisse genau deinen Wunschwert treffen (oder was auch immer) und teilst das Ergebnis durch 36. Dann hast du deine Wahrscheinlichkeit.

Das ließe sich sicher noch optimieren (die Tabelle ist ja achsensymmetrisch zur Diagonalen, im Fall von 2 Würfeln), aber so erstmal als Grundgedanke.

 

[2XS]

Erstmal danke für die Antwort.

Ein Zweidimensionales Array erzeuge ich doch mit:

int[] liste = new int[36][36];

Wie kann ich das denn, wenn ich weiß, dass 4 Würfel verwendet werden sollen umwandeln in:

int n = 6*6*6*6;
int[] liste = new int[n][n][n][n];

Wie ich die Wahrscheinlichkeiten berechnen kann, sobald ich weiß wie viele Möglichkeiten da sind, weiß ich bereits. Mir geht es ja eben um genau die Berechnung der Möglichkeiten.

Ich habe mir halt gedacht, wenn ich ein Array mit allen möglichen Kombinationen für die Würfel habe müssen die Kombinationen nur einmal bei der Initialisierung der Klasse berechnet werden. Ich habe also eine gute Basis um alle Berechnungen für alle x Wy zu machen.
Wenn ich also diese Liste habe könnte ich einfach eine Schleife drüber laufen lassen und einen Counter höher zählen sobald die Summe der Augen kleiner oder gleich dem Mindestwurf sind, oder größer oder sonst was.


Grüße,

Andy

 

[Ark]

Auch wenn mir schleierhaft ist, warum man alle Kombinationen erzeugen wollen sollte: Ein n-dimensionales Array gibt es in Java nicht, aber du kannst mithilfe des Horner-Schemas relativ effizient Werte des dazugehörigen Polynoms berechnen. Diese Werte sind dann die Stellen in einem eindimensionalen Array, die du suchst. Das funktioniert so aber nur, wenn die Indizierung (wie in Java üblich) bei 0 beginnt:

// PSEUDOCODE-SKIZZEN
// Großbuchstabe X, Y, Z meint Anzahl Elemente
// Kleinbuchstabe x, y, z meint Index aus [0 ; X-1], [0 ; Y-1], [0 ; Z-1]

// Bei einem eindimensionalen Array ist die Sache noch einfach:
a = new int[X]
a(x) = a[x]

// jetzt zweidimensional:
a = new int[Y * X]
a(x, y) = a[(y * X) + x]

// dreidimensional:
a = new int[Z * Y * X]
a(x, y, z) = a[(((z * Y) + y) * X) + x]

// So weit alles verstanden? Dann mal vierdimensional:
a = new int[W * Z * Y * X]
a(x, y, z, w) = a[((((w * Z) + z) * Y) + y) * X) + x]

Ich hoffe, das hilft.

Ark

 

[kirax]

Ich verstehe nicht, warum du alles beim Initialisieren ausrechnen willst.
Das ist erstens ziemlich ineffizient und zweitens kein schöner Stil. Du schießt dir damit ins Bein

Ich würde es rekursiv machen und die bisher berechnete Wahrscheinlichkeit mitnehmen in die Rekursion.

 

[Firephoenix]

Ich verstehe nicht, warum du alles beim Initialisieren ausrechnen willst.
Das ist erstens ziemlich ineffizient und zweitens kein schöner Stil. Du schießt dir damit ins Bein

Ich würde es rekursiv machen und die bisher berechnete Wahrscheinlichkeit mitnehmen in die Rekursion.

Hi,
das man i.d.R. im Konstruktor ist noch einleuchtend, aber warum soll das ineffizienter sein?
Hast du im übrigen den Pseudocode-vermerk von ihm gesehen?
Gruß

 

[2XS]

Danke Ark, kirax und Firephoenix!

Leider hilft mir das Alles nicht weiter.

Bei Arks Lösung muss ich ja auch vorher schon wissen, für wie viele Würfel gerechnet werden soll. Bräuchte also ein SWITCH für 1 bis n Würfel.

Kirax Vorschlag habe ich ja selber schon probiert, kam aber irgendwie nicht weiter damit. Mal abgesehen davon, dass dann jedes mal, wenn ich eine Wahrscheinlichkeit haben möchte ich auch immer wieder alle Möglichkeiten dafür ausrechnen muss. Wenn ich nur immer nur einen Wurf berechnen würde würde ich das auch bevorzugen, da ich aber mehrere Würfe berechnen will halte ich es für sinnvoller nur einmal rechnen zu müssen und nachher nur nachschlagen zu müssen.

Firephoenix, meinst Du den Pseudocode von Ark oder von mir?


Grüße,

Andy

 

[XHelp]

Ich verstehe auch nicht so ganz warum du alle Möglichkeiten gespeichert halten willst. Du wirst ja wohl nicht im Sekundentakt die Wahrscheinlichkeit ausrechnen um mit 10000000000000 W99999999999 Würfel über 30 zu würfeln. Du brauchst ja nur die Anzahl der in Frage kommender Ereignisse und das kannst du rekursiv berechnen, wenn du magst.

 

[2XS]

Hi,

ich würde es auch rekursiv berechnen, bzw habe es schon mehrfach versucht. Aber wie bereits geschrieben bekomme ich davon nur Knoten im Hirn. Ich arbeite seit ca fünf Jahren als PL/SQL Programmierer und da hat man es nicht so mit Rekursionen. Und wenn man die ganzen SQL Statements gewöhnt ist wird man etwas träge

Theoretisch weiß ich zwar wie es geht, aber die praktische Umsetzung will nicht so recht klappen.


Grüße,

Andy

 

[kirax]

So in etwa hatte ich mir das vorgestellt.
Ist grad mal so runtergeschrieben, von daher keine Garantie auf Effizienz Lässt sich sicher noch an der ein oder anderen Stelle optimieren (siehe meine Kommentare von weiter oben).

public class Wuerfel {

    private int pos;
    private int size;
    private Wuerfel next;

    public Wuerfel(int size, Wuerfel next) {
        this.pos = 0;
        this.size = size;
        this.next = next;
    }

    public Wuerfel(Wuerfel wuerfel) {
        this.pos = wuerfel.pos;
        this.size = wuerfel.size;
        this.next = wuerfel.next;
    }

    public boolean hasNext() {
        return this.next != null;
    }

    public Wuerfel getNext() {
        return this.next;
    }

    public int getValue() {
        return this.pos + 1;
    }

    public boolean tick() {
        // rekursives Weiterdrehen der Würfel, wo die höchste Ziffer erreicht ist beginnt er von vorne
        // und erhöht den nächsten Würfel um 1. So werden alle Kombinationen durchgespielt. Gibt false
        // zurück, wenn keine neue Kombination mehr existiert, sonst true. 
        this.pos = (this.pos + 1) % this.size;
        if (this.pos == 0) {
            if (this.next != null) {
                return this.next.tick();
            }
            return false;
        }
        return true;
    }

    private static int chanceRec(Wuerfel wuerfel, int threshold) {
        // Basisfall, falls alle Würfel die höchste Ziffer haben, brich die Rekursion ab
        int checkCount = 0;
        int wuerfelCount = 1;
        Wuerfel thisWuerfel = new Wuerfel(wuerfel);
        while (thisWuerfel.hasNext()) {
            if (thisWuerfel.getValue() == thisWuerfel.size) {
                checkCount++;
            }
            wuerfelCount++;
            thisWuerfel = thisWuerfel.getNext();
        }
        if (wuerfelCount == checkCount) {
            return 0;
        }
        // zähle alle Würfelaugen zusammen
        thisWuerfel = new Wuerfel(wuerfel);
        int sum = thisWuerfel.getValue();
        while (thisWuerfel.hasNext()) {
            thisWuerfel = thisWuerfel.getNext();
            sum += thisWuerfel.getValue();
        }
        // wenn die Würfelaugen >= der gesetzten Schwelle sind, erhöhe den ersten Würfel um eins,
        // zähle 1 zu den bisher berechneten erfolgreichen Versuchen und beginne von vorn, höre auf,
        // wenn bereits alle Würfe durchgespielt wurden.
        if (sum >= threshold) {
            if (wuerfel.tick()) {
                return 1 + chanceRec(wuerfel, threshold);
            } else {
                return 1;
            }
        // Wenn die Summe der Würfelaugen kleiner der Schwelle ist, erhöhe den ersten Würfel um eins
        // und beginne von vorn, ohne einen erfolgreichen Versuch draufzurechnen. Rest wie oben.
        } else {
            if (wuerfel.tick()) {
                return chanceRec(wuerfel, threshold);
            } else {
                return 0;
            }
        }
    }
    
    public static double chance(int count, int size, int threshold) {
        // erstelle die Würfel
        Wuerfel[] wuerfel = new Wuerfel[count];
        // beginne mit letztem Würfel, weil dieser keine next-Referenz hat
        wuerfel[count - 1] = new Wuerfel(size, null);
        for (int i = count - 2; i >= 0; i--) {
            wuerfel[i] = new Wuerfel(size, wuerfel[i + 1]);
        }
        // berechne die Chance
        return chanceRec(wuerfel[0], threshold)/Math.pow(size, count);
    }
    

    public static void main(String[] args) {
        System.out.println(chance(2, 6, 7));
        System.out.println(chance(2, 4, 7));
    }
}

Ausgabe für die beiden Beispielfälle (2 W6, 2 W4, jeweils mind. 7 erreichen):

0.5833333333333334
0.1875

 

[2XS]

Vielen Dank Kirax,

jetzt muss ich nur noch dahinter steigen, was genau da passiert. Sah aber beim Überfliegen so aus als wäre es genau das was ich gesucht habe. Aber damit ich davon auch den gewünschten Lerneffekt habe muss ich selber mal etwas damit rumspielen.


Danke an alle!


Grüße,

Andy

 

[kirax]

Habe mal ein paar Comments reingepflanzt.

Aber ich merke gerade, dass es wohl doch eine recht ungeschickte Lösung ist, das rekursiv zu lösen. Mit 5 W6 kommt er glaube ich nicht mehr klar (über 7500 rekursive Aufrufe).

Schlauer wäre wohl eine iterative Lösung. Die Lösung lässt sich aber recht einfach in eine Schleife umwandeln. Und das läuft dann ökonomischer

 

[2XS]

Iterativ müsste ich aber doch vorher wissen wie viele Würfel berechnet werden sollen. Und für jeden Würfel dann eine Schleife haben. Das war ja mein erster Ansatz, als ich es nur für 2 W6 berechnen wollte. Sobald ich es dann dynamischer machen wollte kam ich nicht mehr weiter.


Grüße,

Andy


P.S.: Vielen Dank für die Kommentare! :toll:

 

[kirax]

Die rekursive Lösung oben weiß vorher auch, wie viele Würfel und wie groß die Würfel sind. Anders geht es ja auch gar nicht

public static int chanceIter(Wuerfel wuerfel, int threshold) {
  int chance = 0;
  do {  
    Wuerfel thisWuerfel = new Wuerfel(wuerfel);
    int sum = thisWuerfel.getValue();
    while (thisWuerfel.hasNext()) {
      thisWuerfel = thisWuerfel.getNext();
      sum += thisWuerfel.getValue();
    }
    if (sum >= threshold) {
      chance++;
    }
  } while (wuerfel.tick());
  return chance;
}

Ohne es getestet zu haben.

 

[2XS]

Klappt prima! Aber ich merke gerade wieder wie viel ich schon wieder über Java vergessen oder gar nicht gelernt habe.

Ich hatte die Iteration immer mit kaskadierenden Schleifen versucht. Und die Klasse Wuerfel als Datentyp zu verwenden hätte ich so schnell auch nicht probiert. ;(

Habe jetzt jedenfalls wieder eine Menge Anregungen bekommen. Hoffentlich kann ich das Ganze auch verinnerlichen.


Grüße und noch ein schönes Restwochenende,

Andy

 

[kirax]

Viele Wege führen nach Rom

Im Prinzip ist es eine verkettete Liste, die das weiterdrehen der Würfel mehr oder weniger sich selbst überlässt. Damit braucht man sich nur noch darum zu kümmern, die Augen zusammenzuzählen. Dadurch braucht man keine Schleifenkaskade.