/******************************************************************************
 ** $Id: Kombinatorik.java 625 2014-12-29 16:45:34Z wmh $
 ** Diese Datei ist Bestandteil der Java-Quelltexte des Würfelspiels JaFuffy.
 ** Lauffähig ab Java 6.
 ******************************************************************************
 ** 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;

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

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

    /**
     * @param n
     *            Nichtnegative Zahl.
     * @param k
     *            Ganze Zahl.
     * @return Binomialkoeffizient n über k.
     */
    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
     */
    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.
     */
    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 gleicher Augenzahlen wie eine fest vorgegebene Augenzahl.
     */
    static float gleichenmittel(int n, int r) {
        float p = 1F - (float) Math.pow(5F / 6F, r);
        return n * p;
    }

    /**
     * @param m
     *            Anzahl der Würfel mit gleicher Augenzahl (1, 2, 3, 4, 5).
     * @return Wahrscheinlichkeit für genau m Würfel mit gleicher Augenzahl.
     */
    static float gleichenwahrscheinlichkeit(int m) {
        return GLEICHENWAHRSCHEINLICHKEIT[m - 1];
    }

    /**
     * @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.
     */
    static float gleichenwahrscheinlichkeit(int n, int r) {
        float p = 1F - (float) Math.pow(5F / 6F, r);
        return (float) 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.
     */
    static float gleichenwahrscheinlichkeit(int n, int k, int r) {
        float p = 1F - (float) Math.pow(5F / 6F, r);
        return binom(n, k) * (float) Math.pow(p, k) * (float) Math.pow(1 - p, n - k);
    }

    /**
     * @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.
     */
    static float mindestgleichenwahrscheinlichkeit(int n, int min, int r) {
        float p = 0;
        for (int k = min; k <= Turnier.WUERFEL; k++) {
            p += gleichenwahrscheinlichkeit(n, k, r);
        }
        return p;
    }

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

    /**
     * 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.
     */
    static int stirling2(int n, int k) {
        if (k <= n) {
            return STIRLING2[n][k];
        } else {
            return 0;
        }
    }

    /**
     * @param n
     * @param d
     * @param k
     * @return
     */
    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
     */
    static float strassenteilsequenz(int n, int d, int k, int m) {
        return fallend(m, k) * strassenteilschablone(n, d, k);
    }

    /** Mittlere Augenzahl bei 0, 1, 2 oder 3 Restwürfen. */
    private static final float[] AUGENZAHLEN = { 0F, 3.5F, 4.25F, 14F / 3F };
    /**
     * Wahrscheinlichkeit für 1, ..., 5 gleiche Augen in einem Wurf mit allen Würfeln.
     */
    private static final float[] GLEICHENWAHRSCHEINLICHKEIT = { 5F / 54F, 25F / 36F,
            125F / 648F, 25F / 1296F, 1F / 1296F };
    /**
     * 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;
        }
    }

    /** Als Hilfsklasse nicht instanzierbar. */
    private Kombinatorik() {
    }

}
