//*** CODE ***
/*
Online Java - IDE, Code Editor, Compiler
Online Java is a quick and easy tool that helps you to build, compile, test your programs
online.
*/
// This has been created to ensure I can utilize any random functions more efficiently.
// It is a creation of the combinations (with replacement) calculator.
// It has used techniques I learnt including recursion and also memoization to speed up execution.
// I will incorporate this into Java applications I created previously..
//TEST CASES
// All done on My Approach

import java.math.*;
import java.util.*;
class Staircase
{
    int N; // this can be changed by end user, size of the staircase
    int[] X; // this is the array containing the steps
    int p; // this is random number generated
    int total; // this is running total of the steps
    int cycles=0; // this is number of cycles completed for each
    Set<String> s; // this will contain the combinations for achieving total N
    Random rand = new Random(); // object created of type Random.
    // there is no sense of X getting smaller since its with replacement....
    // need to only add the stringJoiner (converted into string) into the set if the total is equal to N
    // if total goes over, it will continue adding until all cycles for C^R (n,r) has finished
    // Combinations is total of combinations for C^R(n,r)
    // r is the sample size... This can exceed n.
    int newSetSize; // holds size of set after entry added
    
    public Staircase(long combinations, int[] X, int r, Set<String> s, int lengthEncodedMessage)
    {
        this .N=lengthEncodedMessage;
        this.X=X;
        this.s=s;
        System.out.println("Combinations: " + combinations);
        StringJoiner sj = new StringJoiner(","); // creating StringJoiner
        int currentSetSize=0; // holds size of set before entry added
        
        int count;
        int q; //used in the for loop to iterate through r
        int steps; // it will hold value of step generated randomly from r
        
        do
        {
            count=1;
            
            //sets count back to 1 when it has finished. This is visual check to ensure that r is not exceeded
            
            for (q=0; q<r;q++) // processing up to r only since this is the sample size
            {
                p= rand.nextInt(X.length); // if length 3, it will give index numbers 0-2... This is suitable
                steps = X[p]; // step value
                System.out.println("\nrandom step is: " + steps);
                sj.add(Integer.toString(X[p])); //adds the step into StringJoiner
                currentSetSize=s.size(); //current size of set
                total=total+steps; //keeps running total
                System.out.println("This is performing: " + (q+1) +" of " + r + "(r)");

                //reminding end user value N and running total
                System.out.println("TOTAL HERE: " + total + "    N Value is: " + N);
                //if (total==N /*&& count<=r*/)
                
                if (total==N) // running total equals to N (steps in staircase)
                {
                    System.out.println("This is stringjoiner right now: " + sj.toString());
                    System.out.println("Count:" + count);
                    System.out.println("current:" + currentSetSize);
                    System.out.println("TOTAL: " + total);
                    System.out.println("VALUE OF N: " + N);
                    System.out.println("COUNT: " + count);
                    System.out.println("r: " + r);
                    s.add(sj.toString()); // it will only add it if the conditions are met above (size of r and Total=N)
                    
                    count++;
                    
                }
                
                if (q==r-1) // if its on the last loop..
                {
                    sj = new StringJoiner(",");
                    total=0;
                    
                }
                
            }
            
            if (total>N)
            {
                total=0; //resets total
                sj = new StringJoiner(","); //creates new instance, resets contents...
            }
            
            newSetSize = s.size(); // new set size
            System.out.println("new size: "+ newSetSize);
            
            if (newSetSize>currentSetSize) //if larger, i.e a new combination, it will inform end user..
            {
                System.out.println("This has been added into the set:");
                
            }
            cycles++; //increases cycles
            System.out.println("Number of cycles: " + cycles + "\n");
            // can not set this to a certain set size... since it is giving total combinations (with replacement) and not 
            // related to placing items in certain order in which once combinations are known.
            // There are most likely distributions in statistics which might assist with the cycles...
            // This can only be placed in speculatively like throwing dice (a fixed time) and getting total....
            //the safest option for the maximum iterations is combinations x 10.
            //but in reality there is no guarantee that it would have covered all combinations at least once in that duration...
            
            
        }while (cycles<combinations*10);
        
        // this is now getting the String in the set...
        
        for (String g: s)
        {
            System.out.println(g.toString());
        }
        
        
        
        }  //end method
        
        int counter;
        String[] arrangements = new String[newSetSize];
        
        public Set<String> arrangements()
        {
             //Iterator<String> iterator = s.iterator();
             
        
        
        //while (iterator.hasNext()) 
        //{
         //   arrangements[counter]=String.valueOf(iterator);
          //  System.out.println(arrangements[counter]);
        //    counter++;
        //}
        
        return s;
            
        }
    }
public class Combination
{
    Staircase sc; //object of type Staircase
    
    public Combination (int[] lengthLetters, int lengthEncodedMessage)
    {
        System.out.println("IN HERE-----------------------------------------------------------------");
        System.out.println("Welcome to Online IDE!! Happy Coding :)");
    int originalNumber=0; // for moment it is declared a 0 to keep next line content...
    
    int n=originalNumber;
    
    int r; // this does not need be in for loop. user defined
    
    Set <String> s = new HashSet<>(); // it will contain all combinations...
    
    //int [] X = new int []{5,6,7}; //user defined
    int [] X = lengthLetters;
    
    int minimum; // the smallest value in X. This will assist with generating r value...
    
    int maxRValue; //upper limit for r in the loop to process 0<r<=maxRValue+1
    
    
    //need to understand that r can be greater than n in replacement.......
    //r is taken from n objects
    // in this example, r can get larger....
    
    Map <Integer, Long> m; // this can stay outside loop since its not impacted by size of n and r
    
    n=X.length; //length of the array X of steps
    
    System.out.println("Staircase size is:  " + lengthEncodedMessage);
    System.out.println("Steps are: " + Arrays.toString(X));
    
    originalNumber=n; // this will remain constant during a full iteration..
    
    m= new HashMap<>(); //new instance is required to start process again...
    //r can be estimated as follows based on:
    //Maximum length of a combination is approximately (N/ minimum value in X)
    
    minimum=X[0];

    for (int i=0; i<X.length;i++)
    {
        if (X[i]<minimum && X[i]!=0)
        {
            minimum=X[i];
            
        }
        
    }
    maxRValue=(lengthEncodedMessage)/minimum;
    //informs end user of constraints...
    System.out.println("Maximum value of r: " + (maxRValue+ 1) + " has been set using minimum value in set: " + minimum + " , which should be in proximity to N(" + lengthEncodedMessage + ")");
    //additional 1 added due to potential rounding errors

    for (r=0; r<=maxRValue+1; r++)
    {
        System.out.println("\n***COMBINATIONS*** (WITH REPLACEMENT)");
        
        System.out.println("C^R(n + r) = " + "(n+r-1)! / r!(n-1)!");
        
        System.out.println("C^R(" + n+","+r+") = " + (n+r-1)+ "!" + " / " + r+"!"+"("+(n-1)+")!");
        
        //creates instance of Staircase and main execution of code...
        sc = new Staircase (Combinations (n,r,originalNumber, m), X, r,s,lengthEncodedMessage);
        
    }
        
        
    }
    
    
    public static long Combinations (int n, int r, int originalNumber, Map factorialResults)
{
    long result=0;
    int denominator1; //denominator split two parts since there are two factorial calculations
    int denominator2; //denominator split two parts since there are two factorial calculations
    int Numerator=n+r-1; // Numerator
    int zero=0;
    long zeroFactorial = 1;
    // if no sample or objects, there are no outcomes...
    if (originalNumber==0 && r==0)
    {
        System.out.println("n and r can not both be equal to zero");
        //System.exit(0);
        
        return 0;
        
    }
    //this situation would occur if n is 0 only and r is any positive number accept 0 (if statement above)
    //for instance (C^R (n,r)) = (0,3) 0+3-1 = 2 2<3

    if (originalNumber==0 && originalNumber+r-1<r)
    {
        System.out.println("n+r-1 must be > or = to r");
        //System.exit(0);
        return 0;
        
    }
    
    if (Numerator>=1)
    {
        result = ((n+r-1)* (Combinations (n-1, r,originalNumber, factorialResults)));
        // this completes factorial for numerator
        factorialResults.put(Numerator,result); //result stored in the Map
        //factorialResults.put(n-1,result); //result stored in the Map
        //System.out.println("getting result back out numerator: " + (Numerator) + " " + factorialResults.get(n+r-1));
        
        if (n==originalNumber) // this will occur once
        {
            denominator1 = r;
            denominator2 = originalNumber-1;
            factorialResults.put(zero,zeroFactorial); //0! is equal to 1
            
            if (factorialResults.containsKey(denominator1) && factorialResults.containsKey(denominator2))
            {
                long returnValue = result / ((long)factorialResults.get(denominator1) *(long)factorialResults.get(denominator2));
                return returnValue;
                
            }
            
        }
        return result;
        
    }
    return 1; // it will reach here only when condition not met (Numerator>=1)
    }
    
}