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 anaysis

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.

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:

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.

[[[Category:Stacks]]