Комбинаторный "N выбирает R" в Java-математике?

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

Ответ 1

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

Ответ 2

Формула

На самом деле очень легко вычислить 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 делениями.

Треугольник Easy Pascal

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

    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 ³⁸.

Ссылки

Ответ 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);
}

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

Ответ 4

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

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

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

Ответ 5

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

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

Невозможно понять это оттуда:)

Ответ 6

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 out, мы вычислили 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
}

Ответ 7

binomialCoefficient, в Commons Math

Ответ 8

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

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;
}

Ответ 9

guava имеет IntMath # binomial (int, int), LongMath # binomial (int, int) и BigIntegerMath # binomial (int, int).

Ответ 10

ArithmeticUtils.factorial, по-видимому, теперь не рекомендуется. Попробуйте CombinatoricsUtils.binomialCoefficientDouble(n,r)

Ответ 11

Подобно версии guava, здесь есть класс BigIntegerMath здесь Ричардом Дж. Матаром, названным org.nevec.rjm, который пакет классов.

Их реализация предоставляет две подписи для биномиального метода: int, int и BigInteger, BigInteger.

Ответ 12

Использование hashmap для улучшения решения @dimo414:

private static Map<Integer, Map<Integer, Integer>> map = new HashMap<>();
private static int choose(int total, int choose){
    if(total < choose)
        return 0;
    if(choose == 0 || choose == total)
        return 1;

    if (! (map.containsKey(total) && map.get(total).containsKey(choose))){
        map.put(total, new HashMap<>());
        map.get(total).put(choose, choose(total-1,choose-1)+choose(total-1,choose));
    }
    return map.get(total).get(choose);
}

Ответ 13

public static void combinationNcK(List<String> inputList, String prefix, int chooseCount, List<String> resultList) {
    if (chooseCount == 0)
        resultList.add(prefix);
    else {
        for (int i = 0; i < inputList.size(); i++)
            combinationNcK(inputList.subList(i + 1, inputList.size()), prefix + "," + inputList.get(i), chooseCount - 1, resultList);

        // Finally print once all combinations are done
        if(prefix.equalsIgnoreCase("")){
            resultList.stream().map(str->str.substring(1)).forEach(System.out::println);
        }
    }
}

public static void main(String[] args) {
    List<String> positions = Arrays.asList(new String[] { "1", "2", "3", "4", "5", "6", "7", "8", "9", "10", "11", "12" });
    List<String> resultList = new ArrayList<String>();
    combinationNcK(positions, "", 3, resultList);
}

Ответ 14

Согласно формуле: n!/((Nk)! * K!) Если мы просто вычисляем числитель и знаменатель, многие вычисления будут потрачены впустую, и, вероятно, диапазон "int", "float" или даже "BigInteger" может заполниться. Таким образом, чтобы преодолеть этот сценарий, мы можем отменить все до того, как умножим значения.

предположим, что n = 6, k = 3

который => 6 * 5 * 4 * 3 * 2 * 1/((3 * 2) * (3 * 2))

Предположим, если мы умножим числитель, диапазон можно заполнить. Лучший вариант - отменить его, прежде чем даже умножить значения.

В этом case--> если мы отменим все, что у нас осталось: (2 * 5 * 2)

умножение этих значений намного проще и потребует меньше вычислений.

================================================== ====

Приведенный ниже код будет работать "эффективно" для чисел, где:

n == k
к <п
k == 0
разница между n и k слишком велика, например. n = 1000, k = 2
k = n/2 (САМОЕ ПРОЧНОЕ)
Значение k близко к половине значения n

Вероятно, код еще можно улучшить.

BigInteger calculateCombination(int num, int k) {

    if (num == k || k == 0)
        return BigInteger.ONE ;

    int numMinusK = num - k;
    int stopAt; // if n=100, k=2 , can stop the multiplication process at 100*99
    int denominator;

    // if n=100, k=98 OR n=100, k=2 --> output remains same.
    // thus choosing the smaller number to multiply with
    if (numMinusK > k) {
        stopAt = numMinusK;
        denominator = k;
    } else {
        stopAt = k;
        denominator = numMinusK;
    }

    // adding all the denominator nums into list
    List<Integer> denoFactList = new ArrayList<Integer>();
    for (int i = 2; i <= denominator; i++) {
        denoFactList.add(i);
    }

    // creating multiples list, because 42 / 27 is not possible
    // but 42 / 3 and followed by 42 / 2 is also possible
    // leaving us only with "7"
    List<Integer> multiplesList = breakInMultiples(denoFactList);
    Collections.sort(multiplesList, Collections.reverseOrder());

    Iterator<Integer> itr;
    BigInteger total = BigInteger.ONE;
    while (num > 0 && num > stopAt) {

        long numToMultiplyWith = num;
        if (!multiplesList.isEmpty()) {
            itr = multiplesList.iterator();
            while (itr.hasNext()) {
                int val = itr.next();
                if (numToMultiplyWith % val == 0) {
                    numToMultiplyWith = numToMultiplyWith / val;
                    itr.remove();
                }
            }
        }

        total = total.multiply(BigInteger.valueOf(numToMultiplyWith));
        num--;
    }
    return total;

}

ArrayList<Integer> breakInMultiples(List<Integer> denoFactList) {
    ArrayList<Integer> multiplesList = new ArrayList<>();
    for (int i : denoFactList)
        updateListWithMultiplesOf(multiplesList, i);
    return multiplesList;
}

void updateListWithMultiplesOf(ArrayList<Integer> list, int i) {
    int count = 2;
    while (i > 1) {
        while (i % count == 0) {
            list.add(count);
            i = i / count;
        }
        count++;
    }
}

Ответ 15

Уже есть много представленных решений.

Некоторое решение не учитывало целочисленное переполнение.
Некоторое решение рассчитало все возможные nCr при заданных n и r. Результат требует больше времени и места.

В большинстве случаев нам нужно рассчитать nCr напрямую. Я собираюсь поделиться еще одним решением.

static long gcd(long a, long b) {
    if (a == 0) return b;
    return gcd(b%a, a);
}

// Compute (a^n) % m
static long bigMod(long a, long n, long m) {
    if (n == 0) return 1;
    if (n == 1) return a % m;
    long ret = bigMod(a, n/2, m);
    ret = (ret * ret) % m;
    if (n % 2 == 1) return (ret * a) % m;
    return ret;
}

// Function to find (1/a mod m).
// This function can find mod inverse if m are prime
static long modInverseFarmetsTheorem(long a, long m) {
    if (gcd(a, m) != 1) return -1;

    return bigMod(a, m-2, m);
}

// This function finds ncr using modular multiplicative inverse
static long ncr(long n, long r, long m) {
    if (n == r) return 1;
    if (r == 1) return n;

    long start = n - Math.max(r, n - r) + 1;

    long ret = 1;
    for (long i = start; i <= n; i++) ret = (ret * i) % m;

    long until = Math.min(r, n - r), denom = 1;
    for (long i = 1; i <= until; i++) denom = (denom * i)  % m;

    ret = (ret * modInverseFarmetsTheorem(denom, m)) % m;

    return ret;
}

Ответ 16

Вместо реализации n выберите k рекурсивно (что может привести к замедлению при больших числах), мы можем также использовать тот факт, что:

                n(n-1)(n-2)...(n-k+1)
  n choose k =  --------------------
                        k!

Нам все еще нужно вычислить k !, но это можно сделать гораздо быстрее, чем рекурсивный метод.

private static long choose(long n, long k) {
    long numerator = 1;
    long denominator = 1;

    for (long i = n; i >= (n - k + 1); i--) {
        numerator *= i;
    }

    for (long i = k; i >= 1; i--) {
        denominator *= i;
    }

    return (numerator / denominator);
}

Помните, что метод выбора выше предполагает, что ни n, ни k не являются отрицательными. Кроме того, длинный тип данных может переполниться для достаточно больших значений. Версия BigInteger должна использоваться, если результат соотв. числитель и/или знаменатель должны превышать 64 бита.

Ответ 17

public static long nCr(int n, int r) {
    long a = n;
    long b = r;
    long c = (n - r);

    for (int o = (int)a - 1; o > 0; o--) { a = a * o; }
    for (int o = (int)b - 1; o > 0; o--) { b = b * o; }
    for (int o = (int)c - 1; o > 0; o--) { c = c * o; }

    return (a / (b * c)); // n! / r! * (n - r)!
}

Отредактированный из ответа, я сделал несколько лет назад, где a, b и c были ints и целочисленным переполнением, что сделало этот метод критически непригодным. На самом деле это не лучше, чем с надежностью, но это лениво.

Это будет также кирпич, если значение перейдет на длинный предел... Не очень выполнимо, если вы не пытаетесь найти какое-то быстрое решение для школьного проекта или что-то в этом роде.