package orderings;

/**
 * The main() method in this class generates all sequences of length ITEMS made up of 
 * integers chosen from the range from 0 to ITEMS - 1.  It counts the sequences and
 * outputs the number of sequences (which should be ITEMS raised to the power ITEMS).
 * If the value of PRINT is true, it also outputs each individual sequence.
 */
public class AllOrders {

	/**
	 *  The integers from 0 to (ITEMS - 1) will be arranged into sequences of
	 *  length ITEMS.  The value should be a positive integer.
	 *  ***** WARNING:  Don't try to make ITEMS bigger than 9 if you are counting
	 *  sequences.  If you are only counting permutations and derrangements,
	 *  don't try to make it bigger than 12. *****
	 */  
	private final static int ITEMS = 4;
	

	/**
	 * If PRINT is set to true, then each sequence that is generated will be
	 * output to System.out.  If PRINT is false, the sequences are generated
	 * internally but not printed, and only the number of sequences is output.
	 * It only makes sense to set PRINT to true if the value of ITEMS is small,
	 * say 5 or less.
	 */
	private final static boolean PRINT = true;


	/**
	 * This global variable is used for counting the sequences that are generated.
	 * It is incremented each time a sequence is generated in the sequences() method,
	 * and its value is output at the end of the program.
	 */
	private static int sequenceCount;

	
	/**
	 * The main() method is described in the comment for the class.
	 */
	public static void main(String[] args) {
		int[] itemList = new int[ITEMS];
		System.out.println("Finding all sequences made from " 
				+ ITEMS + " integers...\n");
		sequenceCount = 0;
		sequences(itemList, 0);
		System.out.println("\nThere were " + sequenceCount + " sequences.\n");
		System.out.println("The value of " + ITEMS + "^" + ITEMS + " is " + Math.pow(ITEMS, ITEMS));
	}

	/**
	 * This recursive method generates sequences of integers selected from
	 * the range 0 to ITEMS-1.  Whenever it finishes a complete sequence of length
	 * ITEMS, it increments the global variable sequenceCount, and, if PRINT
	 * is true, it outputs the sequence to standard output.
	 * @param listSoFar an array of length ITEMS that contains part of
	 * a sequence, or possibley a completed sequence, when this method is
	 * called.  If the sequence is complete, it is simply counted and printed.
	 * Otherwise, this method adds each possible item onto listSoFar, calling
	 * itself recursively to complete the sequence.
	 * @param itemsInList The number of items in the sequence.  This tells how many
	 * places in the array listSoFar have already been filled before the method is called.
	 */
	private static void sequences(int[] listSoFar, int itemsInList) {
		if (itemsInList == listSoFar.length) {  // The sequence is complete.
			if (PRINT)
				printList(listSoFar);
			sequenceCount++;
		}
		else { // Add a new item to the list in all possible ways
			for (int i = 0; i < ITEMS; i++) {
				listSoFar[itemsInList] = i;  // Add i onto the current sequence.
				itemsInList++;  // Since the length of the sequence has gone up by one.
				sequences(listSoFar, itemsInList); // Complete sequence in all possible ways.
				itemsInList--;  // Removes i from end of sequence before doing next item.
			}
		}
	}

	
	/**
	 * Prints the integers in an array on one line with several spaces at the
	 * beginning of the line and one space between numbers in the list.
	 * @param list The array that contains the numbers that are to be output.
	 */
	private static void printList(int[] list) {
		System.out.print("   ");
		for (int i = 0; i < list.length; i++)
			System.out.print(" " + list[i]);
		System.out.println();
	}

}