package ggw;

import java.math.BigInteger;
import java.util.ArrayList;
import java.util.List;
import java.util.stream.IntStream;

public final class NormalizedGirardWaring {
    public static void main(String... args) {
        for (int I = 1; I <= 10; I++) {
            for (int J = 1; J <= 20; J++) {
                System.out.println("I = " + I + ", J = " + J);

                for (int[] K : computePartitions(J)) {
                    BigInteger c = c(I, J, K);
                    if (c.equals(BigInteger.ZERO)) continue;


                    System.out.print("[");

                    for (int i = 0; i < I; i++) {
                        if (i != 0) System.out.print(" ");
                        int val = 0;
                        if (i < K.length) val = K[i];
                        System.out.print(val);
                    }
                    System.out.println("] " + c);
                }

                System.out.println();
            }
        }
    }

    private static List<int[]> computePartitions(int J) {
        List<int[]> Ks = new ArrayList<>();
        part(J, new int[J], 0, Ks, J);
        return Ks;
    }

    private static void part(int n, int[] v, int level, List<int[]> Ks, int J) {
        if (n < 1) return;
        v[level] = n;

        int[] K = new int[J];
        for (int i = 0; i <= level; i++) {
            K[v[i] - 1]++;
        }
        Ks.add(K);

        int first = level == 0 ? 1 : v[level - 1];
        for (int i = first; i <= n / 2; i++) {
            v[level] = i;
            part(n - i, v, level + 1, Ks, J);
        }
    }

    private static BigInteger c(int I, int J, int[] K) {
        if (IntStream.of(K).sum() == 0) return BigInteger.ONE;
        int sum = 0;
        for (int i = I; i < K.length; i++) {
            sum += K[i];
        }
        if (sum != 0) return BigInteger.ZERO;
        int sumK = IntStream.of(K).sum();
        BigInteger num = BigInteger.valueOf(J);
        BigInteger den = BigInteger.valueOf(I * sumK);
        for (int i = 0; i < J + sumK; i++) num = num.multiply(BigInteger.valueOf(-1L));
        num = num.multiply(factorial(sumK));
        for (int i : K) {
            den = den.multiply(factorial(i));
        }
        for (int i = 0; i < I; i++) {
            for (int jj = 0; jj < (i >= K.length ? 0 : K[i]); jj++) {
                num = num.multiply(choose(I, i + 1));
            }
        }
        return num.divide(den);
    }

    private static BigInteger choose(int n, int k) {
        if (k > n) return BigInteger.ZERO;
        return factorial(n).divide(factorial(k)).divide(factorial(n - k));
    }

    private static final BigInteger[] factorials = new BigInteger[1000];

    static {
        for (int i = 0; i < 1000; i++) {
            BigInteger ret = BigInteger.ONE;
            for (int i1 = 0; i1 < i; i1++) {
                ret = ret.multiply(BigInteger.valueOf(i1 + 1));
            }
            factorials[i] = ret;
        }
    }

    private static BigInteger factorial(int n) {
        if (n < factorials.length) return factorials[n];
        BigInteger ret = BigInteger.ONE;
        for (int i = 0; i < n; i++) {
            ret = ret.multiply(BigInteger.valueOf(i + 1));
        }
        return ret;
    }
}