# StacksQueues/Subsets

### From charlesreid1

## Contents

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

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:

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".)

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:

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 "abcd**g**kji**h**fe"

comes ""abcd**h**ef**g**ijk"

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

## Flags

Data StructuresThis is the staging ground for computer science notes as part of the 2017 CS Study Plan.
Classes of data structures: Abstract Data Types Array-based and Link-based memory management: ArrayLists and Linked Lists Algorithmic Analysis of Data Structures: Algorithmic Analysis of Data Structures Advanced data structures: Advanced Data Structures
· Template:DataStructuresFlag · e |

ArraysSeries on Data Structures Python: Arrays/Python Java: Arrays/Java Categories: Category:Python Arrays
· Template:ArraysFlagBase · e |

Stacks and QueuesSeries on Data Structures
StacksQueues/Python StacksQueues/Python/LinkedStack
StacksQueues/Java StacksQueues/Java/LinkedStack
Postfix_Expressions#Stacks
· Template:StacksQueuesFlagBase · e |

Priority Queues and HeapsSeries on Data Structures
Priority Queues/Heap
· Template:PriorityQueuesFlagBase · e |

Linked ListSeries on Data Structures
· Template:LinkedListFlagBase · e |

TreesSeries on Data Structures Abstract data type: Trees/ADT Concrete implementations: Trees/LinkedTree
Preorder traversal: Trees/Preorder Postorder traversal: Trees/Postorder In-Order traversal: Binary Trees/Inorder Breadth-First Search: BFS Breadth-First Traversal: BFT Depth-First Search: DFS Depth-First Traversal: DFT OOP Principles for Traversal: Tree Traversal/OOP Tree operations: Trees/Operations Performance
Finding Minimum in Log N Time: Tree/LogN Min Search
Abstract data type: Binary Trees/ADT Concrete implementations: Binary Trees/LinkedBinTree Binary Trees/Cheat Sheet
· Template:TreesFlagBase · e |

Search TreesSeries on Data Structures
Binary Search Trees Trees/OOP
(Note that heaps are also value-sorting trees with minimums at the top. See Template:PriorityQueuesFlag and Priority Queues.)
· Template:SearchTreesFlagBase · e |

Maps and DictionariesSeries on Data Structures
Maps Map implementations: Maps/AbstractMap Dictionary implementations: Dictionaries/LinkedDict
Hash Maps/OOP Hash Maps/Dynamic Resizing Hash functions: Hash Functions Hash map implementations: Hash Maps/AbstractHashMap
Skip Lists Java implementations: SkipList
Sets
· Template:MapsFlagBase · e |