Selasa, 17 Juli 2012

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();

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);
    }

}

Senin, 16 Juli 2012

Algorithm Permutations for Java Programming

a. Permutations
Write a program Permutations.java that take a command-line argument n and prints out all n! permutations of the n letters starting at a (assume that n is no greater than 26). A permutation of n elements is one of the n! possible orderings of the elements. As an example, when n = 3 you should get the following output. Do not worry about the order in which you enumerate them.

bca cba cab acb bac abc

Permutations.java

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

* Compilation: javac Permutations.java

* Execution: java Permutations N

* Enumerates all permutations on N elements.

* Two different approaches are included.

* % java Permutations 3

* abc

* acb

* bac

* bca

* cab

* cba

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

public class Permutations {

// print N! permutation of the characters of the string s (in order)

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

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

int N = s.length();

if (N == 0) System.out.println(prefix);

else {

for (int i = 0; i < N; i++)

perm1(prefix + s.charAt(i), s.substring(0, i) + s.substring(i+1, N));

}

// print N! permutation of the elements of array a (not in order)

public static void perm2(String s) {

int N = s.length();

char[] a = new char[N];

for (int i = 0; i < N; i++)

a[i] = s.charAt(i);

perm2(a, N);

}

private static void perm2(char[] a, int n) {

if (n == 1) {

System.out.println(a);

return;

}

for (int i = 0; i < n; i++) {

swap(a, i, n-1);

perm2(a, n-1);

swap(a, i, n-1);

}

// swap the characters at indices i and j

private static void swap(char[] a, int i, int j) {

char c;

c = a[i]; a[i] = a[j]; a[j] = c;

}

public static void main(String[] args) {

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

String alphabet = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";

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

perm1(elements);

System.out.println();

perm2(elements);

}

b. Permutations of size k.
Modify Permutations.java to PermutationsK.java so that it takes two command-line arguments n and k, and prints out all P(n, k) = n! / (n-k)! permutations that contain exactly k of the n elements. Below is the desired output when k = 2 and n = 4. You need not print them out in any particular order.

ab ac ad ba bc bd ca cb cd da db dc

PermutationsK.java

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

* Compilation: javac PermutationsK.java

* Execution: java PermutationsK N k

* Enumerates all permutations of size k chosen from N elements.

* % java PermutationsK 4 2 | sort

* ab

* ac

* ad

* ba

* bc

* bd

* ca

* cb

* cd

* da

* db

* dc

* Limitations

* -----------

* * Assumes N <= 52

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

public class PermutationsK {

public static void choose(char[] a, int R) { enumerate(a, a.length, R); }

private static void enumerate(char[] a, int n, int r) {

if (r == 0) {

for (int i = n; i < a.length; i++)

System.out.print(a[i]);

System.out.println();

return;

}

for (int i = 0; i < n; i++) {

swap(a, i, n-1);

enumerate(a, n-1, r-1);

swap(a, i, n-1);

}

// helper function that swaps a[i] and a[j]

public static void swap(char[] a, int i, int j) {

char temp = a[i];

a[i] = a[j];

a[j] = temp;

}

// sample client

public static void main(String[] args) {

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

int k = Integer.parseInt(args[1]);

String elements = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";

char[] a = new char[N];

for (int i = 0; i < N; i++)

a[i] = elements.charAt(i);

choose(a, k);

}