public static long stirlingS2()

in commons-numbers-combinatorics/src/main/java/org/apache/commons/numbers/combinatorics/Stirling.java [183:232]

• 35 lines of code
• 10 McCabe index (conditional complexity)

    public static long stirlingS2(int n, int k) {
        checkArguments(n, k);

        if (n < StirlingS2Cache.MAX_N) {
            // The number is in the small cache
            return StirlingS2Cache.S2[n][k];
        }

        // Simple cases
        if (k == 0) {
            return 0;
        } else if (k == 1 || k == n) {
            return 1;
        } else if (k == 2) {
            checkN(n, k, 64, S2_ERROR_FORMAT);
            return (1L << (n - 1)) - 1L;
        } else if (k == n - 1) {
            return BinomialCoefficient.value(n, 2);
        } else if (k == n - 2) {
            checkN(n, k, S2_OVERFLOW_K_EQUALS_NM2, S2_ERROR_FORMAT);
            // (3n-5) * binom(n, 3) / 4
            return productOver4(3L * n - 5, BinomialCoefficient.value(n, 3));
        } else if (k == n - 3) {
            checkN(n, k, S2_OVERFLOW_K_EQUALS_NM3, S2_ERROR_FORMAT);
            return BinomialCoefficient.value(n - 2, 2) * BinomialCoefficient.value(n, 4);
        }

        // Compute using:
        // S(n, k) = k * S(n - 1, k) + S(n - 1, k - 1)

        // n >= 26 (MAX_N)
        // 3 <= k <= n-3

        // Start at the largest easily computed value: n < MAX_N or k < 3
        final int reduction = Math.min(n - StirlingS2Cache.MAX_N, k - 3) + 1;
        int n0 = n - reduction;
        int k0 = k - reduction;

        long sum = stirlingS2(n0, k0);
        while (n0 < n) {
            k0++;
            sum = Math.addExact(
                Math.multiplyExact(k0, stirlingS2(n0, k0)),
                sum
            );
            n0++;
        }

        return sum;
    }