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.

[[[Category:Stacks]]