자바에서 조합을 계산하는 방법은 무엇입니까? 메모를 사용하여?

Question

나는 스스로 자바를 배우고 있으며 나는 지금 메모 작성에 대해 배우고있다. 하지만 내 길을 잃는 일종의 ...

재귀를 사용하고 메모를 사용하여 알고리즘을 가속화하여 Java에서 조합을 계산하는 방법에 대한 샘플 코드가 있습니까?

C5,3 = 5 * 4 * 3/3 * 2 * 1 = 10을 계산하는 방법과 같습니다. 재귀를 사용합니까?

Answer 1

은 예와 함께 할 수 있습니다 (20)는 20 choose 5 이후 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/