How to resolve the algorithm Stirling numbers of the first kind step by step in the Java programming language

Published on 12 May 2024 09:40 PM
#Java

How to resolve the algorithm Stirling numbers of the first kind step by step in the Java programming language

Table of Contents

Problem Statement

Stirling numbers of the first kind, or Stirling cycle numbers, count permutations according to their number of cycles (counting fixed points as cycles of length one). They may be defined directly to be the number of permutations of n elements with k disjoint cycles. Stirling numbers of the first kind express coefficients of polynomial expansions of falling or rising factorials. Depending on the application, Stirling numbers of the first kind may be "signed" or "unsigned". Signed Stirling numbers of the first kind arise when the polynomial expansion is expressed in terms of falling factorials; unsigned when expressed in terms of rising factorials. The only substantial difference is that, for signed Stirling numbers of the first kind, values of S1(n, k) are negative when n + k is odd. Stirling numbers of the first kind follow the simple identities:

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Stirling numbers of the first kind step by step in the Java programming language

The provided SterlingNumbersFirstKind Java program calculates and prints the unsigned Stirling numbers of the first kind (S1(n,k)) for integers n and k within a specified range. Additionally, it finds the maximum value of S1(100, k) and the corresponding value of k.

Understanding the Code:

1. Main Method:

  • public static void main(String[] args) is the entry point of the program.

2. Variables and Constants:

  • max: Maximum value for n and k, set to 12 for the initial demonstration.
  • COMPUTED: HashMap used to store precomputed values to avoid redundant calculations.

3. Sterling Number Calculation:

  • private static final BigInteger sterling1(int n, int k): This recursive function computes the unsigned Stirling number of the first kind, S1(n,k), based on the following rules:
    • If n == 0 && k == 0, return 1 (base case for permutations).
    • If n > 0 && k == 0, return 0 (S1(n,0) = 0).
    • If k > n, return 0 (not a valid combination).
    • Otherwise, calculate S1(n,k) using the recurrence relation: S1(n,k) = S1(n-1, k-1) + (n-1) * S1(n-1, k).

4. Printing Output:

  • The program prints the computed values of S1(n,k) in a tabular format, with rows representing n and columns representing k.
  • The printf method is used for formatted printing.

5. Maximum Value of S1(100, k):

  • The program also calculates the maximum value of S1(100, k) by iterating through values of k from 1 to 100.
  • It keeps track of the maximum value and prints the maximum along with the corresponding k.

Source code in the java programming language

import java.math.BigInteger;
import java.util.HashMap;
import java.util.Map;

public class SterlingNumbersFirstKind {

    public static void main(String[] args) {
        System.out.println("Unsigned Stirling numbers of the first kind:");
        int max = 12;
        System.out.printf("n/k");
        for ( int n = 0 ; n <= max ; n++ ) {
            System.out.printf("%10d", n);
        }
        System.out.printf("%n");
        for ( int n = 0 ; n <= max ; n++ ) {
            System.out.printf("%-3d", n);
            for ( int k = 0 ; k <= n ; k++ ) {
                System.out.printf("%10s", sterling1(n, k));
            }
            System.out.printf("%n");
        }
        System.out.println("The maximum value of S1(100, k) = ");
        BigInteger previous = BigInteger.ZERO;
        for ( int k = 1 ; k <= 100 ; k++ ) {
            BigInteger current = sterling1(100, k);
            if ( current.compareTo(previous) > 0 ) {
                previous = current;
            }
            else {
                System.out.printf("%s%n(%d digits, k = %d)%n", previous, previous.toString().length(), k-1);
                break;
            }
        }
    }
    
    private static Map<String,BigInteger> COMPUTED = new HashMap<>();
    
    private static final BigInteger sterling1(int n, int k) {
        String key = n + "," + k;
        if ( COMPUTED.containsKey(key) ) {
            return COMPUTED.get(key);
        }
        if ( n == 0 && k == 0 ) {
            return BigInteger.valueOf(1);
        }
        if ( n > 0 && k == 0 ) {
            return BigInteger.ZERO; 
        }
        if ( k > n ) {
            return BigInteger.ZERO;
        }
        BigInteger result = sterling1(n-1, k-1).add(BigInteger.valueOf(n-1).multiply(sterling1(n-1, k)));
        COMPUTED.put(key, result);
        return result;
    }

}

You may also check:How to resolve the algorithm Doubly-linked list/Traversal step by step in the Python programming language
You may also check:How to resolve the algorithm Count in octal step by step in the VBScript programming language
You may also check:How to resolve the algorithm Host introspection step by step in the PL/I programming language
You may also check:How to resolve the algorithm Greatest element of a list step by step in the Wart programming language
You may also check:How to resolve the algorithm Gray code step by step in the SenseTalk programming language