Комбинаторный 'N выбирают R' в java математике?

Question

Есть ли в java-библиотеке встроенный метод, который может вычислить 'N Choose R' для любого N, R?

Answer 1

Формула

На самом деле очень просто вычислить N choose K даже без вычисления факториалов.

Мы знаем, что формула для (N choose K):

    N!
 --------
 (N-K)!K!

Следовательно, формула для (N choose K+1):

       N!                N!                   N!               N!      (N-K)
---------------- = --------------- = -------------------- = -------- x -----
(N-(K+1))!(K+1)!   (N-K-1)! (K+1)!   (N-K)!/(N-K) K!(K+1)   (N-K)!K!   (K+1)

То есть:

(N choose K+1) = (N choose K) * (N-K)/(K+1)

Мы также знаем, что (N choose 0) это:

 N!
---- = 1
N!0!

Так что это дает нам легкую отправную точку, и, используя формулу выше, мы можем найти (N choose K) для любого K > 0 с K умножениями и K делениями.

---

Треугольник Легкого Паскаля

Собрав все вместе, мы легко можем сгенерировать треугольник Паскаля следующим образом:

    for (int n = 0; n < 10; n++) {
        int nCk = 1;
        for (int k = 0; k <= n; k++) {
            System.out.print(nCk + " ");
            nCk = nCk * (n-k) / (k+1);
        }
        System.out.println();
    }

Это печатает:

1 
1 1 
1 2 1 
1 3 3 1 
1 4 6 4 1 
1 5 10 10 5 1 
1 6 15 20 15 6 1 
1 7 21 35 35 21 7 1 
1 8 28 56 70 56 28 8 1 
1 9 36 84 126 126 84 36 9 1 

---

BigInteger версия

Применение формулы для BigInteger довольно просто:

static BigInteger binomial(final int N, final int K) {
    BigInteger ret = BigInteger.ONE;
    for (int k = 0; k < K; k++) {
        ret = ret.multiply(BigInteger.valueOf(N-k))
                 .divide(BigInteger.valueOf(k+1));
    }
    return ret;
}

//...
System.out.println(binomial(133, 71));
// prints "555687036928510235891585199545206017600"

По данным Google, 133 выберите 71 = 5,55687037 × 10 ³⁸ .

---

Ссылки * * тысяча пятьдесят-одна Википедия / Биномиальный коэффициент Википедия / треугольник Паскаля Wikipedia / Combination

Answer 2

Apache-Commons "Math" поддерживает это в org.apache.commons.math4.util.CombinatoricsUtils

Answer 3

Рекурсивное определение дает вам довольно простую функцию выбора, которая отлично подойдет для небольших значений. Если вы планируете многократно использовать этот метод или использовать большие значения, стоит запомнить его, но в остальном он работает просто отлично.

public static long choose(long total, long choose){
    if(total < choose)
        return 0;
    if(choose == 0 || choose == total)
        return 1;
    return choose(total-1,choose-1)+choose(total-1,choose);
}

Улучшение времени выполнения этой функции оставлено как упражнение для читателя :)

Answer 4

Я просто пытаюсь подсчитать количество комбинаций из двух карт с разным размером колоды ...

Нет необходимости импортировать внешнюю библиотеку - из определения комбинации, с n карточками, которые будут n*(n-1)/2

Бонусный вопрос: Эта же формула вычисляет сумму первых n-1 целых чисел - понимаете, почему они одинаковы? :)

Answer 5

N! / ((R!) (N-R)!)

В этой формуле можно многое отменить, поэтому факториалы обычно не проблема. Допустим, что R> (N-R) затем отменяет N! / R! в (R + 1) * (R + 2) * ... * N. Но правда, int очень ограничен (около 13!).

Но тогда можно было бы с каждой итерации делить. В псевдокоде:

d := 1
r := 1

m := max(R, N-R)+1
for (; m <= N; m++, d++ ) {
    r *= m
    r /= d
}

Важно начать деление с одного, даже если это кажется излишним. Но давайте сделаем пример:

for N = 6, R = 2: 6!/(2!*4!) => 5*6/(1*2)

Если мы опускаем 1, мы вычисляем 5/2 * 6. Разделение оставило бы целочисленный домен. Оставляя 1, мы гарантируем, что мы не сделаем этого, так как первый или второй операнд умножения является четным.

По той же причине мы не используем r *= (m/d).

Все это может быть пересмотрено до

r := max(R, N-R)+1
for (m := r+1,d := 2; m <= N; m++, d++ ) {
    r *= m
    r /= d
}

Answer 6

Математическая формула для этого:

N!/((R!)(N-R)!)

Не должно быть трудно понять это оттуда:)

Answer 7

binomialCoefficient, в Общая математика

Answer 8

Следующая процедура вычислит n-choose-k, используя рекурсивное определение и памятку. Процедура чрезвычайно быстрая и точная:

inline unsigned long long n_choose_k(const unsigned long long& n,
                                     const unsigned long long& k)
{
   if (n  < k) return 0;
   if (0 == n) return 0;
   if (0 == k) return 1;
   if (n == k) return 1;
   if (1 == k) return n;
   typedef unsigned long long value_type;
   value_type* table = new value_type[static_cast<std::size_t>(n * n)];
   std::fill_n(table,n * n,0);
   class n_choose_k_impl
   {
   public:

      n_choose_k_impl(value_type* table,const value_type& dimension)
      : table_(table),
        dimension_(dimension)
      {}

      inline value_type& lookup(const value_type& n, const value_type& k)
      {
         return table_[dimension_ * n + k];
      }

      inline value_type compute(const value_type& n, const value_type& k)
      {
         if ((0 == k) || (k == n))
            return 1;
         value_type v1 = lookup(n - 1,k - 1);
         if (0 == v1)
            v1 = lookup(n - 1,k - 1) = compute(n - 1,k - 1);
         value_type v2 = lookup(n - 1,k);
         if (0 == v2)
            v2 = lookup(n - 1,k) = compute(n - 1,k);
         return v1 + v2;
      }

      value_type* table_;
      value_type dimension_;
   };
   value_type result = n_choose_k_impl(table,n).compute(n,k);
   delete [] table;
   return result;
}

Answer 9

ArithmeticUtils.factorial явно устарела. Пожалуйста, попробуйте CombinatoricsUtils.binomialCoefficientDouble(n,r)

Answer 10

гуава имеет IntMath # бином (int, int) , LongMath # бином (int, int) и BigIntegerMath # бином (int, INT) .