자바 수학에서 조합 'N choose R'?
모든 N, R에 대해 'N choose R'을 계산할 수있는 Java 라이브러리에 내장 된 메소드가 있습니까?
apache-commons "Math"는 org.apache.commons.math4.util.CombinatoricsUtils 에서이를 지원합니다.
공식
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분열.
이지 파스칼의 삼각형
위의 내용을 종합하면 다음과 같이 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 38을 선택 합니다.
참고 문헌
재귀 적 정의는 당신이 아주 간단 작은 값에 대한 벌금을 작동 기능을 선택할 수 있습니다. 이 방법을 많이 또는 큰 값으로 실행할 계획이라면 메모하는 데 비용이 들지만 그렇지 않으면 잘 작동합니다.
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);
}
이 기능의 실행 시간을 개선하는 것은 독자 를위한 연습으로 남겨집니다. :)
덱 크기가 다른 2 개의 카드 조합 수를 계산하려고합니다.
조합의 정의에서 외부 라이브러리를 가져올 필요 n가 없습니다.n*(n-1)/2
보너스 질문 : 이 동일한 공식은 첫 번째 n-1정수 의 합계를 계산합니다. 왜 같은지 아십니까? :)
이에 대한 수학적 공식은 다음과 같습니다.
N!/((R!)(N-R)!)
거기에서 그것을 알아내는 것이 어렵지 않아야합니다 :)
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
}
불필요한 것처럼 보이지만 분할을 하나로 시작하는 것이 중요합니다. 그러나 예를 들어 보겠습니다.
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
}
binomialCoefficient, Commons Math에서
다음 루틴은 재귀 적 정의와 메모를 사용하여 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;
}
구아바 에는 IntMath # binomial (int, int) , LongMath # binomial (int, int) 및 BigIntegerMath # binomial (int, int) 있습니다.
ArithmeticUtils.factorial지금은 분명히 사용되지 않습니다. 시도하십시오CombinatoricsUtils.binomialCoefficientDouble(n,r)
구아바 버전과 유사하게 여기 에 Richard J. Mathar가 클래스 패키지 인 org.nevec.rjm이라고 하는 BigIntegerMath 클래스 가 있습니다.
이들의 구현은 이항 메서드에 대해 int, int 및 BigInteger, BigInteger의 두 가지 서명을 제공합니다.
해시 맵을 사용하여 @ 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);
}
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);
}
공식에 따라 : n! / ((nk)! * k!) 단순히 분자와 분모를 계산하면 많은 계산이 낭비되고 아마도 "int", "float"또는 "BigInteger"의 범위가 채워질 수 있습니다. 따라서이 시나리오를 극복하기 위해 값을 곱하기 전에 상황을 취소 할 수 있습니다.
n = 6, k = 3이라고 가정합니다.
=> 6 * 5 * 4 * 3 * 2 * 1 / ((3 * 2) * (3 * 2))
분자를 곱하면 범위가 채워질 수 있다고 가정합니다. 더 나은 옵션은 값을 곱하기 전에 취소하는 것입니다.
이 경우-> 방금 남은 모든 것을 취소하면 : (2 * 5 * 2)
이 값을 곱하는 것은 훨씬 쉽고 계산이 덜 필요합니다.
================================================ ====
아래 언급 된 코드는 다음과 같은 숫자에 대해 "효율적으로"작동합니다.
- n == k
- k <n
- 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++;
}
}
이미 제출 된 많은 솔루션이 있습니다.
일부 솔루션은 정수 오버플로를 고려하지 않았습니다.
일부 솔루션은 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;
}
Instead of implementing n choose k recursively (which can get slow with large numbers), we can also make use of the fact that:
n(n-1)(n-2)...(n-k+1)
n choose k = --------------------
k!
We still need to calculate k!, but this can be done much faster than the recursive method.
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);
}
Be aware that the choose method above assumes that neither n nor k is negative. Also, the long data type can overflow for large enough values. A BigInteger version should be used if the result resp. numerator and/or denominator are expected to exceed 64 bits.
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)!
}
Edited from answer I made few years back, where a, b, and c were ints and integer overflow made the method critically unusable. This one is not really any better in terms of reliability, but it's lazy.
This will brick as well, if the value goes over long's limit... Not very feasible unless you're trying to find some quick solution for a school project or something.
ReferenceURL : https://stackoverflow.com/questions/2201113/combinatoric-n-choose-r-in-java-math
'Programing' 카테고리의 다른 글
| 문자열에서 숫자 추출-StringUtils Java (0) | 2020.12.28 |
|---|---|
| Mongodb : 127.0.0.1:27017에 연결하지 못했습니다. 이유 : errno : 10061 (0) | 2020.12.28 |
| Android에서 그라디언트가있는 텍스트 (0) | 2020.12.28 |
| iOS 앱의 첫 실행 감지 (0) | 2020.12.28 |
| WPF WebBrowser 컨트롤-스크립트 오류를 억제하는 방법? (0) | 2020.12.28 |