/* 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 //r=2 n=5 PASS //r=5 n=5 PASS //r=1 n=4 PASS //r=0 n=3 FAIL it is getting 2... it should be getting 1........... (FIXED IN THE COMBINATION CALCULATOR ITSELF) //r=0 n=0 need validation code... not allowed (FIXED in the calculator)..... // now going to flip the above //r=5 n=2 PASS //r=5 n=5 PASS //r=4 n=1 FAIL its getting 24 all the ones where r is bigger than n are currently failing..... //r=3 n=0 FAIL.... FIXED //test to make numerator less than r // n = 4 r=3 FAIL n+r-1 must be > or = to r (FIXED) import java.math.*; import java.util.*; public class Combination { public static void main(String[] args) { System.out.println("Welcome to Online IDE!! Happy Coding :)"); // this is going to be slight challenge... int originalNumber=0; // for moment it is declared a 0 to keep next line content... This variable is based on the size of n in outer for loop... int n=originalNumber; // this can stay here.... int r; // this does not need be in for loop int [] x = new int []{1,2,3}; //just to keep this loop flowing, I will complete exercise inline with 3 values in k.. // Require a nested loop as follows and execution has to run separately //These are all scenarios //n=1 to n< X.length() //r=1 to r<=n //need to understand that r can be greater than n in replacement....... //r is taken from n objects // in this example, does r need to get bigger than n Map m; // this can stay outside loop since its not impacted by size of n and r // this will never reach situation where r or n is equal 0 // need to see what will happen if n=1 for (n=0; n<=x.length; n++) // this should go from 1 to 3 { System.out.println("VALUE N: " + n); originalNumber=n; // this will remain constant during a full iteration.. m= new HashMap<>(); //new instance is required to start process again... for (r=0; r<=n+5; r++) // for moment r is set 5 more than objects available.. This bit can be experimented later.. { System.out.println("Value r: " + r); //("n and r cannot both = 0"); if (n==0 && r==0) { System.out.println("when"); r++; } if (n+r-1 or = to r"); } else { if (n!=0) // n+r-1 >=r //(this is condition that should be met....) { System.out.println("***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)+")!"); System.out.println(Combinations (n,r,originalNumber, m)); } } } } } public static long Combinations (int n, int r, int originalNumber, Map factorialResults) { // n are objects // r is sample /* ***CALCULATION*** (n+r-1)! / r!(n-1)! */ 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 (n==0 && r==0) { System.out.println("n and r can not both be equal to zero"); 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 (n+r-1 or = to r");. return 0; } if (Numerator>=1) // this will ensure that all factorials as low as 1! are processed //reason for this is since C^R(r,n) for instance C^R(1,0) //(n+r-1) = 0 // This does not seem like an issue but since the numerator is calculated as follows: //result = ((n+r-1)* (Combinations (n-1, r,originalNumber, factorialResults))); // this completes factorial for numerator // it can be seen that Java will not be content with 0 * another number..... // As an offset, since the denominator relies on mapped values for numerator, there will be no entry in the map for //0!. The only way to overcome this is to put an entry manually for 0! = 1... { //System.out.println("value of n: " + Numerator); // EXAMPLE // C^R (5,6) = (5+6-1)! / 6! (5-1)! = 3628800 / (6! * 4!) = 3628800 / 720 * 24 = 210 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)); System.out.println("value of n:" + n); if (n==originalNumber) // this will occur once { denominator1 = r; // r sample size has not changed denominator2 = originalNumber-1; // originalNumber required since n has reduced as part of the recursive calls // this is using the Java Memoization technique to ensure the factorial outcome is not calculated again, to save program cycles. // since the returns are done in reverse order.... n = 1 is processed first and n=6 last... Hence in practice // there will be entry in Map for all factorials, ready for the denominator.. //n+r-1 r=6 n = 3 or 2 or 1 so recursive values going in set are 8! , 7!, 6! factorial // but the put method for the set would recursively call and populate others up to 1! // this is where it currently fails for cases such as C^R (3,0), (1,0) //reason is since it would have not created an entry for 0! at any point in time //entry being created now factorialResults.put(zero,zeroFactorial); //0! is equal to 1 System.out.println("den1:" + denominator1); System.out.println("den2:" + denominator2); if (factorialResults.containsKey(denominator1) && factorialResults.containsKey(denominator2)) { //System.out.println("here"); System.out.println("This is exact value of factorial denominator part1 " + (denominator1) + " : " + factorialResults.get(denominator1)); System.out.println("This is exact value of factorial denominator part2 " + (denominator2) + " : " + factorialResults.get(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) } }