组合 'N 选择 R'在java数学中？

Question

java库中是否有内置方法可以为任何N，R计算“N选择R”？

Answer 1

公式

实际上，计算N 选择 K 非常容易，甚至无需计算阶乘。

我们知道，(N 选择 K) 的公式为：

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

因此，(N 选择 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 选择 K) >(N select 0) 是：

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

所以这给了我们一个简单的起点，使用上面的公式，我们可以找到任何 K > 的 (N select 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³⁸。

---

参考文献

• 维基百科/二项式系数
• 维基百科/帕斯卡三角形
• 维基百科/组合

Answer 2

apache-commons“数学”支持这一点
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

我只是想计算不同牌组大小的 2 张牌组合的数量...

无需导入外部库 - 根据组合的定义，n 卡将是 n* (n-1)/2

额外问题：这个相同的公式计算前 n-1 整数的总和 - 你明白为什么它们是相同的？ :)

Answer 5

二项式系数，位于 Commons Math< /a>

返回二项式系数的精确表示，“n 选择 k”，即可以从 n 元素集中选择的 k 元素子集的数量。

Answer 6

N！/（（R！）（NR）！）

这个公式中有很多东西可以取消，所以阶乘通常没有问题。假设 R > (NR) 然后取消 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
}

以 1 开始除法很重要，尽管这似乎是多余的。但让我们举个例子：

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 7

其数学公式是：

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

从那里应该不难算出来:)

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

guava 具有 IntMath#binomial(int, int) ，LongMath#binomial(int, int) 和 BigIntegerMath#binomial(int, int)。

Answer 10

ArithmeticUtils.factorial 现在显然已被弃用。请尝试CombinatoricsUtils.binomialCoefficientDouble(n,r)

Answer 11

与番石榴版本类似，有一个 BigIntegerMath 类 此处，由 Richard J. Mathar 称为org.nevec.rjm，这是类的包。

他们的实现为二项式方法提供了两个签名：int,int 和 BigInteger,BigInteger。

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

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

Answer 14

根据公式：n!/ ((nk)! * k!)
如果我们简单地计算分子和分母，许多计算将被浪费，并且可能“int”，“float”甚至“BigInteger”的范围可以填充。
因此，为了克服这种情况，我们可以在乘以值之前取消这些内容。

假设n=6，k=3

=> 6*5*4*3*2*1 / ((3*2) * (3*2))

假设如果我们乘以分子，则可以填充范围。更好的选择是在将值相乘之前将其取消。

在这种情况下——>
如果我们取消一切，我们只剩下：
(2*5*2)

乘以这些值要容易得多，并且需要更少的计算。

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

下面提到的代码对于以下数字将“有效”工作：

1. n == k
2. k < n
3. k == 0
4. n 和 k 之间的差异太大，例如。
   n=1000, k=2
5. k = n/2 (最难)
6. 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++;
    }
}

Answer 15

已经有很多解决方案提交了。

1. 某些解决方案未考虑整数溢出。

2. 某些解决方案在给定 n 和 r 的情况下计算所有可能的 nCr。
   结果是需要更多的时间和空间。

大多数情况下我们需要直接计算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;
}

Answer 16

我们还可以利用以下事实：

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

我们仍然需要计算 k！，而不是递归地实现 n 选择 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);
}

请注意，上面的 select 方法假设 n 和 k 都不为负数。此外，长数据类型可能会因足够大的值而溢出。如果结果分别应使用 BigInteger 版本。分子和/或分母预计超过 64 位。

Answer 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 是整数，整数溢出使该方法严重无法使用。就可靠性而言，这个并没有真正更好，但它很懒。

如果值超过多头的限制，这也会变砖......除非您试图为学校项目或其他东西找到一些快速解决方案，否则不太可行。