//*** 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

//NOTE THE CODE IS MASSIVELY COMMENTED OUT AND PRESERVED CRITICAL COMMENTS ON THE SCREEN....

import java.math.*;
import java.util.*;

class Staircase
{
    int count;   
    static int k = 24; // values in subset will add up to value k
    int[] S; // 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 c(n,r).. It is reset each time....
    int maxRValue;
    
    static int totalcycles=0;
    static int subsetIndex=0;
    
    //this has to be static since class is instantiated on each combination (n,r)
    //it needs to mantain value to ensure the offset from which the successful subsets are returned are not repeated...
    static int difference = 0;  //used to get difference in set size and offset to display results on screen...
   
    //it has to be static since every time the class is instantiated, it will lose its value otherwise....
    //this is now a good indicator to see the cycle on the screen and occurrence of subset totalling k.
    static int i=0;
    
    static Set<String> st; // this will contain the combinations for achieving total k
    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.
    
     // this has to be initialised due to cloning process by valuesSetPrevious
     //if any unexpected occurrences in code, consider this.. However unlikely it will cause issue
     //since it is ample size....
     
    static String[] valuesSet= new String[500];   // this will be used to hold all values from the set...
    
    static String[] valuesSetPrevious = new String[500];
    
    static int len=0;
    
    public Staircase(long combinations, int[] X, int r, Set<String> st, int maxRValue)
    {
        
        int j;
        this.S=S;
        this.st=st;
        this.maxRValue=maxRValue;
        System.out.println("Combinations: " + combinations);
        StringJoiner sj = new StringJoiner(","); // creating StringJoiner for the final output
        StringJoiner sj1 = new StringJoiner(",");  //creating StringJoiner if all numbers same in X []
        
        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
        boolean allSameDigit=false;  // this is used to check if X array contains all number 1's....
        
        String subsetIntToString; //  since it needs to add number back into the StringJoiner, 
        //it has to be converted into a String first....
        
        int pos=0;  // used to index array X. Required so that it can check if previous number holds same value...
        int previousI; //value of previous number in X array
        
        int h=0;
        
        int firstNullValuePosDest=0;
        
        int posFirstNull=0;
        
        int firstNullValuePos=0;
        
        int prevcurrentSetSize=0;
        
        //As per my documentation, there is a serious issue if all the numbers are same in selection..
        // Also it will create a massive hindrance since the r value in combinations will be driven too high...
        
        for (int i: X)
        {
            pos++;
            previousI=i;
            
            subsetIntToString =  Integer.toString(i);
            
            sj.add(subsetIntToString);
            
            //only does previous check if not the first item...
            if (pos>0)
            {
            if (i==previousI)
            {
                allSameDigit=true;
            }
            }
        }
      
        if (!allSameDigit && pos>0)
        {
            System.out.println("This is the solution: " +  sj.toString());
            allSameDigit=false;
            System.exit(0);
        }
        
        System.out.println("INITIAL VALUE OF  CYCLES: " + cycles);
        
        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 number from original subset is : " + steps);
                sj.add(Integer.toString(X[p])); //adds the step into StringJoiner
                
                prevcurrentSetSize=currentSetSize;
                //System.out.println("EARLIEST HERE: " + prevcurrentSetSize);
                
                currentSetSize=st.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 + "    k Value is: " + k);
                //if (total==N /*&& count<=r*/)
                
                if (total==k) // running total equals to defined k
                {
                    //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 k: " + k);
                    //System.out.println("COUNT: " + count);
                    //System.out.println("r: " + r);
                    st.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>k)
            {
                
                total=0; //resets total
                sj = new StringJoiner(","); //creates new instance, resets contents...
            }
            
            newSetSize = st.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:");
                //System.out.println("Total is " + k +  ":  " + stringWithTotal24);
                
            }
            cycles++; //increases cycles
            //it is increasing cycle every time its on the end of completing do while loop
            
            totalcycles++;
            
           
            
            
            //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*500);
        }while (cycles<250000);
        
        // this is now getting the String in the set...
        
        
        //initially i will be 0 and it will output entire contents of the set..
        //once it has completed it first time, it will continue from its last position.
        //this is taken to be difference.... 
        
        //this is only way to process the set entry in an if loop...
        //seems to be inaccurate...
        
         // as per documentation, it is now good opportunity to remove all items.
        //it can not be done from the set, otherwise it will start duplicating entries again....
        // the valuesSet are already overwritten each time...
        //there is only option available...
        
        //Before valuesSet takes all of the set values again, it keeps a copy  (this is ok)
        //The valuesSet then takes values again from set.  (this is ok)
        //complete for loop between valuesSet and old valuesSet.
        //any matches (i.e those that have been displayed to the screen), 
        //in ValuesSet, it changes String to "ALREADY PROCESSED".
        
        // the valuesSetPrevious is cumulative...
        //so it is not a clone!!!!
        //the system.arraycopy has to occur on destination starting at its existing length.....
        
        //System.out.println("FDSFDSF: " + lengthvaluesSet);
        
        //String valuesSetPrevious[]=valuesSet.clone();
         
         
         //the destPos is a bit tricky...  
         //need to figure this out from logic below.....
         //it should be consistent with set size... since zero index, this would be the first spot with null..
         
         // len requires severe thought.. This refers to the length of data that needs to be copied from
         // valuesSet to valuesSetPrevious
         //surely the length is required to be the difference from a logical mindset  (valuesSet-valuesSetPrevious)
         //since valuesSet is getting bigger alongside Set...
         //but we know both have length inline with the declaration 500,000
         //We require difference in filled content!!!!
         //Length valuesset would just be the same as the set size.....
         //Length of valuesSetPrevious  would be 0 initially.
         //it would then take the value of the oldsetsize.... this variable already defined... (currentSetSize);
         //so length would be  newSetSize-currentSetSize....
         
         //valuesSet is the exact contents of the set...
         //newSetSize is the difference between  set size from the last occurence..... this has to be the destPos...
         
         
         System.out.println("NEW SET SIZE: " + newSetSize);
         System.out.println("CURRENT SET SIZE: " + firstNullValuePos);
         
         
         System.out.println("NSS:" + newSetSize);
       
         //sourcepos surely must be destpos + length?
         int sourcePos = newSetSize + (newSetSize-prevcurrentSetSize);
         //prevcurrentSetSize
        //destPos could also be first position it finds a null in destination... 
         //System.arraycopy(source_arr, sourcePos, dest_arr,  destPos, len);
         
         int k=0;
         
         System.out.println("DDSADSDFDSFSDF WHY NOTHING: " + valuesSetPrevious[0]);
         
         for (String g: valuesSetPrevious)
         {
             k++;
             
             if (g==null);
             {
             //it is k-1 since the increment had to happen first  outside of this loop
             //in practce k could have occurred before the break...
             //but then it does not get effect of checking each String from start to finish due to condition in this loop
             
             firstNullValuePosDest=k-1;
             break;
             
             }
             
         }
         
         
         
         //System.out.println("source pos: " + firstNullValuePos);
         //System.out.println("source pos: " + (len+1));
         System.out.println("source pos: " + (subsetIndex));
         
         System.out.println("dest pos: " + firstNullValuePosDest);
         System.out.println("length: " + (newSetSize-firstNullValuePos));
          System.out.println("current values in set: " + valuesSet.length);
         System.out.println("pos first zero in valuesSet: " + firstNullValuePos);
         
         
         //all number variables need to be declared static to preserve state!!!!!
         
         //sourcePos = does not need to be static, its re-calculated
         //destPost = does not need to be static, its re-calculated
         //  len is:       basically if this was the valuesSet    {already processed  },   {  },  {    },   NULL,  NULL
          //firstNullValuePos would be 4
         // already processed would be 1
         // we need 2 and 3
         // Length would be 1 less than   4-1
          
          int lengthvaluesSetPrev;
          
          if (valuesSetPrevious[0]==null)
          {
              lengthvaluesSetPrev = 0; 
              
          }
          
          //in here need to check where the first value occurs.
          //this has been processed elsewhere....
          //and then assign the length here to it.
          //no adjustment needed since its zero indexed....
          
          else
          {
              //posFirstNull was already calculated when it was scanning through the valuesSetPrev
              //to identify values and check to see if it appears in valuesSet (to ensure no screen duplication)
              
              lengthvaluesSetPrev=posFirstNull;
              
          }
         
         len = len + (firstNullValuePos-lengthvaluesSetPrev);
         
         //int sourcePos;
         
         //prevent fail below..... and will force it back at 0 index....
         
         if (newSetSize==0)
         {
             sourcePos=0;
         }
         
         
         
         //System.arraycopy(source_arr, sourcePos, dest_arr,  destPos, len);
         if (st.size()>0  && firstNullValuePos!=0)
         {
         System.out.println("*****PERFORM COPY ********************");
        //System.arraycopy(valuesSet, sourcePos, valuesSetPrevious, firstNullValuePosDest, (firstNullValuePos-lengthvaluesSetPrev));
        System.arraycopy(valuesSet, subsetIndex, valuesSetPrevious, subsetIndex,  len);
         System.out.println("*************************");
         }
        
        System.out.println("This is length content filled into valuesSetPrevious: " + (firstNullValuePos-lengthvaluesSetPrev));
        
        System.out.println("MUST BE dest !!!!!!:      " + valuesSetPrevious[0]);
        
        
        if (st.size()>2)
        {
            System.out.println("MUST BE src !!!!!!:      " + valuesSet[2]);
            
        }
        
        
        
        //System.out.println("MUST BE src !!!!!!:      " + valuesSet[0]);

        
        System.out.println("confirm clone");
        
        for(String m: valuesSetPrevious)
        {
            
            if (m!=null)
            {
            System.out.println(m);
            System.out.println("CONTENT!!!!!");
            }
            h++;
        }
        
        h=0;
        
        valuesSet = st.toArray(new String[st.size()]);
        
        
        System.out.println("length of previous set: " + valuesSetPrevious.length);
        
        for (int n=0; n<valuesSetPrevious.length; n++)
        {
            if (valuesSetPrevious==null)
            {
                posFirstNull=n;
                System.out.println("%^$%^: " + posFirstNull);
            }
            
            for (int p=0; p<valuesSet.length; p++)
            {
                //System.out.println("VERY CRITICAL&&^&%^&$^^%$^$%^$%^: " + valuesSet[p]);
                
                if (valuesSetPrevious!=null)
                {
                    
                    
                if (valuesSetPrevious[n]==valuesSet[p])
                {
                    System.out.println(valuesSet[p]);
                    valuesSet[p]="ALREADY PROCESSED";
                    
                }
            }
                
            }
        }
        
        
        System.out.println("*************NEW VALUE CYCLES: " + cycles);
        System.out.println("*************RUNNING TOTAL CYCLES: " + totalcycles);
        
        System.out.println("***PROCESSING SET AT INDEX: " + (difference));
        System.out.println("***********************ENDING AT INDEX:***** " + st.size());
        
        
        for (int i=0; i<valuesSet.length; i++)
        {
            if (valuesSet[i]!="ALREADY PROCESSED")
            {
                subsetIndex++;
            
            System.out.println(valuesSet[i] + "    Subset: " + subsetIndex  + "  at cycle number: " + totalcycles);
            
            }
            
            //it has to do this once only.....
            //it can break out for loop since once its hit a null, not expected to find any other sets further..
            if (valuesSet[i]==null)
            {
                firstNullValuePos=i;
                break;
            }
            
        }
        
        //System.out.println("Size of valueSet: " + valuesSet.length);
        //System.out.println("Size of set: " + newSetSize);
        
        //on first time it reaches above,    currentSetSize will be 0....
        //next time, currentsetSize will be previously newSetSize....
        //so it will perform incremental difference...
        
        //Set is zero index,  so it would have completed 5 items at  s.get(4)
        //s.size() is actual length...
        //if set size was 5 after  first  C(n,r) ,  it would have processed 0,1,2,3,4
        //difference would  be  5-0 = 5
        //so this is correct start point.....
        
        //difference = newSetSize;
        
        }  //end of constructor...
}
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 []{12,1,61,5,9,2}; //user defined
    //int [] X = new int []{1,2,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1};
    //int [] X = new int []{12,1,61,5,9,2}; //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=null; //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("Staircase size is:  " + Staircase.k);
    //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=(Staircase.k)/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.k + ")");
    //additional 1 added due to potential rounding errors
    
    //as per the findings in the documentation.....
    if (maxRValue>=64)
    {
        System.out.println("Value is too high computationally. It will be reduced to: " + (maxRValue-1));
    }

    
    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, maxRValue);
        
    }
    
    
    Iterator iterator = Staircase.st.iterator();
    
    while (iterator.hasNext())
    {
        System.out.println(iterator.next());
    }
    
    System.out.println("Value set");
    
    for (int j=0; j<sc.valuesSet.length; j++)
    {
        System.out.println(sc.valuesSet[j]);
        
    }
    
    
    
}

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)
    }
    
}