/******************************************************************************
 ** $Id: Kombinatorik.java 1017 2016-05-28 20:35:09Z wmh $
 ** Diese Datei ist Bestandteil der Java-Quelltexte des Würfelspiels JaFuffy.
 ** Lauffähig ab Java 7.
 ******************************************************************************
 ** Copyright (C) Wolfgang Hauck <wolfgang.hauck@3kelvin.de>
 ******************************************************************************
 ** This program is free software: you can redistribute it and/or modify
 ** it under the terms of the GNU General Public License as published by
 ** the Free Software Foundation, either version 3 of the License, or
 ** (at your option) any later version.
 **
 ** This program is distributed in the hope that it will be useful,
 ** but WITHOUT ANY WARRANTY; without even the implied warranty of
 ** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 ** GNU General Public License for more details.
 **
 ** You should have received a copy of the GNU General Public License
 ** along with this program.  If not, see <http://www.gnu.org/licenses/>.
 ******************************************************************************
 ** Die aktuellste Version von JaFuffy findet sich im Internet unter
 ** <http://jafuffy.3kelvin.de>.
 **
 ** Kommentare, Fehler oder Erweiterungswünsche bitte per E-Mail senden an
 ** <jafuffy@3kelvin.de>.
 ******************************************************************************/
package jafuffy.logik;

/** Sammlung von allgemeinen Formeln zum Thema Kombinatorik. */
public final class Kombinatorik {

    /** Anzahl Möglichkeiten, wenn alle Würfel geworfen werden. */
    public static final int VARIATIONEN = 7776;
    /** Wahrscheinlichkeit bei einem Würfel bei einem Wurf eine bestimmte Augenzahl auszulassen. */
    public static final double AUSLASSUNGSWAHRSCHEINLICHKEIT = 5. / 6.;

    /** Mittlere Augenzahl bei 0, 1, 2 oder 3 Restwürfen. */
    private static final double[] AUGENZAHLEN = { 0, 3.5, 4.25, 14. / 3. };
    /** Wahrscheinlichkeit für 1, ..., 5 gleiche Augen in einem Wurf mit allen Würfeln. */
    private static final double[] GLEICHENWAHRSCHEINLICHKEIT =
            { 5. / 54., 25. / 36., 125. / 648., 25. / 1296., 1 / 1296. };
    /** Stirling-Zahlen der zweiten Art. S(n,k) = k * S(n-1,k) + S(n-1,k-1); S(n,0) = 0, S(n,1) = 1 */
    private static final int[][] STIRLING2;

    static {
        STIRLING2 = new int[Turnier.WUERFEL + 1][];
        STIRLING2[0] = new int[1];
        STIRLING2[0][0] = 1;
        for (int n = 1; n <= Turnier.WUERFEL; n++) {
            STIRLING2[n] = new int[n + 1];
            STIRLING2[n][0] = 0;
            for (int k = 1; k < n; k++) {
                STIRLING2[n][k] = k * STIRLING2[n - 1][k] + STIRLING2[n - 1][k - 1];
            }
            STIRLING2[n][n] = 1;
        }
    }

    /**
     * @param r
     *            Restliche Anzahl der freien Würfe.
     * @return Mittlere erzielbare Augenzahl des Würfels.
     */
    public static double augenzahl(int r) {
        return AUGENZAHLEN[r];
    }

    /**
     * @param a
     *            Vorliegende Augenzahl des Würfels.
     * @param r
     *            Restliche Anzahl der freien Würfe für den Würfel.
     * @return Mittlere erzielbare Augenzahl des Würfels unter Berücksichtigung der vorliegenden Augenzahl.
     */
    public static double augenzahl(int a, int r) {
        return Double.max(a, augenzahl(r));
    }

    /**
     * @param n
     *            Nichtnegative Zahl.
     * @param k
     *            Ganze Zahl.
     * @return Binomialkoeffizient n über k.
     */
    public static int binom(int n, int k) {
        if (k < 0 || k > n) {
            return 0;
        }
        if (2 * k > n) {
            return binom(n, n - k);
        }
        int koeffizient = 1;
        n -= k;
        for (int i = 1; i <= k; i++) {
            n++;
            koeffizient *= n;
            koeffizient /= i;
        }
        return koeffizient;
    }

    /**
     * @param n
     *            Nichtnegative Zahl
     * @return Fakultät
     */
    public static int fakultaet(int n) {
        int p = 1;
        while (n > 0) {
            p *= n;
            n--;
        }
        return p;
    }

    /**
     * @param n
     *            Startfaktor.
     * @param k
     *            Anzahl der Faktoren.
     * @return Fallende Fakultät.
     */
    public static int fallend(int n, int k) {
        int p;
        if (k < 0) {
            p = 0;
        } else {
            p = 1;
            for (int i = 0; i < k; i++, n--) {
                p *= n;
            }
        }
        return p;
    }

    /**
     * @param n
     *            Anzahl der Würfel.
     * @param r
     *            Anzahl der Restwürfe.
     * @return Mittlere Anzahl von Würfeln mit gleicher Augenzahl mit einer fest vorgegebenen Augenzahl.
     */
    public static double fixgleichenmittel(int n, int r) {
        double p = 1 - Math.pow(AUSLASSUNGSWAHRSCHEINLICHKEIT, r);
        return n * p;
    }

    /**
     * @param n
     *            Anzahl der Würfel.
     * @param r
     *            Anzahl der Restwürfe (0 ist erlaubt).
     *
     * @return Wahrscheinlichkeit für genau n gleiche Würfel bei festgelegter Augenzahl.
     */
    public static double fixgleichenwahrscheinlichkeit(int n, int r) {
        double p = 1 - Math.pow(AUSLASSUNGSWAHRSCHEINLICHKEIT, r);
        return Math.pow(p, n);
    }

    /**
     * @param n
     *            Anzahl der Würfel.
     * @param k
     *            Anzahl der gleichen Würfel bei festgelegter Augenzahl.
     * @param r
     *            Anzahl der Restwürfe.
     *
     * @return Wahrscheinlichkeit für genau k gleiche Würfel bei festgelegter Augenzahl.
     */
    public static double fixgleichenwahrscheinlichkeit(int n, int k, int r) {
        double p = 1 - Math.pow(AUSLASSUNGSWAHRSCHEINLICHKEIT, r);
        return binom(n, k) * Math.pow(p, k) * Math.pow(1 - p, n - k);
    }

    /**
     * @param m
     *            Genaue Anzahl der Würfel mit gleicher Augenzahl (1, 2, 3, 4, 5). Im selben Wurf treten nicht mehr
     *            gleiche Würfel auf als diese Anzahl.
     * @return Wahrscheinlichkeit für genau m Würfel mit gleicher Augenzahl, wobei die Augenzahl beliebig, m aber
     *         maximal ist.
     */
    public static double gleichenwahrscheinlichkeit(int m) {
        return GLEICHENWAHRSCHEINLICHKEIT[m - 1];
    }

    /**
     * @param a
     *            Vorgegebene maximale Augenzahl, mit der ein k-Mehrling auftauchen soll.
     * @param k
     *            Genaue Länge des Mehrlings mit der angegebenen Augenzahl. Im Wurf tritt kein längerer Mehrling auf.
     * @return Wahrscheinlichkeit, den k-Mehrling (Einling, Zwilling, Drilling, Vierling, Fünfling) mit der Augenzahl a
     *         bei fünf Würfeln in einem Wurf zur erzielen, wobei im Wurf kein gleich langer Mehrling zu einer größeren
     *         Augenzahl auftritt.
     */
    public static double mehrlingswahrscheinlichkeit(int a, int k) {
        if (k == 2) {
            return (25. + 5 * (a - 1)) / 324.;
        } else {
            return gleichenwahrscheinlichkeit(k) / 6;
        }
    }

    /**
     * @param min
     *            Mindestanzahl der Würfel, welche eine bestimmte Augenzahl zeigen sollen.
     * @return Wahrscheinlichkeit für die Mindestanzahl.
     */
    public static double mindestfixgleichenwahrscheinlichkeit(int min) {
        return mindestfixgleichenwahrscheinlichkeit(Turnier.WUERFEL, min, Turnier.RUNDEN);
    }

    /**
     * @param n
     *            Anzahl der Würfel, die zur Verfügung stehen.
     * @param min
     *            Mindestanzahl der Würfel, welche eine bestimmte Augenzahl zeigen sollen.
     * @param r
     *            Anzahl der verbleibenden Restwürfe.
     * @return Wahrscheinlichkeit für die Mindestanzahl.
     */
    public static double mindestfixgleichenwahrscheinlichkeit(int n, int min, int r) {
        double p = 0;
        for (int k = min; k <= Turnier.WUERFEL; k++) {
            p += fixgleichenwahrscheinlichkeit(n, k, r);
        }
        return p;
    }

    /**
     * @param min
     *            Mindestanzahl der Würfel mit gleicher Augenzahl (1, 2, 3, 4, 5).
     * @return Wahrscheinlichkeit für mindestens m Würfel mit gleicher Augenzahl, wobei die Augenzahl beliebig ist. Im
     *         Wurf werden die Würfel mit gleicher Augenzahl gezählt; es gilt die längste Sequenz, wobei bei gleich
     *         langen Sequenzen diejenige zu der höheren Augenzahl gewählt wird.
     */
    public static double mindestgleichenwahrscheinlichkeit(int min) {
        double p = 0;
        for (int k = min; k <= Turnier.WUERFEL; k++) {
            p += gleichenwahrscheinlichkeit(k);
        }
        return p;
    }

    /**
     * @param a
     *            Vorgegebene maximale Augenzahl, mit der mindestens ein k-Mehrling auftauchen soll.
     * @param k
     *            Minimale Länge eines Mehrlings mit der angegebenen Augenzahl.
     * @return Wahrscheinlichkeit, mindestens einen k-Mehrling (Einling, Zwilling, Drilling, Vierling, Fünfling) mit der
     *         gegebenen Augenzahl bei fünf Würfeln in einem Wurf zur erzielen, wobei kein gleich langer Mehrling mit
     *         einer größeren Augenzahl auftritt.
     */
    public static double mindestmehrlingswahrscheinlichkeit(int a, int k) {
        double p = 0;
        for (int l = k; l <= Turnier.WUERFEL; l++) {
            p += mehrlingswahrscheinlichkeit(a, l);
        }
        return p;
    }

    /**
     * Berechnet Stirlingzahl der zweiten Art (Anzahl der Partitionen der Menge der Kardinalität n in k nicht-leere
     * Mengen).
     *
     * @param n
     *            Kardinalität der Menge.
     * @param k
     *            Anzahl der nicht-leeren Mengen.
     * @return Stirlingzahl der zweiten Art.
     */
    public static int stirling2(int n, int k) {
        if (k <= n) {
            return STIRLING2[n][k];
        } else {
            return 0;
        }
    }

    /**
     * @param n
     * @param d
     * @param k
     * @return
     */
    public static int strassenteilschablone(int n, int d, int k) {
        int summe = 0;
        for (int i = k; i <= n; i++) {
            summe += stirling2(i, k) * binom(n, i) * Math.pow(d, n - i);
        }
        return summe;
    }

    /**
     * @param n
     * @param d
     * @param k
     * @param m
     * @return
     */
    public static double strassenteilsequenz(int n, int d, int k, int m) {
        return fallend(m, k) * strassenteilschablone(n, d, k);
    }

    /** Diese Klasse liefert nur statische Methode, daher wird eine Instanziierung verboten. */
    private Kombinatorik() {
    }

}
