package math.kombi;

import math.bigs.BigsUtil;
import math.utils.ArrayUtil;
import math.utils.MathUtil;

import java.math.BigDecimal;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.TreeSet;
import java.util.concurrent.ExecutionException;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.Future;

public class KombiUtil {
    private KombiUtil() {
    }

    /**
     * Oblicza (a+b)^n
     *
     * @param n
     * @param a
     * @param b
     * @return zwraca pełne rozwinięte równanie a^n + a^n-1y, etc.
     */
    @SuppressWarnings("JavaDoc")
    public static String binomial(int n, String a, String b) {
        StringBuilder sb = new StringBuilder();
        sb.append("(").append(a).append(" + ").append(b).append(")").append(n).append(" = ");
        BigInteger nn = new BigInteger(String.valueOf(n));
        ExecutorService es = Executors.newFixedThreadPool(n + 1);
        Future<BigInteger> f;
        if (n == 0) {
            sb.append("1");
            return sb.toString();
        }
        for (int i = 0; i < n + 1; i++) {
            f = es.submit(new Npok(nn, new BigInteger(String.valueOf(i))));
            try {
                BigInteger c = f.get();
                if (!c.equals(BigInteger.ONE)) {
                    sb.append(c.toString());
                }
            } catch (InterruptedException | ExecutionException e) {
                e.printStackTrace();
            }
            int xc = n - i;
            if (xc == n) {
                if (xc == 1) {
                    sb.append(a);
                } else {
                    sb.append(a).append(xc);
                }
            } else if (i == n) {
                if (i == 1) {
                    sb.append(b);
                } else {
                    sb.append(b).append(i);
                }
            } else {
                if ((xc == 1) && (i == 1)) {
                    sb.append(a).append(b);
                } else if (xc == 1) {
                    sb.append(a).append(b).append(i);
                } else if (i == 1) {
                    sb.append(a).append(xc).append(b);
                } else {
                    sb.append(a).append(xc).append(b).append(i);
                }
            }
            if (i < n) {
                sb.append(" + ");
            }
        }
        es.shutdown();
        return sb.toString();
    }

    /**
     * Oblicza (a+b)^n
     *
     * @param n - wykładnik dwumianu
     * @return - tablicę wszystkich liczb będących kolejnymi współczynnikami
     * rozwinięcia
     */
    public static BigInteger[] binomialCoeffs(int n) {
        BigInteger[] array = new BigInteger[n + 1];
        BigInteger nn = new BigInteger(String.valueOf(n));
        ExecutorService es;
        Future<BigInteger> f;
        int p;
        if (n % 2 == 0) {
            p = (n / 2) + 1;
            es = Executors.newFixedThreadPool(p);
        } else {
            p = ((n - 1) / 2) + 1;
            es = Executors.newFixedThreadPool(p);
        }
        for (int i = 0, r = n; i < p; i++, r--) {
            BigInteger k = new BigInteger(String.valueOf(i));
            f = es.submit(new Npok(nn, k));
            try {
                array[i] = f.get();
                array[r] = new BigInteger(array[i].toString());
            } catch (InterruptedException | ExecutionException e) {
                e.printStackTrace();
            }
        }
        es.shutdown();
        return array;
    }


    /**
     * Oblicza prawdopodobieństwo (n po k)p^kq^n-k
     *
     * @param n - liczba elementów
     * @param k - liczba stanów
     * @param p - prawdopodobieństwo zdarzenia sprzyjającego
     * @param q - prawdopodobieństwo zdarzenia przeciwnego
     * @return zwraca obliczone prawdopodobieństwo
     */
    public static BigDecimal bernoulli(int n, int k, BigDecimal p,
                                       BigDecimal q) {
        ExecutorService es = Executors.newFixedThreadPool(1);
        Future<BigInteger> f;
        f = es.submit(new Npok(new BigInteger(String.valueOf(n)),
                new BigInteger(String.valueOf(k))));
        BigDecimal pk = p.pow(k);
        BigDecimal qk = q.pow(n - k);
        BigInteger npok = null;
        try {
            npok = f.get();
        } catch (InterruptedException | ExecutionException e) {
            e.printStackTrace();
        }
        es.shutdown();
        return new BigDecimal(npok.toString()).multiply(pk).multiply(qk);
    }


    public static Fraction bernoulli(int n, int k, Fraction p, Fraction q) {
        ExecutorService es = Executors.newFixedThreadPool(1);
        Future<BigInteger> f;
        f = es.submit(new Npok(new BigInteger(String.valueOf(n)),
                new BigInteger(String.valueOf(k))));
        Fraction pk = p.pow(k);
        Fraction qk = q.pow(n - k);
        BigInteger npok = null;
        try {
            npok = f.get();
        } catch (InterruptedException | ExecutionException e) {
            e.printStackTrace();
        }
        Fraction result = Fraction.mult(Fraction.mult(pk, qk),
                new Fraction(npok, BigInteger.ONE));
        es.shutdown();
        return result;
    }


    //Oblicza liczbę kombinacji bez powtórzeń
    public static long kbp(int n, int k) {
        return Npok.npok(n, k);
    }

    public static BigInteger kbp(long n, long k) {
        return Npok.npok(n, k);
    }

    public static BigInteger kbp(BigInteger n, BigInteger k) {
        ExecutorService es = Executors.newFixedThreadPool(1);
        Future<BigInteger> f;
        f = es.submit(new Npok(new BigInteger(String.valueOf(n)),
                new BigInteger(String.valueOf(k))));
        BigInteger npok = null;
        try {
            npok = f.get();
        } catch (InterruptedException | ExecutionException e) {
            e.printStackTrace();
        }
        es.shutdown();
        return npok;
    }

    //Oblicza liczbe kombinacji z powtorzeniami
    public static long kzp(int n, int k) {
        return Npok.npok(n + k - 1, k);
    }

    public static BigInteger kzp(long n, long k) {
        return Npok.npok(n + k - 1, k);
    }

    public static BigInteger kzp(BigInteger n, BigInteger k) {
        ExecutorService es = Executors.newFixedThreadPool(1);
        BigInteger nn = n.add(k).subtract(BigInteger.ONE);
        Future<BigInteger> f;
        f = es.submit(new Npok(nn, k));
        BigInteger npok = null;
        try {
            npok = f.get();
        } catch (InterruptedException | ExecutionException e) {
            e.printStackTrace();
        }
        es.shutdown();
        return npok;
    }


    //oblicza liczbe wariacji bez powtorzen
    public static long wbp(int n, int k) {
        long b = Factorial.factorial(n);
        long c = Factorial.factorial(n - k);
        return b / c;
    }

    public static BigInteger wbp(long n, long k) {
        BigInteger b = Factorial.factorial(n);
        BigInteger c = Factorial.factorial(n - k);
        return b.divide(c);
    }

    public static BigInteger wbp(BigInteger n, BigInteger k) {
        BigInteger nk = kbp(n, k);
        return nk.multiply(new BigInteger(String.valueOf(2)));
    }

    //oblicza liczbe wariacji z powtorzeniami
    public static long wzp(int n, int k) {
        return (long) Math.pow(n, k);
    }

    public static BigInteger wzp(long n, int k) {
        BigInteger res = new BigInteger(String.valueOf(n));
        return res.pow(k);
    }

    public static BigInteger wzp(BigInteger n, int k) {
        return n.pow(k);
    }

    //oblicza liczbe permutacje bez powtorzen
    public static long pbp(int n) {
        return Factorial.factorial(n);
    }

    public static BigInteger pbp(long n) {
        return Factorial.factorial(n);
    }

    public static BigInteger pbp(BigInteger n) {
        ExecutorService es = Executors.newFixedThreadPool(1);
        Future<BigInteger> f;
        f = es.submit(new Factorial(n));
        BigInteger np = null;
        try {
            np = f.get();
        } catch (InterruptedException | ExecutionException e) {
            e.printStackTrace();
        }
        es.shutdown();
        return np;
    }


    //oblicza liczbe permutacji z powtorzeniami
    //w tablicy liczba powtórzeń każdego z elementów
    // {t,a,t,a} n=4, array={t,a}={2,2}
    //{m,a,t,a},n=4, array={m,a,t}={1,2,1}

    public static long pzp(int n, int[] array) {
        long ilo = 1;
        for (int i1 : array) {
            ilo = ilo * Factorial.factorial(i1);
        }
        return Factorial.factorial(n) / ilo;
    }

    public static BigInteger pzp(long n, long[] array) {
        BigInteger ilo = BigInteger.ONE;
        for (long l : array) {
            ilo = ilo.multiply(Factorial.factorial(l));
        }
        return Factorial.factorial(n).divide(ilo);
    }

    public static BigInteger pzp(BigInteger n, BigInteger[] array) {
        BigInteger ilo = BigInteger.ONE;
        ExecutorService es = Executors.newFixedThreadPool(array.length + 1);
        Future<BigInteger> f;
        f = es.submit(new Factorial(n));
        BigInteger res = null;
        try {
            res = f.get();
        } catch (InterruptedException | ExecutionException e1) {
            e1.printStackTrace();
        }
        for (BigInteger bigInteger : array) {
            f = es.submit(new Factorial(bigInteger));
            try {
                ilo = ilo.multiply(f.get());
            } catch (InterruptedException | ExecutionException e) {
                e.printStackTrace();
            }
        }
        es.shutdown();
        return res.divide(ilo);
    }

    /**
     * Oblicza liczby Eulera I rodzaju (rzędu)
     *
     * @param n
     * @param k
     * @return
     */
    public static long euler1(int n, int k) {
        if (n == 0) {
            return 1;
        }
        long sum = 0;
        for (int m = 0; m <= k + 1; m++) {
            sum += Npok.npok(n + 1, m) * (Math.pow(k - m + 1, n))
                    * Math.pow(-1, m);
        }
        return sum;
    }

    /**
     * Oblicza liczby Eulera 1 rodzaju (rzędu)
     *
     * @param n
     * @param k
     * @return
     */
    public static BigInteger euler1Big(int n, int k) {
        if (n == 0) {
            return BigInteger.ONE;
        }
        BigInteger sum = BigInteger.ZERO;
        for (int m = 0; m <= k + 1; m++) {
            sum = sum.add(Npok
                    .npok(new BigInteger(String.valueOf(n + 1)),
                            new BigInteger(String.valueOf(m)))
                    .multiply(
                            (new BigInteger(String.valueOf(k - m + 1)).pow(n)))
                    .multiply((new BigInteger(
                            "-1").pow(m))));
        }
        return sum;
    }

    /**
     * Oblicza liczby Eulera II rodzaju (rzędu)
     *
     * @param n
     * @param k
     * @return
     */
    public static long euler2recur(int n, int k) {
        if (k == 0) {
            return 1L;
        } else if (n == 0 && k == 0) {
            return 1L;
        } else if (n == k) {
            return 0;
        } else {
            return (k + 1) * euler2recur(n - 1, k)
                    + (2 * n - k - 1) * euler2recur(n - 1, k - 1);
        }
    }

    /**
     * Oblicza liczby Eulera II rodzaju (rzędu)
     *
     * @param n
     * @param k
     * @return
     */
    public static BigInteger euler2recur(long n, long k) {
        if (k == 0) {
            return BigInteger.ONE;
        } else if (n == 0 && k == 0) {
            return BigInteger.ONE;
        } else if (n == k) {
            return BigInteger.ZERO;
        } else {
            return new BigInteger(String.valueOf(k + 1))
                    .multiply(euler2recur(n - 1, k))
                    .add(new BigInteger(String.valueOf(2 * n - k - 1))
                            .multiply(euler2recur(n - 1, k - 1)));
        }
    }

    /**
     * Oblicza liczby Bernoulliego
     *
     * @param n
     * @return
     */
    public static Fraction bernoulli(int n) {
        if (n == 0) {
            return Fraction.ONE;
        }
        if (((n & 1) == 1) && n > 2) {
            return Fraction.ZERO;
        }
        Fraction bn = Fraction.ZERO;
        for (int k = 0; k <= n; k++) {
            BigInteger sum = BigInteger.ZERO;
            for (int r = 0; r <= k; r++) {
                if ((r & 1) == 1) {
                    sum = sum.add(((new BigInteger(String.valueOf(r))).pow(n))
                            .multiply(
                                    Npok.npok(new BigInteger(String.valueOf(k)),
                                            new BigInteger(String.valueOf(r))))
                            .negate());
                } else {
                    sum = sum.add(((new BigInteger(String.valueOf(r))).pow(n))
                            .multiply(Npok.npok(
                                    new BigInteger(String.valueOf(k)),
                                    new BigInteger(String.valueOf(r)))));
                }
            }
            bn = bn.add(
                    new Fraction(sum, new BigInteger(String.valueOf(k + 1))));
        }
        return bn;
    }

    //Oblicza liczbę partycji dla danej liczby
    public static int partycje(int n) {
        return RXXX.r001(n, n);
    }

    public static long partycje(long n) {
        return RXXX.r001(n, n);
    }

    public static BigInteger partycje(BigInteger n) {
        ExecutorService es = Executors.newFixedThreadPool(1);
        Future<BigInteger> f;
        f = es.submit(new RXXX(n, n, "000"));
        BigInteger np = null;
        try {
            np = f.get();
        } catch (InterruptedException | ExecutionException e) {
            e.printStackTrace();
        }
        es.shutdown();
        return np;
    }

    //Oblicza liczbę partycji dla n przedstawionego jako
    //suma k liczb naturalnych
    public static int partycje(int n, int k) {
        return RXXX.r000(k, n);
    }

    public static long partycje(long n, long k) {
        return RXXX.r000(k, n);
    }

    public static BigInteger partycje(BigInteger n, BigInteger k) {
        ExecutorService es = Executors.newFixedThreadPool(1);
        Future<BigInteger> f;
        f = es.submit(new RXXX(k, n, "001"));
        BigInteger np = null;
        try {
            np = f.get();
        } catch (InterruptedException | ExecutionException e) {
            e.printStackTrace();
        }
        es.shutdown();
        return np;
    }

    public static int inversion(int n) {
        long t1 = Factorial.factorial(n);
        double sum = 0;
        for (int i = 0; i < n + 1; i++) {
            sum += Math.pow(-1.0, i) * (1.0 / Factorial.factorial(i));
        }
        return (int) (sum * t1);
    }

    public static BigInteger inversion(BigInteger n) {
        BigInteger o = n.add(BigInteger.ONE);
        BigInteger dwa = new BigInteger("2");
        ExecutorService es = Executors.newCachedThreadPool();
        Future<BigInteger> f = es.submit(new Factorial(n));
        BigInteger t1 = null;
        try {
            t1 = f.get();
        } catch (InterruptedException | ExecutionException e) {
            e.printStackTrace();
        }
        Fraction sum = Fraction.ZERO;
        BigInteger i = BigInteger.ZERO;
        while (BigsUtil.mniejszy(i, o)) {
            f = es.submit(new Factorial(i));
            if (i.remainder(dwa).equals(BigInteger.ZERO)) {
                try {
                    sum = Fraction.add(sum,
                            new Fraction(BigInteger.ONE, f.get()));
                } catch (InterruptedException | ExecutionException e) {
                    e.printStackTrace();
                }
                i = i.add(BigInteger.ONE);
            } else {
                try {
                    sum = Fraction.add(sum,
                            new Fraction(BigInteger.ONE, f.get().negate()));
                } catch (InterruptedException | ExecutionException e) {
                    e.printStackTrace();
                }
                i = i.add(BigInteger.ONE);
            }
        }
        sum = Fraction.mult(sum, t1, BigInteger.ONE);
        BigInteger a = sum.getNumerator().divide(sum.getDenominator());
        es.shutdown();
        return a;
    }

    public static long catalan(int n) {
        return Npok.npok(2 * n, n) / (n + 1);
    }

    public static BigInteger catalan(long n) {
        return Npok.npok(2 * n, n)
                .divide(new BigInteger(String.valueOf(n + 1)));
    }

    public static BigInteger catalan(BigInteger n) {
        ExecutorService es = Executors.newFixedThreadPool(1);
        Future<BigInteger> f;
        f = es.submit(new Npok(n.multiply(new BigInteger("2")), n));
        BigInteger npok = null;
        try {
            npok = f.get();
        } catch (InterruptedException | ExecutionException e) {
            e.printStackTrace();
        }
        es.shutdown();
        return npok.divide(n.add(BigInteger.ONE));
    }

    public static long bell(int n) {
        long[] tabl = new long[n + 1];
        tabl[0] = 1;
        for (int i = 1; i < n + 1; i++) {
            long sum = 0;
            for (int k = 0; k < i; k++) {
                sum += Npok.npok(i - 1, k) * tabl[k];
            }
            tabl[i] = sum;
            sum = 0;
        }
        return tabl[n];
    }

    public static int bell2(int n) {
        int sum = 0;
        for (int i = 0; i < n + 1; i++) {
            sum += Stir2.stir2(i, n);
        }
        return sum;
    }

    //zwraca ostatnią liczbę w tablicy, która zawiera wszystkie poprzednie liczby.
    //Można zwrócić tablicę i odczytać wszystkie lub tylko ostatnią liczbę
    public static BigInteger bell1(int n) {
        ExecutorService es = Executors.newFixedThreadPool(n);
        Future<BigInteger> f;
        BigInteger[] tabl = new BigInteger[n + 1];
        tabl[0] = BigInteger.ONE;
        for (int i = 1; i < n + 1; i++) {
            BigInteger sum = BigInteger.ZERO;
            for (int k = 0; k < i; k++) {
                f = es.submit(new Npok(new BigInteger(String.valueOf(i - 1)),
                        new BigInteger(String.valueOf(k))));
                BigInteger ff = null;
                try {
                    ff = f.get();
                } catch (InterruptedException | ExecutionException e) {
                    e.printStackTrace();
                }
                sum = sum.add(ff.multiply(tabl[k]));
            }
            tabl[i] = sum;
            sum = BigInteger.ZERO;
        }
        es.shutdown();
        return tabl[n];
    }

    /**
     * Funkcja tocjent Eulera = liczba liczb względnie pierwszych z podaną
     * liczbą
     *
     * @param n - liczba
     * @return liczba liczb względnie pierwszych z n
     */
    public static int totient(int n) {
        int sum = 0;
        for (int i = 0; i < n; i++) {
            if (MathUtil.nwd2(n, i) == 1) {
                sum++;
            }
        }
        return sum;
    }

    public static BigInteger totient(BigInteger n) {
        BigInteger sum = BigInteger.ZERO;
        BigInteger i = BigInteger.ZERO;
        while (BigsUtil.mniejszy(i, n)) {
            if ((n.gcd(i)).equals(BigInteger.ONE)) {
                sum = sum.add(BigInteger.ONE);
            }
            i = i.add(BigInteger.ONE);
        }
        return sum;
    }

    public static long totient(long n) {
        long sum = 0;
        for (long i = 0; i < n; i++) {
            if (MathUtil.nwd2(n, i) == 1) {
                sum++;
            }
        }
        return sum;
    }

    /**
     * Funkcja tocjent Eulera = liczba liczb względnie pierwszych z podaną
     * liczbą
     *
     * @param n - liczba
     * @return liczba liczb względnie pierwszych z n
     */
    public static int totient2(int n) {
        return relativePrimes(n).length;
    }

    public static long totient2(long n) {
        return relativePrimes(n).length;
    }

    public static int totient2(BigInteger n) {
        return relativePrimes(n).size();
    }

    public static long[] relativePrimes(long n) {
        long[] tabl = new long[0];
        for (long i = 0; i < n; i++) {
            if (MathUtil.nwd2(n, i) == 1) {
                tabl = ArrayUtil.extendArray(tabl, tabl.length, i);
            }
        }
        return tabl;
    }

    public static ArrayList<BigInteger> relativePrimes(BigInteger n) {
        ArrayList<BigInteger> al = new ArrayList<>();
        for (BigInteger a : al) {
            if (n.gcd(a).equals(BigInteger.ONE)) {
                al.add(a);
            }
        }
        return al;
    }

    public static int naszyjniki(int n, int k) {
        int[] tabl = KombiUtil.divisors(n);
        int sum = 0;
        for (int i1 : tabl) {
            sum += KombiUtil.totient(i1) * Math.pow(k, n / i1);
        }
        return sum / n;
    }

    public static long naszyjniki(long n, long k) {
        long[] tabl = KombiUtil.divisors(n);
        long sum = 0;
        for (long l : tabl) {
            sum += KombiUtil.totient(l) * Math.pow(k, n / l);
        }
        return sum / n;
    }

    public static BigInteger naszyjniki2(long n, long k) {
        long[] tabl = KombiUtil.divisors(n);
        BigInteger sum = BigInteger.ZERO;
        for (long l : tabl) {
            sum = sum.add(
                    new BigInteger(String.valueOf(KombiUtil.totient(l)))
                            .multiply(new BigInteger(String
                                    .valueOf((long) Math.pow(k, n / l)))));
        }
        return sum.divide(new BigInteger(String.valueOf(n)));
    }

    public static int bransoletki(int n, int k) {
        int[] tabl = KombiUtil.divisors(n);
        int sum = 0;
        for (int i1 : tabl) {
            sum += KombiUtil.totient(i1) * Math.pow(k, n / i1);
        }
        if ((n & 1) == 1) {
            sum += n * Math.pow(k, (n + 1) / 2);
        } else {
            sum += (n * (k + 1) * Math.pow(k, n / 2)) / 2;
        }
        return sum / (2 * n);
    }

    public static long bransoletki(long n, long k) {
        long[] tabl = KombiUtil.divisors(n);
        long sum = 0;
        for (long l : tabl) {
            sum += KombiUtil.totient(l) * Math.pow(k, n / l);
        }
        if ((n & 1) == 1) {
            sum += n * Math.pow(k, (n + 1) / 2);
        } else {
            sum += (n * (k + 1) * Math.pow(k, n / 2)) / 2;
        }
        return sum / (2 * n);
    }

    public static BigInteger bransoletki2(long n, long k) {
        long[] tabl = KombiUtil.divisors(n);
        BigInteger sum = BigInteger.ZERO;
        for (long l : tabl) {
            sum = sum.add(
                    new BigInteger(String.valueOf(KombiUtil.totient(l)))
                            .multiply(new BigInteger(String
                                    .valueOf((long) Math.pow(k, n / l)))));
        }
        if ((n & 1) == 1) {
            sum = sum.add(
                    (new BigInteger(String.valueOf(n)).multiply(new BigInteger(
                            String.valueOf((long) Math.pow(k, (n + 1) / 2))))));
        } else {
            //sum += (n * (k + 1) * Math.pow(k, n / 2)) / 2;
            sum = sum.add((new BigInteger(String.valueOf(n * (k + 1)))
                    .multiply(new BigInteger(
                            String.valueOf((long) Math.pow(k, n / 2))))
                    .divide(new BigInteger("2"))));
        }
        sum = sum.divide(new BigInteger(String.valueOf(2 * n)));
        return sum;
    }

    public static int[] divisors(int n) {
        int[] tabl = new int[0];
        for (int i = 1; i < n + 1; i++) {
            if (n % i == 0) {
                tabl = ArrayUtil.extendArray(tabl, tabl.length, i);
            }
        }
        return tabl;
    }

    public static long[] divisors(long n) {
        long[] tabl = new long[0];
        for (long i = 1; i < n + 1; i++) {
            if (n % i == 0) {
                tabl = ArrayUtil.extendArray(tabl, tabl.length, i);
            }
        }
        return tabl;
    }

    public static ArrayList<BigInteger> divisors(BigInteger n) {
        ArrayList<BigInteger> al = new ArrayList<>();
        BigInteger i = BigInteger.ONE;
        BigInteger nn = n.add(BigInteger.ONE);
        while (BigsUtil.mniejszy(i, nn)) {
            if (n.mod(i).equals(BigInteger.ZERO)) {
                al.add(i);
            }
            i = i.add(BigInteger.ONE);
        }
        return al;
    }

    /**
     * Wypełnia TreeSet listą permutacji. W secie są tylko
     * nie powtarzające się permutacje
     *
     * @param set   - tablica permutowanych elementów
     * @param str   - wstawić "" - potrzebne tylko wewnętrznie
     * @param perms - podstawiony pusty Treeset na wyniki
     */
    public static void selPermutList(String[] set, String str,
                                     TreeSet<String> perms) {
        for (int a = 0; a < set.length; a++) {
            String p1 = str;
            String[] set1 = new String[set.length - 1];
            int b = 0;
            for (int c = 0; c < set.length; c++) {
                if (c != a)
                    set1[b++] = set[c];
            }
            p1 = p1.concat(set[a].concat(","));
            if (set1.length == 0) {
                perms.add(p1.substring(0, p1.length() - 1));
            } else {
                selPermutList(set1, p1, perms);
            }
        }
    }

    /**
     * Wypełnia ArrayListę listą permutacji. W liście są
     * wszystkie permutacje
     *
     * @param set   - tablica permutowanych elementów
     * @param str   - wstawić "" - potrzebne tylko wewnętrznie
     * @param perms - podstawiony pusta ArrayLista na wyniki
     */
    public static void allPermutList(String[] set, String str,
                                     ArrayList<String> perms) {
        for (int a = 0; a < set.length; a++) {
            String p1 = str;
            String[] set1 = new String[set.length - 1];
            int b = 0;
            for (int c = 0; c < set.length; c++) {
                if (c != a)
                    set1[b++] = set[c];
            }
            p1 = p1.concat(set[a].concat(","));
            if (set1.length == 0) {
                perms.add(p1.substring(0, p1.length() - 1));
            } else {
                allPermutList(set1, p1, perms);
            }
        }
    }

    public static int npok2(int n, int k) {
        if (k > n) {
            return 0;
        } else if (k == 0 || k == n) {
            return 1;
        } else if (k == 1 || k == (n - 1)) {
            return n;
        } else {
            int b = factorial2(k);
            int c = factorial2(n - k);
            int a = b;
            for (int i = k + 1; i < n + 1; i++) {
                a *= i;
            }
            return a / (b * c);
        }
    }

    public static int factorial2(int n) {
        if (n > 20) {
            throw new Error("zbyt duża liczba");
        }
        if (n == 0) {
            return 1;
        }
        int sum = 1;
        for (int i = 1; i < n + 1; i++) {
            sum *= i;
        }
        return sum;
    }
}
