combination enumerator in java

 
/*
  Combination.java
 
  generates all combinations of C(n,m) for n >= m >= 0
 
Usage: java Combination n m
 
Sample Output:
> java Combination 5 2
--- recursive one-shot generation ---
k=1 ---> {1, 2}
k=2 ---> {1, 3}
k=3 ---> {1, 4}
k=4 ---> {1, 5}
k=5 ---> {2, 3}
k=6 ---> {2, 4}
k=7 ---> {2, 5}
k=8 ---> {3, 4}
k=9 ---> {3, 5}
k=10 ---> {4, 5}
--- nonrecursive item-wise generation ---
k=1 ---> {1, 2}
k=2 ---> {1, 3}
k=3 ---> {1, 4}
k=4 ---> {1, 5}
k=5 ---> {2, 3}
k=6 ---> {2, 4}
k=7 ---> {2, 5}
k=8 ---> {3, 4}
k=9 ---> {3, 5}
k=10 ---> {4, 5}
 
--- Combination.java ---
*/
import java.util.Vector;
import java.util.Enumeration;
 
// class for generating all m-item selection sets from an n-item population set
public class Combination {
    Vector < Object > n_set; // population set of objects for combination
    int n; // population size, n >= m >= 0
    int m; // selection size
 
    // constructor for combination object
    //   n_set: population set of objects for combination
    //   m:  selection size
    public Combination(Vector < Object > n_set, int m) {
        this.n_set = n_set;
        this.n = n_set.size();
        this.m = m;
 
        if (n < m || m < 0 || n <= 0) {
            System.err.printf("combine(n=%d, m=%d): illegal n,m!\n", n, m);
        }
    }
 
    // generate integer objects from 1 to n
    public static Vector < Object > generateIntegers(int n) {
        Vector < Object > set = new Vector < Object > ();
        for (int i = 1; i <= n; i++) set.add(i);
        return set;
    }
 
    // generate integer objects from 1 to n
    public static Vector < Vector < Object >> cnm(int n, int m) {
        Vector < Object > set = generateIntegers(n);
        Combination c = new Combination(set, m);
        Vector < Vector < Object >> set_list = c.cnm();
        return set_list;
    }
 
    // generate all m-item selection sets from population set n_set
    //   returns set of all m-item selection sets from population set n_set
    Vector < Vector < Object >> cnm() {
        return cnm(n_set, m);
    }
 
    // recursive generation of all m-item selection sets from population set n_set
    //   n_set: population set
    //   m: selection size
    //   returns set of all m-item selection sets from population set n_set
    Vector < Vector < Object >> cnm(Vector < Object > n_set, int m) {
        Vector < Object > set = new Vector < Object > ();
        Vector < Vector < Object >> result_list = new Vector < Vector < Object >> ();
 
        int n = n_set.size();
        if (n < m || m < 0 || n <= 0) {
            System.err.printf("combine(n=%d, m=%d): illegal n,m!\n", n, m);
            return null;
        }
 
        // base case 1: m=0
        if (m == 0) {
            result_list.add(set);
            return result_list;
        }
        // base case 2: m=n
        else if (m == n) {
            result_list.add(n_set);
            return result_list;
        }
 
        // recursive call:
        Vector < Vector < Object >> result_with_first = new Vector < Vector < Object >> ();
        Vector < Vector < Object >> result_without_first = new Vector < Vector < Object >> ();
 
        Vector < Object > n_minus_1_set = new Vector < Object > (n_set);
        n_minus_1_set.removeElementAt(0);
        result_with_first = cnm(n_minus_1_set, m - 1);
        result_without_first = cnm(n_minus_1_set, m);
        for (Vector < Object > comb: result_with_first) {
            comb.insertElementAt(n_set.firstElement(), 0);
        }
 
        result_list.addAll(result_with_first);
        result_list.addAll(result_without_first);
 
        return result_list;
    }
 
    // get enumerator for all m-item selection sets from population set n_set
    Enumeration < Vector < Object >> enumeration() {
        if (n < m || m < 0 || n <= 0) {
            System.err.printf("combine(n=%d, m=%d): illegal n,m!\n", n, m);
            return null;
        }
        return new Enumerator();
    }
 
    // inner class of Combination class
    // enumerator for non-recursive generation of all m-item selection sets from population set n_set
    public class Enumerator implements Enumeration < Vector < Object >> {
        int index[];
        int index_upper[];
        boolean carry;
        boolean hasMore;
        Vector < Object > element;
 
        // constructor for m-item selection set enumerator
        public Enumerator() {
            element = new Vector < Object > ();
            hasMore = true;
 
            //carry = new boolean[m];
            index = new int[m];
            index_upper = new int[m];
            for (int i = 0; i <= m - 1; i++) {
                index[i] = i;
                index_upper[i] = n - m + i;
            }
        }
 
        public boolean hasMoreElements() {
            return hasMore;
        }
 
        public Vector < Object > nextElement() {
            int i;
            element.clear();
            for (i = 0; i <= m - 1; i++) {
                element.add(n_set.get(index[i]));
            }
 
            // point to next index
            carry = false;
            for (i = m - 1; i >= 0; i--) {
                int digit = index[i];
                if (digit + 1 <= index_upper[i]) {
                    index[i]++;
 
                    if (carry == true)
                        while (i + 1 <= m - 1) {
                            index[i + 1] = index[i] + 1;
                            i++;
                        }
                    break;
                } else
                    carry = true;
            }
 
            if (i < 0) hasMore = false;
            return element;
        } // end of nextElement
    } // end of enumerator class
 
    // main program for test
    public static void main(String args[]) {
        int n = 5;
        int m = 2;
 
        if (args.length == 2) {
            n = Integer.parseInt(args[0]);
            m = Integer.parseInt(args[1]);
        }
 
        System.out.println("--- recursive one-shot generation ---");
 
        Vector < Vector < Object >> set_list = Combination.cnm(n, m);
        int k = 1;
        for (Vector < Object > set: set_list) {
            System.out.printf("k=%d ---> {", k);
            boolean first = true;
            for (Object o: set) {
                if (first) first = false;
                else System.out.print(", ");
                System.out.print((Integer) o);
            }
            System.out.println("}");
            k++;
        }
 
        System.out.println("--- nonrecursive item-wise generation ---");
 
        Vector < Object > set = Combination.generateIntegers(n);
        Combination c = new Combination(set, m);
        Enumeration < Vector < Object >> e = c.enumeration();
        k = 1;
        while (e.hasMoreElements()) {
            set = e.nextElement();
            System.out.printf("k=%d ---> {", k);
            boolean first = true;
            for (Object o: set) {
                if (first) first = false;
                else System.out.print(", ");
                System.out.print((Integer) o);
            }
            System.out.println("}");
            k++;
        }
    }
}

註: 本程式使用 GitHub JavaScript code prettifier 工具標示顏色。其方法如下:
   1.參考 [Blogger] 如何在 Blogger 顯示程式碼 - Google Code Prettify
     於【Blogger 版面配置 HTML/JavaScript小工具】安裝如下套件
       <script src="https://cdn.jsdelivr.net/gh/google/code-prettify@master/loader/run_prettify.js"></script>
   2.文章編輯再以HTML模式為程式包上如下標籤。
       <code class="prettyprint lang-java linenums"> ... </code>