全ての組み合わせを得る．タグ付けから類似度を求めるとき用

Comb.java

package sandbox;

import java.math.BigInteger;

/**
 *
 * @author udonchan
 */

public class Comb {

    private int[] a;
    private int n;
    private int r;
    private BigInteger numLeft;
    private BigInteger total;


    public Comb(int n, int r) {
        if (r > n) {
            throw new IllegalArgumentException();
        }
        if (n < 1) {
            throw new IllegalArgumentException();
        }
        this.n = n;
        this.r = r;
        a = new int[r];
        BigInteger nFact = getFactorial(n);
        BigInteger rFact = getFactorial(r);
        BigInteger nminusrFact = getFactorial(n - r);
        total = nFact.divide(rFact.multiply(nminusrFact));
        reset();
    }

    public void reset() {
        for (int i = 0; i < a.length; i++) {
            a[i] = i;
        }
        numLeft = new BigInteger(total.toString());
    }

    public BigInteger getNumLeft() {
        return numLeft;
    }

    public boolean hasMore() {
        return numLeft.compareTo(BigInteger.ZERO) == 1;
    }

    public BigInteger getTotal() {
        return total;
    }

    private static BigInteger getFactorial(int n) {
        BigInteger fact = BigInteger.ONE;
        for (int i = n; i > 1; i--) {
            fact = fact.multiply(new BigInteger(Integer.toString(i)));
        }
        return fact;
    }

    public int[] getNext() {
        if (numLeft.equals(total)) {
            numLeft = numLeft.subtract(BigInteger.ONE);
            return a;
        }
        int i = r - 1;
        while (a[i] == n - r + i) {
            i--;
        }
        a[i] = a[i] + 1;
        for (int j = i + 1; j < r; j++) {
            a[j] = a[i] + j - i;
        }
        numLeft = numLeft.subtract(BigInteger.ONE);
        return a;
    }

    // test
    public static void main(String args[]) {
        String[] elements = {"a", "b", "c", "d", "e", "f", "g"};

        int[] indices;
        StringBuffer combination;
        for (int j = 1; j <= elements.length; j++) {
            Comb x = new Comb(elements.length, j);
            while (x.hasMore()) {
                combination = new StringBuffer();
                indices = x.getNext();
                for (int i = 0; i < indices.length; i++) {
                    combination.append(elements[indices[i]] + " ");
                }
                System.out.println(combination.toString());
            }
        }
    }
/* result 
a 
b 
c 
d 
e 
f 
g 
a b 
a c 
a d 
a e 
a f 
a g 
b c 
b d 
b e 
b f 
b g 
c d 
c e 
c f 
c g 
d e 
d f 
d g 
e f 
e g 
f g 
a b c 
a b d 
a b e 
a b f 
a b g 
a c d 
a c e 
a c f 
a c g 
a d e 
a d f 
a d g 
a e f 
a e g 
a f g 
b c d 
b c e 
b c f 
b c g 
b d e 
b d f 
b d g 
b e f 
b e g 
b f g 
c d e 
c d f 
c d g 
c e f 
c e g 
c f g 
d e f 
d e g 
d f g 
e f g 
a b c d 
a b c e 
a b c f 
a b c g 
a b d e 
a b d f 
a b d g 
a b e f 
a b e g 
a b f g 
a c d e 
a c d f 
a c d g 
a c e f 
a c e g 
a c f g 
a d e f 
a d e g 
a d f g 
a e f g 
b c d e 
b c d f 
b c d g 
b c e f 
b c e g 
b c f g 
b d e f 
b d e g 
b d f g 
b e f g 
c d e f 
c d e g 
c d f g 
c e f g 
d e f g 
a b c d e 
a b c d f 
a b c d g 
a b c e f 
a b c e g 
a b c f g 
a b d e f 
a b d e g 
a b d f g 
a b e f g 
a c d e f 
a c d e g 
a c d f g 
a c e f g 
a d e f g 
b c d e f 
b c d e g 
b c d f g 
b c e f g 
b d e f g 
c d e f g 
a b c d e f 
a b c d e g 
a b c d f g 
a b c e f g 
a b d e f g 
a c d e f g 
b c d e f g 
a b c d e f g 
*/
}