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:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle 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".)

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle 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:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle 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;
	}
}