如何在java中計算組合？通過使用memoization？

Question

我正在學習JAVA，我正在學習有關memoization。但我有點失去我的方式...

有沒有人有關於如何通過使用遞歸和使用memoization來加速算法計算在Java組合的示例代碼？

就像計算C5,3 = 5 * 4 * 3/3 * 2 * 1 = 10的方法一樣。但使用遞歸？

Answer 1

讓我們用一個例子做20選5

由於20 choose 5被定義爲20!/(5! * (20-5)!)

我們可以使用memoization來存儲那些因子計算，所以我們不必連續在我們的遞歸下重新計算它們。

所以：

//STORING FACTORIAL COMPUTATIONS 
    private Map<Integer,Long> factorialMap = new HashMap<Integer,Long>(); 


    public Long getFactorial(int number) { 

     //CHECK IF I ALREADY COMPUTED THIS FACTORIAL 
     Long val = factorialMap.get(number); 
     if(val != null) { 
      //GOT IT! 
      return val; 
     } else { 
      //NEED TO COMPUTE! 
      val = getFactorialRecursive(number); 
      //STORING IT TO SAVE COMPUTATION FOR LATER 
      factorialMap.put(number, val); 
      return val; 
     } 
    } 

    //RECURSIVE FUNCTION TO COMPUTE FACTORIAL 
    public Long getFactorialRecursive(int number) { 
     if(number < 2) { 
      return 1L; 
     } else { 
      return number * getFactorialRecursive(number-1); 
     } 
    } 


    //ACTUAL CALL TO "20 choose 5" 
    public Long combination(int fromVal, int chooseVal) { 
     return getFactorial(fromVal)/(getFactorial(chooseVal)*getFactorial(fromVal-chooseVal)); 
    } 

Answer 2

可以使用combinatoricslib庫可以免費在這裏：

http://code.google.com/p/combinatoricslib/