n個の中ならr個を選ぶ、重複を許さない組み合わせは、nCr通りありますが、
これを順番に出力するにはどのようにすればよいでしょうか?
要素を{p1,p2,p3,p4,p5,...,pn}とするとき、例えばr=3ならば
f(i=1)={p1,p2,p3},f(i=2)={p1,p2,p4},f(i=3)={p1,p2,p3},...
f(i=n-2)={p1,p2,pn},f(i=n-1)={p1,p3,p4},f(i=n)={p1,p3,p5},
f(i=n+1)={p1,p3,p6},f(i=n+2)={p1,p3,p7},f(i=n+3)={p1,p3,p8},...
f(i=2n-3)={p1,p4,p5},f(i=2n-2)={p1,p4,p6},...
f(i=nCr)={pn-2,pn-1,pn}
という風になるかと思いますが、その規則性がわかりません。
上記規則に従う必要は無いのですが、java.util.Listに入っているn個の
要素に対して、rとiを指定してその1つの組み合わせを得る方法を
探しています。
ご存知の方がおられましたら、よろしくお願いします。
A 回答 (1件)
- 最新から表示
- 回答順に表示
No.1
- 回答日時:
このプログラムは、奥村、山田といったアルゴリズムの大先生の作品を私が使いやすく改良したものです。
配列のインデクスの組み合わせを出力しますから、java.util.Collection系のindexに対してももちろん使えます。------------------------------------------------------
import java.util.*;
public class IndicesCombis implements Enumeration<int[]>{
private int N, K, numComb;
private BitSet X;
private int[] indices;
private int[][] results;
public IndicesCombis(int n, int k){
this.indices = indices;
N = n;
K = k;
indices = new int[n];
for (int i = 0; i < n; ++i){
indices[i] = i;
}
X = new BitSet(N + 1);
for (int i = 0; i < k; ++i){
X.set(i);
}
results = getIndexCombinations();
}
public int getNumComb(){ //number of generated combinations
return numComb;
}
public int[][] getResults(){ //return combinations as array of indices set
return results;
}
public int[][] getIndexCombinations(){
int[][] result;
int[] cmb; //each combination
ArrayList<IntArray> combis;
//ArrayList of IntArray is nothing but an array of array
combis = new ArrayList<IntArray>();
int count = 0;
while(hasMoreElements()) {
cmb = nextElement();
Arrays.sort(cmb);
combis.add(new IntArray(cmb));
count++;
}
numComb = count;
Collections.sort(combis);
result = new int[numComb][]; //List of array -> array of array conversion
count = 0;
for (IntArray a: combis){
result[count++] = a.iarray;
}
return result;
}
public boolean hasMoreElements() {
return ! X.get(N);
}
private int findOne(BitSet bs) {
int len = bs.size();
for(int i = 0; i <= N; ++i) {
if (bs.get(i)){
return i;
}
}
return -1;
}
private int incr(BitSet bs, int n) {
int a = 0;
for(;;) {
if (bs.get(n)){
bs.clear(n); n++; a++;
}
else{
bs.set(n); break;
}
}
return a;
}
public int[] nextElement() {
int k = 0;
int[] combi = new int[K];
for (int i = 0; i <= N; i++){
if(X.get(i)){
combi[k++] = indices[i];
}
}
int u = incr(X, findOne(X)) - 1;
for(int i = 0; i < u; ++i){
X.set(i);
}
return combi;
}
// main() for test
public static void main(String[] args) {
int[][] combinations;
int[] cmb;
int n, k;
if (args.length < 2){ // 4 from 10
n = 10;
k = 4;
}
else{
n = Integer.parseInt(args[0]);
k = Integer.parseInt(args[1]);
}
System.out.println("N=" + n);
System.out.println("K=" + k);
IndicesCombis icmb = new IndicesCombis(n, k);
combinations = icmb.getResults();
for (int i = 0; i < combinations.length; ++i){
cmb = combinations[i];
print(cmb);
}
System.out.println("count = " + icmb.getNumComb());
}
static void print(int[] ar){ //this method was used for debugging
for (int i = 0; i < ar.length; ++i){
System.out.print(ar[i] + " ");
}
System.out.println();
}
}
class IntArray implements Comparable<IntArray>{
public int[] iarray;
public int length;
public IntArray(int[] a){
iarray = a;
length = iarray.length;
}
public int compareTo(IntArray other){ //for sorting
int diff = 0;
for (int i = 0; i < length && i < other.length; ++i){
diff = iarray[i] - other.iarray[i];
if (diff != 0){
break;
}
}
if (diff == 0 && length != other.length){
diff = length > other.length ? 1 : -1;
}
return diff;
}
public String toString(){
String s = "";
for (int n: iarray){
s += n + " ";
}
return s;
}
}
---------------------------------------------
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
似たような質問が見つかりました
- その他(プログラミング・Web制作) Pythonでの不均一なサイコロをつくるプログラミングがわかりません 4 2022/06/07 13:10
- 数学 確率の最大値を求める方法について 確率 Pn<P(n+1)⇄Pn/P(n+1)<1のときと Pn>P 2 2022/07/29 20:15
- 経済学 経済学のベルトラン均衡について教えてください。 4 2022/11/23 16:37
- Java java 引数 戻り値のあるメソッド 3 2023/02/12 06:23
- 数学 環論の素元について 6 2022/05/09 04:04
- 統計学 こんな問題を使って教育するのは、文科省の方針ですか。 3 2022/06/17 09:14
- 数学 写真の数学の問題です。 ①(1)の場合分けの方法はどうやったら思いつけますか?(その考えにたどり着く 1 2023/04/22 16:26
- 数学 A君とB君はコインを1枚ずつ投げ、2枚とも表、あるいは2枚とも裏が出れば、投げた2枚をA君がもらい、 3 2023/02/05 12:19
- 数学 数学A 確率 白玉5個、赤玉n個の入っている袋がある。 この袋の中から、2個の玉をとりだすとき、白玉 4 2023/04/22 15:18
- Visual Basic(VBA) エクセルのマクロについて教えてください。 1 2022/10/11 12:55
このQ&Aを見た人はこんなQ&Aも見ています
関連するカテゴリからQ&Aを探す
このQ&Aを見た人がよく見るQ&A
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
C++からC#のdllを参照する際、...
-
再帰・組み合わせ
-
C#で実行時にメソッドの返り値...
-
javaでcsvファイル読込時の改行...
-
【C#】クラスのメンバ変数のア...
-
JAVA エラー 式の開始が不正で...
-
(Swing)JTextFieldを半角のみ入...
-
javaについての質問です
-
intが負の時に投げる例外はあり...
-
java spring でエラーが出て困...
-
アンマネージDLLで、ダイアログ...
-
DataSet(DataTable)の使い方
-
C#のプログラムでエラーが…
-
classを使って座標軸を求めるコ...
-
JAVAでCの関数ポインタのような...
-
JUnit4のアノテーションについて
-
「配列定数は、イニシャライザ...
-
コード中の謎のエラー
-
C#でfirefoxのウインドウを移動...
-
メンバ関数のconst
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
式の型は配列型で int に解決済...
-
「配列定数は、イニシャライザ...
-
intが負の時に投げる例外はあり...
-
javaでカレンダー作成
-
メインが含まれていません
-
JAVA エラー 式の開始が不正で...
-
Javaで電卓を作りたい
-
javaでcsvファイル読込時の改行...
-
(Swing)JTextFieldを半角のみ入...
-
javaのエラーの意味がわかりま...
-
「WorkImage.getGraphics()」が...
-
初心者ですが、今javaで簡単な...
-
sin曲線とcos曲線を描くプログ...
-
java spring でエラーが出て困...
-
SwingでJtableのヘッダ行が表示...
-
Java 初心者 int型の取り扱い方
-
DataSet(DataTable)の使い方
-
JAVAでCの関数ポインタのような...
-
6桁の数字を重複なしでランダム...
-
JAVA EOFの検出 (条件文で「...
おすすめ情報