package math.kombi;

import java.math.BigInteger;
import java.util.concurrent.Callable;

/**
 * Nierekurencyjna - setki razy szybsza niz rekurencyjna
 *
 * @author Jacek
 */
public class Stir2 implements Callable<BigInteger> {
    private final long k;
    private final long n;

    public Stir2(long k, long n) {
        this.k = k;
        this.n = n;
    }

    @Override
    public BigInteger call() {
        return stir2(this.k, this.n);
    }

    //oblicza liczbe Stirlinga II rodzaju (dla podzbiorow)
    //czyli k podzbiorow n
    public static long stir2(int k, int n) {
        if (n == 0 && k == 0) {
            return 1L;
        } else if (n == 0 && k == 1) {
            return 0L;
        } else if (n > 0) {
            if (k == 0) {
                return 0;
            } else if (k == 1) {
                return 1;
            } else if (n < k) {
                return 0;
            } else if (n == k) {
                return 1;
            } else {
                //return stir2(k - 1, n - 1) + k * stir2(k, n - 1);
                long kk = (int) Factorial.factorial(k);
                long sum = 0;
                for (int m = 0; m <= k; m++) {
                    sum += ((int) Math.pow(-1, k - m)) * Npok.npok(k, m)
                            * ((int) Math.pow(m, n));
                }
                return sum / kk;
            }
        }
        return 0;
    }

    public static BigInteger stir2(long k, long n) {
        if (n == 0 && k == 0) {
            return BigInteger.ONE;
        } else if (n == 0 && k == 1) {
            return BigInteger.ZERO;
        } else if (n > 0) {
            if (k == 0) {
                return BigInteger.ZERO;
            } else if (k == 1) {
                return BigInteger.ONE;
            } else if (n < k) {
                return BigInteger.ZERO;
            } else if (n == k) {
                return BigInteger.ONE;
            } else {
                BigInteger kk = Factorial.factorial(k);
                BigInteger sum = BigInteger.ZERO;
                for (long m = 0; m <= k; m++) {
                    if (((k - m) & 1) == 1) {
                        sum = sum
                                .subtract(Npok.npok(k, m)
                                        .multiply((new BigInteger(
                                                String.valueOf(m)))
                                                .pow((int) n)));
                    } else {
                        sum = sum
                                .add(Npok.npok(k, m)
                                        .multiply((new BigInteger(
                                                String.valueOf(m)))
                                                .pow((int) n)));
                    }
                }
                return sum.divide(kk);
            }
        }
        return null;
    }

}
