StacksQueues/Subsets

All possible subsets

Based on Goodrich Python Chapter 6 Stacks and Queues.

Question: Use stacks S and queues Q to generate all possible subsets of an n-element set T without using recursion.

Example: T = {1, 2, 3, 4}

All possible subsets: {1, 2, 3} , {1, 2, 4}, {1, 3,4}, {2, 3, 4}

Math Analysis

The formula for this operation, subsets for which order is not important, we use the choose function, or n-choose-k function,

$ C(n,k) = \dfrac{n!}{(n-k)! k!} $

For the example given, there are 4 total elements, from which are are choosing 3, order ignored. That is 4 choose 3, for 4 outcomes:

$ C(4,3) = \dfrac{4!}{(4-3)! 3!} = 4 $

corresponding to the 4 possible subsets given above.

This relates to the N Queens Problem, in which we use backtracking and Recursion to answer the question of how many non-attacking configurations of N queens can be found on an NxN chessboard. In the case of a standard chessboard, we are placing 8 queens on 64 possible squares - so n = 64 possible squares to choose, from which we select k = 8 - which we can express as 64 choose 8 (that's if we choose to ignore any solutions that are simply rotations of prior solutions, and not consider them "new".)

$ C(64,8) = \dfrac{64!}{(64-8)! 8!} = 4,426,165,368 $

or about 4e9, or 4 billion.

Note that if we had considered each rotation of a given solution to count as a solution, we would have been using the n-pick-k function, which is substantially larger:

$ P(64,8) = \dfrac{64!}{(64-8)!} = 178,462,987,637,760 $

or around 2e14, or 178 trillion. That's 1e5 or 100,000 x bigger. Remember, this is the total number of possible solutions.

Permutations without recursion

Now, we're asked to find the permutations without using recursion - that's really asking us to do it with constant additional space, instead of building some complicated backtracking structure and having six dozen instances of a function on the stack.

Algorithm

Here are the steps:

To find permutations, in lexographic order:

1. Sort the list of items and print this as the first permutation

2. Let i be the last index such that input[i] < input[i+1] (if no such index, we are done)

3. Let j be the last index such that input[i] < input[j]

4. Swap input[i] with input[j]

5. Reverse input[i+1] through input[input.length-1]

Example

Example:

after "abcdgkjihfe"

comes ""abcdhefgijk"

Break that down one more time:

Start with my name:

• ACEHLRS

Round one:

• Find i, i=5 (R)
• Find j, j=6 (S)
• Swap i and j: ACEHLSR
• Reverse inputi+1 thru end: ACEHLSR
• Put a permutation in the bukkit

Round two:

• Find i, i=4 (L)
• Find j, j=6 (R)
• Swap i and j: ACEHRSL
• Reverse inputi+1 thru end: ACEHRLS
• Put a permutation in the bukkit

etc.

Implemlentation

Java

Also see StacksQueues/Subsets/Java

	public static LinkedQueue<String> stringPermutations(String s_input) {
		LinkedQueue<String> q = new LinkedQueue<String>();

		// Save useful info
		int n = s_input.length();

		char[] input = s_input.toCharArray();
		Arrays.sort(input);

		// First is sorted string
		q.enqueue(new String(input));

		boolean done = false;

		try {

			// Loop until we reach end
			while(!done) {
				// Step 1:
				// let i be the last index such that input[i] < input[i+1]
				// (if no such index, i=0 and we are done)
				int i = -1;
				for(int k=0; k<(n-1); k++) {
					if(input[k] < input[k+1]) {
						i = k;
					}
				}
				if(i<0) {
					// No such index, we are done
					done = true;
					break;
				}

				// Step 2:
				// let j be the last index such that input[i] < input[j]
				int j = -1;
				for(int k=i+1; k<n; k++) {
					if(input[i] < input[k]) {
						j = k;
					}
				}

				// Step 3:
				// swap i and j
				swap(input,i,j);

				// Step 4:
				// reverse i+1 thru length-1
                reverseFrom(input, i+1);

				q.enqueue(new String(input));
			}

		} catch(ArrayIndexOutOfBoundsException e) {
			System.out.println("OOPSIE");
		}
		return q;
	}
}