N、Rに対して「N choose R」を計算できるメソッドがJavaライブラリに組み込まれていますか?
88478 次
17 に答える
106
式
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 > 0KK
簡単なパスカルの三角形
上記をまとめると、パスカルの三角形は次のように簡単に生成できます。
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 38を選択しています。
参考文献
于 2010-05-28T14:34:06.940 に答える
49
apache-commons の「Math」は、 org.apache.commons.math4.util.CombinatoricsUtilsでこれをサポートしています。
于 2010-02-04T16:06:14.053 に答える
24
再帰的な定義は、小さな値に対してうまく機能する非常に単純な choose 関数を提供します。このメソッドを頻繁に、または大きな値で実行する予定がある場合は、メモ化するのに費用がかかりますが、それ以外の場合は問題なく機能します。
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);
}
この関数の実行時間を改善することは、読者の課題として残されています:)
于 2010-02-10T09:01:58.327 に答える
15
デッキサイズが異なる2枚のカードの組み合わせの数を計算しようとしています...
外部ライブラリをインポートする必要はありません - 組み合わせの定義からn、n*(n-1)/2
おまけの質問: この同じ数式は、最初の整数の合計を計算n-1します。なぜそれらが同じなのか分かりますか? :)
于 2010-02-05T14:48:12.313 に答える
4
N!/((R!)(NR)!)
この式で取り消すことができるものはたくさんあるので、通常、階乗は問題ありません。R > (NR) で N!/R! をキャンセルするとしましょう。to (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 のままにしておくと、乗算の第 1 オペランドまたは第 2 オペランドが偶数になるため、そうしないことが保証されます。
同じ理由で、使用しませんr *= (m/d)。
全体を次のように修正できます
r := max(R, N-R)+1
for (m := r+1,d := 2; m <= N; m++, d++ ) {
r *= m
r /= d
}
于 2010-05-28T12:07:51.213 に答える
4
于 2010-02-04T16:06:38.527 に答える
2
これの数式は次のとおりです。
N!/((R!)(N-R)!)
そこからそれを理解するのは難しくないはずです:)
于 2010-02-04T16:05:51.400 に答える
2
次のルーチンは、再帰的な定義とメモ化を使用して、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;
}
于 2011-01-19T04:25:56.780 に答える
1
guavaにはIntMath#binomial(int, int)、LongMath#binomial(int, int)、BigIntegerMath#binomial(int, int) があります。
于 2014-02-09T21:59:39.227 に答える
1
ArithmeticUtils.factorial現在は明らかに廃止されています。してみてください CombinatoricsUtils.binomialCoefficientDouble(n,r)
于 2015-04-27T11:44:31.077 に答える
0
guava バージョンと同様に、 Richard J. Mathar によって org.nevec.rjm と呼ばれる BigIntegerMath クラスがここにあり、これはクラスのパッケージです。
それらの実装は、二項メソッドに 2 つのシグネチャを提供します: int,int と BigInteger,BigInteger です。
于 2015-08-28T17:33:14.537 に答える
0
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);
}
于 2016-12-04T07:45:23.833 に答える
-1
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 は int であり、整数オーバーフローによりメソッドが非常に使用できなくなりました。これは信頼性の点でそれほど優れているわけではありませんが、怠け者です。
値が長い限界を超えた場合、これも同様にブリックになります...学校のプロジェクトなどのための迅速な解決策を見つけようとしている場合を除き、あまり実現可能ではありません.
于 2015-07-30T03:30:26.843 に答える