StacksQueues/Subsets - Revision history

Admin: /* Java */

2017-06-04T18:59:45Z

Java

@@ Line 94: / Line 94: @@
 ===Java===
-See [[StacksQueues/Subsets/Java]]
+Also see [[StacksQueues/Subsets/Java]]
 ==Flags==

Admin: /* Implemlentation */

2017-06-04T17:53:21Z

Implemlentation

← Older revision		Revision as of 17:53, 4 June 2017
Line 90:		Line 90:
	etc.		etc.

	===Implemlentation===		==Implemlentation==



			===Java===

			See [[StacksQueues/Subsets/Java]]

	==Flags==		==Flags==

Admin at 17:43, 4 June 2017

2017-06-04T17:43:10Z

← Older revision		Revision as of 17:43, 4 June 2017
Line 100:		Line 100:
	{{DataStructuresFlag}}		{{DataStructuresFlag}}

	[[[Category:Stacks]]		[[Category:Stacks]]
	[[Category:Queues]]		[[Category:Queues]]
			[[Category:Math]]
			[[Category:Permutations]]
			[[Category:Combinatorics]]

Admin: /* math anaysis */

2017-06-04T17:42:39Z

math anaysis

← Older revision		Revision as of 17:42, 4 June 2017
Line 9:		Line 9:
	All possible subsets: {1, 2, 3} , {1, 2, 4}, {1, 3,4}, {2, 3, 4}		All possible subsets: {1, 2, 3} , {1, 2, 4}, {1, 3,4}, {2, 3, 4}

	===~~math anaysis~~===		===Math Analysis===

	The formula for this operation, subsets for which order is not important, we use the choose function, or n-choose-k function,		The formula for this operation, subsets for which order is not important, we use the choose function, or n-choose-k function,
Line 40:		Line 40:

	or around 2e14, or 178 trillion. That's 1e5 or 100,000 x bigger. Remember, this is the total number of possible solutions.		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===		===Permutations without recursion===

Admin at 17:42, 4 June 2017

2017-06-04T17:42:26Z

← Older revision		Revision as of 17:42, 4 June 2017
Line 45:		Line 45:

	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.		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:		Here are the steps:
Line 59:		Line 61:

	5. Reverse <code>input[i+1]</code> through <code>input[input.length-1]</code>		5. Reverse <code>input[i+1]</code> through <code>input[input.length-1]</code>

			===Example===

	Example:		Example:
Line 87:		Line 91:
	etc.		etc.

			===Implemlentation===





			==Flags==

	{{DataStructuresFlag}}		{{DataStructuresFlag}}

Admin at 17:39, 4 June 2017

2017-06-04T17:39:55Z

← Older revision		Revision as of 17:39, 4 June 2017
Line 66:		Line 66:
	comes ""abcd'''h'''ef'''g'''ijk"		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.

Admin at 17:36, 4 June 2017

2017-06-04T17:36:00Z

← Older revision	Revision as of 17:36, 4 June 2017
Line 42:	Line 42:


		===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 <code>input[i] < input[i+1]</code> (if no such index, we are done)

		3. Let j be the last index such that <code>input[i] < input[j]</code>

		4. Swap <code>input[i]</code> with <code>input[j]</code>

		5. Reverse <code>input[i+1]</code> through <code>input[input.length-1]</code>

		Example:

		after "abcd'''g'''kji'''h'''fe"

		comes ""abcd'''h'''ef'''g'''ijk"

Admin: Created page with "==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..."

2017-06-04T17:32:25Z

Created page with "==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..."

New page

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

<math>
C(n,k) = \dfrac{n!}{(n-k)! k!}
</math>

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:

<math>
C(4,3) = \dfrac{4!}{(4-3)! 3!} = 4
</math>

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

<math>
C(64,8) = \dfrac{64!}{(64-8)! 8!} = 4,426,165,368
</math>

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:

<math>
P(64,8) = \dfrac{64!}{(64-8)!} = 178,462,987,637,760
</math>

or around 2e14, or 178 trillion. That's 1e5 or 100,000 x bigger. Remember, this is the total number of possible solutions.

{{DataStructuresFlag}}

[[[Category:Stacks]]
[[Category:Queues]]