全組み合わせの出力

質問

ｎ個の中ならｒ個を選ぶ、重複を許さない組み合わせは、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に入っているｎ個の
要素に対して、ｒとｉを指定してその１つの組み合わせを得る方法を
探しています。

ご存知の方がおられましたら、よろしくお願いします。

回答No.1

_ranco_

このプログラムは、奥村、山田といったアルゴリズムの大先生の作品を私が使いやすく改良したものです。配列のインデクスの組み合わせを出力しますから、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;
　}
}
---------------------------------------------