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

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

public class Permutation
{
    public static void main(String[] args) {
        System.out.println("Welcome to Online IDE!! Happy Coding :)");
        
        int originalNumber=6;
        int n=originalNumber;
        int r =3;
        Map <Integer, Long> m = new HashMap<>();
        
        System.out.println("***PERMUTATIONS***");
        System.out.println("P(" + n+","+r+") = " + n+"!" + " / " + "("+n+"-"+r+")!");
        System.out.println(Permutations (n,r,originalNumber, m));
        
    }
    
    public static long Permutations (int n,  int r, int originalNumber, Map factorialResults)
    {
        
        // n are objects
        // r is sample
       
       /*
       ***CALCULATION***
        P(n,r) =   n! / (n−r)!
        
        */
        
        long result=0;
        int temp;
        int denominator;
        
        if (n>=1)
        {
            
            // EXAMPLE
            
            // P (5,6)   =   5* 4 * 3 * 2 * 1   /   (6-5)!     =    24 / 2!    =  24 / 2 * 1   =    24/2  = 12
            
        
        result = (n* (Permutations (n-1, r,originalNumber, factorialResults)));  // this completes factorial for numerator
        
        factorialResults.put(n,result);  //result stored in the Map
        //System.out.println("getting result back out: " + factorialResults.get(n));
        
        
        if (n==originalNumber)    // this will occur once
        {
            
            denominator = originalNumber-r;   // originalNumber required since n has reduced as part of the recursive calls
            //System.out.println(denominator);
            
            
        // this is using the Java Memoization technique to ensure the factorial outcome is not calculated again, to save program execution 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..
        
            if (factorialResults.containsKey(denominator))  
            
            {
                //System.out.println("here");
                //System.out.println("This is exact value of factorial  " + (denominator) + " : " +  factorialResults.get(denominator));
                
                return result / (long)factorialResults.get(denominator);  // this is number permutations
            }
           
        }
        
                return result;  // this will be returning already calculating numerator part 
            
        }
          return 1;     // it should not reach here..
        }
        
    }