## 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,

${\displaystyle 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:

${\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".)

${\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:

${\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:

• 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) {

// 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;
}
}