//------------------------------------------------------------------------//
// David Cline
//
// Recursion, Odometers, Permutations, and Combinations
//
// Abstract:
// A frequent goal in computer science is to enumerate all permutations
// or combinations of a set.  If the number of items in the set is known
// at coding time, a classic solution is to write a fixed series of
// nested loops to create the desired result.  If the number of items is
// not known until runtime, however, the typical solution utilizes a
// recursive algorithm.  A less common approach is to use an iterative
// "odometer" algorithm.  Simply stated, an odometer is a loop that uses
// an array of counters rather than a single counter variable to control
// the loop operation.  In this talk, I will cover recursive and iterative
// odometer methods to generate permutations and combinations, and
// hopefully provide some insight about the relationship between recursive
// and iterative algorithms.
//------------------------------------------------------------------------//

//------------------------------------------------------------------------//
// Odometer.java
// A class to generate permutations and combinations, using loopy
// methods, recursion, and odometers.
//
// Motivating example:
// Given a boolean expression, the size of which is unknown at compile
// time, write code to create the truth table.
//
// Motivating example 2:
// Given a blocks workd description, where the number of blocks is
// unknown at compile time, write code to generate all possible moves
// from a given state.
//------------------------------------------------------------------------//

public class Odometer
{
    //------------------------------------------------------------------------//
    // Some example data
    //------------------------------------------------------------------------//

    static String[][] A = {
        {"0", "1", "2"},
        {"0", "1", "2"},
        {"0", "1", "2"}
    };

    static String[][] B = {
        {"A", "B"},
        {"1", "2"},
        {"X", "Y", "Z"}
    };

    static String[] C = {
        "Go",
        "Pokes",
        "Cowboys"
    };

    static String[] D = {
        "A",
        "B",
        "C",
        "D"
    };

    //------------------------------------------------------------------------//
    // main method
    //------------------------------------------------------------------------//

    public static void main(String[] args)
    {
        System.out.println();

        combinationsLoopy(A);
        //combinationsLoopy(B);

        //subsetsLoopy(C);
        //subsetsRecursive(D, "", 0);
        //subsetsBinaryOdometer(D);

        //combinationsOdometer(B);
        //combinationsWithHelper(B);

        //permutationsRecursive(D, "", 0);
        //permutationsWithHelper(D);
    }

    //------------------------------------------------------------------------//
    // loopy method to produce all combinations of one element from
    // each of 3 arrays (stored as a 2D array). The loopy method
    // represents a rigid logic structure that cannot readily adapt
    // to the data.  This results from the need for a nested loop for
    // each array.
    //------------------------------------------------------------------------//

    public static void combinationsLoopy(String[][] A)
    {
        for (int i=0; i<A[0].length; i++) {
            for (int j=0; j<A[1].length; j++) {
                for (int k=0; k<A[2].length; k++) {
                    String s = A[0][i] + " " + A[1][j] + " " + A[2][k];
                    System.out.println(s);
                }
            }
        }
    }

    //------------------------------------------------------------------------//
    // Enumerating all subsets (loopy version). As with the combinations
    // code, the loopy version is quite limited, since it requires a 
    // physical nested loop for each element in the set.
    //------------------------------------------------------------------------//

    public static void subsetsLoopy(String[] A)
    {
        for (int i=0; i<2; i++) {
            String a = "";
            if (i==1) a = A[0] + " ";

            for (int j=0; j<2; j++) {
                String b = a;
                if (j==1) b += A[1] + " ";

                for (int k=0; k<2; k++) {
                    String c = b;
                    if (k==1) c += A[2] + " ";
                    System.out.println("{ " + c + " } ");
                }
            }
        }
    }

    //------------------------------------------------------------------------//
    // Enumerating all subsets (recursive version). The recursive method 
    // offers much more flexibility.  In essence, the recursion "rolls up"
    // the nested loops, with one nesting per recursive call. In addition,
    // since the loops only count 0 and 1, we can dispense with the loop
    // entirely, and just make two recursive calls.
    //------------------------------------------------------------------------//

    public static void subsetsRecursive(String[] A, String subset, int index)
    {
        if (index >= A.length) {
            System.out.println("{ " + subset + " }");
            return;
        }

        // Subsets that do not include A[index]
        subsetsRecursive(A, subset, index+1);

        // Subsets that include A[index]
        subsetsRecursive(A, subset + " " + A[index], index+1);
    }

    //------------------------------------------------------------------------//
    // A "binary odometer" uses the bits of an integer to enumerate all
    // bit combinations up to 2^n.  To create a subset from a single int,
    // we extract the low order n bits of the int one at a time. A 1 bit
    // indicates that a particualr element from A should be included in
    // the subset, and a 0 indicates that it shoudl not be included.
    //------------------------------------------------------------------------//

    public static void subsetsBinaryOdometer(String[] A)
    {
        int numSubsets = 1 << A.length; // 2^(A.length)

        for (int odometer=0; odometer<numSubsets; odometer++) 
        {
            String subset = "";
            for (int i=0; i<A.length; i++) 
            {
                // if bit i of counter is a 1
                if (((odometer>>i) & 0x1) == 1) 
                {
                    subset += A[i] + " ";
                }
            }
            System.out.println("{ " + subset + " }");
        }
    }

    //------------------------------------------------------------------------//
    // Full odometer. Instead of a single counter variable, an array
    // of counter variables controls the loop. The counters are incremented
    // in "odometer" fashion.  That is, the low order counter is incremented
    // first. If it overflows, it is reset to 0, and the next counter is 
    // incremented, and so forth.  Once the last counter overflows, the
    // algorithm is done.
    //------------------------------------------------------------------------//

    public static void combinationsOdometer(String[][] A)
    {
        int[] counters = new int[A.length]; // the "odometer" counters

        while (true)
        {
            // print the current combination
            String comb = "";
            for (int i=0; i<A.length; i++) {
                // counter i tells which element from set i to take
                comb += A[i][counters[i]] + " ";
            }
            System.out.println(comb);

            // Advance the odometer
            int c = 0; // the current counter
            counters[c]++; // increment the first counter
            while (counters[c] >= A[c].length) // if counter c overflows
            {
                counters[c] = 0; // reset counter c
                c++; // increment the current counter
                if (c >= A.length) break; // if we run out of counters, we're done
                counters[c]++;
            }
            if (c >= A.length) break; // done with all combinations
        }
    }

    //------------------------------------------------------------------------//
    // A nice feature of the odometer algorithm is that the advancing of
    // the counters can be encapsulated in a service routine. nextCombination
    // does this.
    //------------------------------------------------------------------------//

    public static boolean nextCombination(String[][] A, int[] counters)
    {
        int c = 0; // the current counter
        counters[c]++; // increment the first counter
        while (counters[c] >= A[c].length) // if counter c overflows
        {
            counters[c] = 0; // reset counter c
            c++; // increment the current counter
            if (c >= A.length) return false; // if we run out of counters, we're done
            counters[c]++;
        }
        return true;
    }

    //------------------------------------------------------------------------//
    // Given the service routine to advance the odometer counters, the
    // actual structure of an algorithm to work with combinations
    // simply becomes a while loop, with a "nextCombination" call.
    //------------------------------------------------------------------------//

    public static void combinationsWithHelper(String[][] A)
    {
        int[] counters = new int[A.length];

        while (true) {
            // print current combination
            String comb = "";
            for (int i=0; i<A.length; i++) {
                comb += A[i][counters[i]] + " ";
            }
            System.out.println(comb);

            // Advance combination
            if (!nextCombination(A, counters)) break;
        }
    }

    //------------------------------------------------------------------------//
    // The permutations of a list can be created easily using a recursive
    // algorithm. The permutations code here reorders the list to make
    // the permutation, and then undoes the changes when it is through.
    //------------------------------------------------------------------------//

    public static void swap(String[] A, int i, int j)
    {
        String temp = A[i];
        A[i] = A[j];
        A[j] = temp;
    }

    public static void permutationsRecursive(String[] A, String perm, int index)
    {
        if (index >= A.length) {
            System.out.println(perm);
        }
        else {
            for (int i=index; i<A.length; i++) {
                swap(A, index, i);
                permutationsRecursive(A, perm + A[index] + " ", index+1);
                swap(A, index, i);
            }
        }
    }

    //------------------------------------------------------------------------//
    // We can make an odometer that will enumerate the permutations. Each
    // counter will have a limit of one less than the last.
    //------------------------------------------------------------------------//

    public static boolean nextPermutation(int[] limits, int[] counters)
    {
        int c = 0; // the current counter
        counters[c]++; // increment the first counter
        while (counters[c] >= limits[c]) // if counter c overflows
        {
            counters[c] = 0; // reset counter c
            c++; // increment the current counter
            if (c >= A.length) return false; // if we run out of counters, we're done
            counters[c]++;
        }
        return true;
    }

    public static void permutationsWithHelper(String[] A)
    {
        int[] counters = new int[A.length];
        int[] limits = new int[A.length];
        String[] B = new String[A.length];

        for (int i=0; i<limits.length; i++) 
            limits[i] = (limits.length-i);

        while (true) {
            // print current permutation
            String perm = "";
            for (int i=0; i<B.length; i++) // Copy Array
                B[i] = A[i];
            for (int i=0; i<B.length; i++) {
                perm += B[counters[i]] + " ";
                swap(B, B.length-i-1, counters[i]);
            }
            System.out.println(perm);

            // Advance permutation
            if (!nextPermutation(limits, counters)) break;
        }
    }
}