Java実装配列組合せ
基本概念
階乗
配列組合せを紹介する前にまず階乗を紹介します.多くの配列組合せの演算は階乗を使うからです.階乗の定義は、
配列組合せは組合せ学の最も基本的な概念である.配列とは,与えられた個数の要素から指定された個数の要素を取り出して並べ替えることである.コンビネーションとは、指定された数の要素から指定された数の要素のみを取り出し、ソートを考慮しないことを意味します.以下は整理された資料です.
名前
整列
コンポジット
定義#テイギ#
n個の異なる要素からm個の要素を取り出し、一定の順序で並べ替える
n個の異なる要素からm個の要素を取り出し、ソートを考慮しない
基本的な書き方
Amn A n m
Cmn C n m
計算式
Amn=n(n−1)...(n−m+1) A n m = n ( n − 1 ) . . . ( n − m + 1 ) , Amn=n!m! A n m = n ! m ! , Ann=n! A n n = n ! , A0n=1 A n 0 = 1
Cmn=n(n−1)...(n−m+1)m! C n m = n ( n − 1 ) . . . ( n − m + 1 ) m ! , Cmn=n!m!(n−m)! C n m = n ! m ! ( n − m ) ! , C0n=1 C n 0 = 1 , Cnn=1 C n n = 1
関係
Amn=Cmn×Amm A n m = C n m × A m m
Cmn=AmnAmm C n m = A n m A m m
せいしつ
Amn=n×Am−1n−1 A n m = n × A n − 1 m − 1
Cmn=Cmn−m C n m = C n − m m , Cmn+1=Cmn+Cm−1n C n + 1 m = C n m + C n m − 1
インプリメンテーションコード
階乗
配列の組合せ
階乗
配列組合せを紹介する前にまず階乗を紹介します.多くの配列組合せの演算は階乗を使うからです.階乗の定義は、
(factorial) , 0 1。 n n!。
、すなわちn!=1×2×3×...×n
である.階乗も再帰的に定義できます:0!=1,n!=(n-1)!×n
配列の組合せ配列組合せは組合せ学の最も基本的な概念である.配列とは,与えられた個数の要素から指定された個数の要素を取り出して並べ替えることである.コンビネーションとは、指定された数の要素から指定された数の要素のみを取り出し、ソートを考慮しないことを意味します.以下は整理された資料です.
名前
整列
コンポジット
定義#テイギ#
n個の異なる要素からm個の要素を取り出し、一定の順序で並べ替える
n個の異なる要素からm個の要素を取り出し、ソートを考慮しない
基本的な書き方
Amn A n m
Cmn C n m
計算式
Amn=n(n−1)...(n−m+1) A n m = n ( n − 1 ) . . . ( n − m + 1 ) , Amn=n!m! A n m = n ! m ! , Ann=n! A n n = n ! , A0n=1 A n 0 = 1
Cmn=n(n−1)...(n−m+1)m! C n m = n ( n − 1 ) . . . ( n − m + 1 ) m ! , Cmn=n!m!(n−m)! C n m = n ! m ! ( n − m ) ! , C0n=1 C n 0 = 1 , Cnn=1 C n n = 1
関係
Amn=Cmn×Amm A n m = C n m × A m m
Cmn=AmnAmm C n m = A n m A m m
せいしつ
Amn=n×Am−1n−1 A n m = n × A n − 1 m − 1
Cmn=Cmn−m C n m = C n − m m , Cmn+1=Cmn+Cm−1n C n + 1 m = C n m + C n m − 1
インプリメンテーションコード
階乗
/**
*
* @param n
* @return
*/
public int factorial(int n){
if(n==0){
return 1;
}else{
int result=1;
for(int i=1;i<=n;i++){
result*=i;
}
return result;
}
}
/**
*
* @param n
* @return
*/
public int factorial(int n){
if(n==0){
return 1;
}else{
return n*factorial(n-1);
}
}
配列の組合せ
/**
*
* @param m
* @param n
* @return
*/
public int permutation(int m,int n){
if(n==0){
return 1;
}
int result=1;
for(int k=n;k>=n-m+1;k--){
result*=k;
}
return result;
}
/**
*
* @param m
* @param n
* @return
*/
public int combination(int m,int n){
return permutation(m,n)/permutation(m,m);
}