// Arup Guha
// 6/29/2016
// Code for Brute Force lecture (originally written for SI@UCF Java GUI class)

import java.util.*;

public class bruteforce {
	
	final public static boolean TEST_ODOMETER = true;
	final public static boolean TEST_COMBO_ODOM = false;
	final public static boolean TEST_COMBOS = false;
	final public static boolean TEST_PERM = false;
	final public static boolean TEST_DERANGE = false;
	final public static boolean TEST_UPWARDS = false;
	
	public static void main(String[] args) {
		
		// 4 digit odometer with 3 possible digits.
		if (TEST_ODOMETER) odometer(new int[4], 3, 0, true);
		
		// subsets of size 5
		if (TEST_COMBO_ODOM) odometer(new int[5], 2, 0, false);
		
		// subsets of size 5
		if (TEST_COMBOS) printcombos(new int[5], 0);
		
		// perms of size 4
		if (TEST_PERM) printperms(new int[4], new boolean[4], 0);
		
		// derangements of size 4
		if (TEST_DERANGE) derange(new int[4], new boolean[4], 0);
		
		// upwards of length 4 with a skip of 2 (or more)
		if (TEST_UPWARDS) upwards(new char[4], 2, 0);
	}

	public static void odometer(int[] digits, int numDigits, int k, boolean printFlag) {

		// Odometer is filled, print it.
    	if (k == digits.length) {
    		print(digits, digits.length, printFlag);
			return;
    	}
    	
    	// Try each possible digit in slot k.
    	for (int i=0; i<numDigits; i++) {
        	digits[k] =i;
        	odometer(digits, numDigits, k+1, printFlag);
    	}
	}
	
	public static void printcombos(int[] combo, int k) {
    
    	// This itself is a valid combination.
    	print(combo, k, true);

    	// Determine the smallest item that can go in slot k.
    	int start = 0;
    	if (k > 0) start = combo[k-1] + 1;

    	// Same as odometer, except a different start value.
    	for (int i=start; i<combo.length; i++) {
        	combo[k] = i;
       		printcombos(combo, k+1);
    	}
	}
	
	public static void printperms(int[] perm, boolean[] used, int k) {
    
    	// Filled out a permutation, print it.
    	if (k == perm.length) print(perm, perm.length, true);

		// Try each unused item in slot k.
    	for (int i=0; i<perm.length; i++) {
        	if (!used[i]) {
        		
        		// Mark it and put it in.
            	used[i] = true;
           		perm[k] = i;
           		
           		// Recurse.
            	printperms(perm, used, k+1);
            	
            	// Must unmark...
            	used[i] = false;
        	}
    	}
	}
	
	public static void derange(int[] perm, boolean[] used, int k) {

		// Filled out a derangement, print it.
    	if (k == perm.length) print(perm, perm.length, true);

		// Try each unused item in slot k that isn't k.
    	for (int i=0; i<perm.length; i++) {
        	if (!used[i] && i != k) {
        		
        		// Mark it and put it in.
            	used[i] = true;
            	perm[k] = i;
            	
            	// Recurse.
            	derange(perm, used, k+1);
            	
            	// Must unmark...
            	used[i] = false;
        	}
    	}
	}
	
	// Prints all skip-level upwards of length word.length with the first k items fixed.
	public static void upwards(char[] word, int skip, int k) {
    
    	// Filled the word, print it.
    	if (k == word.length) System.out.println(new String(word));

		// Recursive case.
    	else {
        
        	// Calculate first possible letter to place in slot k.
        	char start = 'a';
        	if (k > 0) start = (char)(word[k-1] + skip + 1);

			// Try this and all subsequent letters in slot k.
        	for (char i=start; i<='z'; i++) {
            	word[k] = i;
            	upwards(word, skip, k+1);
        	}
    	}
	}
	
	// if mode is true, prints items[0..length-1]
	// if mode is false, it interprets items as boolean array with 0 as false
	// and all other values as true and prints out the indexes that store true values
	// in sorted order.
	public static void print(int[] items, int length, boolean mode) {
		
		// Standard print - prints each item in items[0...length-1].
		if (mode) {
			for (int i=0; i<length; i++)
				System.out.print(items[i]+" ");
		}
		
		// Uses boolean interpretation of items data if items[i] != 0, then item i is in the set.
		else {
			for (int i=0; i<length; i++)
				if (items[i] != 0)
					System.out.print(i+" ");
		}
		System.out.println();
	}
	
}