- 締切済み
全組み合わせの出力
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つの組み合わせを得る方法を 探しています。 ご存知の方がおられましたら、よろしくお願いします。
- ggable
- お礼率11% (9/76)
- Java
- 回答数1
- ありがとう数1
- みんなの回答 (1)
- 専門家の回答
みんなの回答
- _ranco_
- ベストアンサー率58% (126/214)
このプログラムは、奥村、山田といったアルゴリズムの大先生の作品を私が使いやすく改良したものです。配列のインデクスの組み合わせを出力しますから、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
- 重複順列nΠr≧順列nPr≧組合せnCr
にゃんこ先生といいます。 異なるn個の物からr個を取る。 この取るという動作には、重複を許すやり方と許さないやり方があります。 また、取った後の動作には、並べる方法と組合せにする方法があります。 全部で2*2=4つのバージョンが考えられます。 順列nPr=n!/(n-r)! 組合せnCr=n!/(n-r)!r! 重複順列nΠr=n^r 重複組合せnHr=n+r-1Cr=(n+r-1)!/(n-1)!r! ここで、一般に 重複順列nΠr≧順列nPr≧組合せnCr が成り立ちますが、nHrとの大小関係はどうなるのでしょうか? 二変数関数としての場合分けが必要とは思うのですがよくわかりません。
- 締切済み
- 数学・算数
- ランダウ量子力学 第二量子化(ボーズ粒子の場合)
小教程を読んでいるのですが… ボソンの系のN個粒子の波動関数 Ψ=(N_1!…/N!)^(1/2)ΣΨ_p1(ξ1)Ψ_p2(ξ2)…Ψ_pN(ξN) について、 f^(1)_a をa番目の粒子に関する物理量演算子とした上で、全ての粒子について対称な演算子F^(1)=Σf^(1)_a の行列要素の求め方がまったく載っていません。 <N_i, N_k-1 | F | N_i-1, N_k>=f _ik√NiNk として答えが載っていますが、 Ψ_1=(N_1!…N_i-1!/N!)^(1/2)ΣΨ_p1(ξ1)Ψ_p2(ξ2)…Ψ_pN(ξN) Ψ_2=(N_1!…N_k-1!/N!)^(1/2)ΣΨ_p1(ξ1)Ψ_p2(ξ2)…Ψ_pN(ξN) として ∫Ψ*_1FΨ_2 dξ を計算すればよいのでしょうか?? それでも、とても簡単とはいかなさそうなのですが… 指針やアドバイスだけで構わないので、どなたかご教授お願いできますか。 よろしくお願いします。
- ベストアンサー
- 物理学
- 組み合わせの漸化式について
組み合わせnCrは、漸化式nC(r-1) * (n-r+1)/rによって表されることを確かめようと、以下の計算をしたのですが、どうしても nC(r-1) * (n-r+1)になってしまいます。 nCr = n!/n!(n-r)! nC(r-1) = n!/n!(n-r+1)! nCr / nC(r-1) = n-r+1 漸化式が成り立つ理由をご教授お願いします。
- ベストアンサー
- 数学・算数
- 「組合せ」に出てくる文字の読み方について
nPr の「P」はPermutation nCr の「C」はCombination ここまでは教科書にものっていて知っているのですが… 「異なるn個のものから重複を許してr個とる組合せ」 これはよく問題集などで「nHr」とされています。 この「H」は一体なんと読むのですか? おそらくPやCのように、何かの頭文字であるとは思うのですが…。 ネットでも検索してみたのですが、検索ワードが悪いのか見つかりません。 知っている方がいらっしゃいましたら、ぜひ教えてください。
- ベストアンサー
- 数学・算数
- 素数と組み合わせの問題
Z会の問題なのですが、わからないところがあるので質問します。 nは素数pと自然数mを用いて、n=p^mと表される数であるとする。このとき、次の各問に答えよ。 (1)r=1,2,・・・,n-1のとき、nCrはpの倍数であることを示せ。 (2)nと(2^n)-1は互いに素であることを示せ。 nCrが自然数であることなら帰納法でなんとかなると思ったのですが、pの倍数になることがどうしても証明できません。どなたか教えてください。
- ベストアンサー
- 数学・算数
- 組み合わせ(数学)について
組み合わせの性質で、 nCr=nCr+1(+1はrと同サイズ) の場合、n=5、r=2で式が成立するのですが、rに1を足しているのに、なぜ、式が等しいのか分かりません。 教えて下さい。
- ベストアンサー
- 数学・算数
- nCr?二項定理?
お恥ずかしい話ですが、ご教授下さい。 問題「男子3人,女子5人の中から3人を選ぶとき,男子が少なくとも1人含まれる選び方は何通りあるか。 」という問題があるのですが、さっぱり分かりません。 まあ、回答結果は、答えをみればよいのですが、その解説がさっぱりです。 解説には「n 個の中から r 個取り出す組み合わせは、 nCr=n! / r!(n-r)! である」とありますが、 nCrってなんですか?高校で習いました?高校時代まじめに勉強していなかったおかげで、 さっぱり意味不明です。 nとrは変数ですよね?でもCって何ですか?それと「n!」って何ですか? そもそも「n!」は、「nエクスクラメーション」と読むのでしょうか? ついでに「nCr」は「えぬ、しー、あーる」と読むのでしょうか? 「n!」は、nをどうすればよいのでしょうか? 今更ながら基礎教育の大事さを身に染みて感じております。 是非、私程度のものでも分かる解説をお願い致します。
- ベストアンサー
- 数学・算数
- 組み合わせ
n個の集合からp個を取る組み合わせの総数を出力するプログラムなんですが nCp=n!/p!(n-p)!という式を使い #include<stdio.h> int kaijo(int m); int comb(int n,int p); int main(void) { int i,j; printf("n="); scanf("%d",&i); printf("p="); scanf("%d",&j); printf("comb(%d,%d)=%d\n",i,j,comb(i,j)); } int kaijo(int m) { if(m>0) return(m*kaijo(m-1)); else return 1; } int comb(int n,int p) { if(n>0) return((n*kaijo(n-1))/(p*kaijo(p-1)*(n-p)*kaijo(n-p-1))); else return 1; } と書いてみたのですがこれではnが大きいとC言語のint型で扱える最大値を超えてしまい正しい結果が出力されません。 そこでint型を使ったままでnやpが大きい場合でもある程度出力できるようにしたいのですがどう改良したらよいのでしょうか? おそらくnCp=n*(n-1)*・・・*(n-p+1)/p!という式を使うのですがよく分かりません。よろしくお願いします。
- 締切済み
- C・C++・C#