Algorithm Combinations for Java Programming

Combinations. Write a program Combinations.java that takes one command-line argument n and prints out all 2^n combinations of any size. A combination is a subset of the n elements, independent of order. As an example, when n = 3 you should get the following output.

a ab abc ac b bc c

 Combinations.java

/*************************************************************************

 *  Compilation:  javac Combinations.java

 *  Execution:    java Combinations N

 *  

 *  Enumerates all subsets of N elements using recursion.

 *  Uses some String library functions.

 *

 *  Both functions (comb1 and comb2) print them in alphabetical

 *  order; comb2 does not include the empty subset.

 *

 *  % java Combinations 3

 *  

 *  a

 *  ab

 *  abc

 *  ac

 *  b

 *  bc

 *  c

 *

 *  a

 *  ab

 *  abc

 *  ac

 *  b

 *  bc

 *  c

 *

 *  Remark: this is, perhaps, easier by counting from 0 to 2^N - 1 by 1

 *  and looking at the bit representation of the counter. However, this

 *  recursive approach generalizes easily, e.g., if you want to print

 *  out all combinations of size k.

 *

 *************************************************************************/

public class Combinations {

    // print all subsets of the characters in s

    public static void comb1(String s) { comb1("", s); }

    // print all subsets of the remaining elements, with given prefix 

    private static void comb1(String prefix, String s) {

        if (s.length() > 0) {

            System.out.println(prefix + s.charAt(0));

            comb1(prefix + s.charAt(0), s.substring(1));

            comb1(prefix,               s.substring(1));

        }

    }  

    // alternate implementation

    public static void comb2(String s) { comb2("", s); }

    private static void comb2(String prefix, String s) {

        System.out.println(prefix);

        for (int i = 0; i < s.length(); i++)

            comb2(prefix + s.charAt(i), s.substring(i + 1));

    }  

    // read in N from command line, and print all subsets among N elements

    public static void main(String[] args) {

       int N = Integer.parseInt(args[0]);

       String alphabet = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";

       String elements = alphabet.substring(0, N);

       // using first implementation

       comb1(elements);

       System.out.println();

       // using second implementation

       comb2(elements);

       System.out.println();

    }

}

Copyright © 2000–2010, Robert Sedgewick and Kevin Wayne.
Last updated: Wed Feb 9 09:05:37 EST 2011.

Note that the first element printed is the empty string (subset of size 0). Combinations of size k. Modify Combinations.java to CombinationsK.java so that it takes two command-line arguments n and k, and prints out all C(n, k) = n! / (k! * (n-k)!) combinations of size k. For example, when n = 5 and k = 3 you should get the following output.

abc abd abe acd ace ade bcd bce bde cde

CombinationsK.java

/*************************************************************************
 *  Compilation:  javac CombinationsK.java
 *  Execution:    java CombinationsK N k 
 *  
 *  Enumerates all subsets of size k on N elements in lexicographic order.
 *  Two different solutions. Uses some String library functions. 
 *
 *  % java CombinationsK 5 3
 *  abc
 *  abd
 *  abe
 *  acd
 *  ace
 *  ade
 *  bcd
 *  bce
 *  bde
 *  cde
 *
 *************************************************************************/

public class CombinationsK {

    // print all subsets that take k of the remaining elements, with given prefix 
    public  static void comb1(String s, int k) { comb1(s, "", k); }
    private static void comb1(String s, String prefix, int k) {
        if (s.length() < k) return;
        else if (k == 0) System.out.println(prefix);
        else {
            comb1(s.substring(1), prefix + s.charAt(0), k-1);
            comb1(s.substring(1), prefix, k);
        }
    }  


    // print all subsets that take k of the remaining elements, with given prefix 
    public  static void comb2(String s, int k) { comb2(s, "", k); }
    private static void comb2(String s, String prefix, int k) {
        if (k == 0) System.out.println(prefix);
        else {
            for (int i = 0; i < s.length(); i++)
                comb2(s.substring(i + 1), prefix + s.charAt(i), k-1);
        }
    }  

    // read in N and k from command line, and print all subsets of size k from N elements
    public static void main(String[] args) {
       int N = Integer.parseInt(args[0]);
       int k = Integer.parseInt(args[1]);
       String alphabet = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
       String elements = alphabet.substring(0, N);

       comb1(elements, k);
       System.out.println();
       comb2(elements, k);
    }

}

Copyright © 2000–2011, Robert Sedgewick and Kevin Wayne.
Last updated: Fri Aug 5 12:25:48 EDT 2011.