/*
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 
{
    static int N = 4;     // 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.
    
    public Staircase(long combinations, int[] X, int r, Set<String> s)
    {
        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 newSetSize;      // holds size of set after 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... since it is giving total combinations (with replacement) and not necessarily
        // related to obtaining a total of 6 with each...
        // 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.
        
        }while (cycles<combinations*10);
        
        // this is now getting the String in the set...
        for (String g: s)
        {
            System.out.println(g.toString());
        }
        
    }
}


public class Combination
{
    public static void main(String[] args) 
    {
        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 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
        Staircase sc;  //object of type Staircase
        
        
        //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("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 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=(Staircase.N)/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(" + Staircase.N + ")");
             
             //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);
                 
             }
    }
    
    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)
    }
}