StacksQueues/Python - Revision history

Admin: Replacing charlesreid1.com:3000 with git.charlesreid1.com

2019-10-09T03:54:51Z

Replacing charlesreid1.com:3000 with git.charlesreid1.com

← Older revision		Revision as of 03:54, 9 October 2019
Line 27:		Line 27:
	The array-based structure can either utilize a ctype array (as with the [[Arrays/Python/DynamicArray]] class), or can just utilize a list, which the DynamicArray class was meant to emulate.		The array-based structure can either utilize a ctype array (as with the [[Arrays/Python/DynamicArray]] class), or can just utilize a list, which the DynamicArray class was meant to emulate.

	Here is the code for an array-based stack: https://charlesreid1.com~~:3000~~/cs/python/src/master/stacks-queues-deques/stacks/ArrayStack.py		Here is the code for an array-based stack: https://git.charlesreid1.com/cs/python/src/master/stacks-queues-deques/stacks/ArrayStack.py

	See [[StacksQueues/Python/ArrayStack]]		See [[StacksQueues/Python/ArrayStack]]
Line 54:		Line 54:
	This was also the subject of "Igor" in the Google Code Jam problem "Ignore My Comments," who wanted to put C-style /* */ comments in every file, and wanted help building his own file parser to remove them.		This was also the subject of "Igor" in the Google Code Jam problem "Ignore My Comments," who wanted to put C-style /* */ comments in every file, and wanted help building his own file parser to remove them.

	https://charlesreid1.com~~:3000~~/charlesreid1/code-jam/src/master/ignore-my-comments		https://git.charlesreid1.com/charlesreid1/code-jam/src/master/ignore-my-comments

	Being able to focus on a single comment would allow focusing one character at a time.		Being able to focus on a single comment would allow focusing one character at a time.
Line 153:		Line 153:
	===Deque double-ended queue===		===Deque double-ended queue===

	Link to code on git.charlesreid1.com: https://charlesreid1.com~~:3000~~/cs/python/src/master/stacks-queues-deques/deque/ArrayDeque.py		Link to code on git.charlesreid1.com: https://git.charlesreid1.com/cs/python/src/master/stacks-queues-deques/deque/ArrayDeque.py

	Details of deque implementation: [[StacksQueues/Python/ArrayDeque]]		Details of deque implementation: [[StacksQueues/Python/ArrayDeque]]

Admin: /* Flags */

2017-09-09T17:08:59Z

Flags

← Older revision		Revision as of 17:08, 9 September 2017
Line 353:		Line 353:


	{{~~DataStructuresFlag~~}}		{{StacksQueuesFlag}}

Admin: /* All possible subsets */

2017-06-04T17:52:47Z

All possible subsets

← Older revision		Revision as of 17:52, 4 June 2017
Line 301:		Line 301:
	===All possible subsets===		===All possible subsets===

	'''Question: Use stacks S and queues Q to generate all possible subsets of an n-element set T without using recursion.'''		'''Question C-6.20) 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}		Example: T = {1, 2, 3, 4}

Admin: /* All possible subsets */

2017-06-04T17:41:28Z

All possible subsets

← Older revision		Revision as of 17:41, 4 June 2017
Line 337:		Line 337:
	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.

	See [[StacksQueues/Subsets]] for continued analysis.		The algorithm to solve this using a stack, and doing in-place permutations in a sorted and methodical order, is as follows:
			* Sort string and give this as first permutation
			* Let i be the last index such that input[i] < input[i+1]
			* Let j be the last index such that input[i] < input[j]
			* Swap i and j
			* Reverse input i+1 thru end

			See [[StacksQueues/Subsets]] for continued analysis and implementation.

	=Flags=		=Flags=

Admin: /* Questions from Goodrich Chapter 6 Stacks and Queues */

2017-06-04T17:31:29Z

Questions from Goodrich Chapter 6 Stacks and Queues

← Older revision		Revision as of 17:31, 4 June 2017
Line 197:		Line 197:
	=Questions=		=Questions=

	==Questions from Goodrich Chapter 6 Stacks and Queues==		==Questions from Goodrich Python Chapter 6 Stacks and Queues==

	===Recursive method to remove all items from stack===		===Recursive method to remove all items from stack===

Admin: /* Goodrich et al - Data Structures in Python - Chapter 6 Stacks and Queues */

2017-06-04T17:31:15Z

Goodrich et al - Data Structures in Python - Chapter 6 Stacks and Queues

← Older revision		Revision as of 17:31, 4 June 2017
Line 197:		Line 197:
	=Questions=		=Questions=

	==Goodrich ~~et al - Data Structures in Python -~~ Chapter 6 Stacks and Queues==		==Questions from Goodrich Chapter 6 Stacks and Queues==

	===Recursive method to remove all items from stack===		===Recursive method to remove all items from stack===

Admin: /* Goodrich et al Data Structures in Python Chapter 6 */

2017-06-04T17:30:45Z

Goodrich et al Data Structures in Python Chapter 6

← Older revision		Revision as of 17:30, 4 June 2017
Line 197:		Line 197:
	=Questions=		=Questions=

	==Goodrich et al Data Structures in Python Chapter 6==		==Goodrich et al - Data Structures in Python - Chapter 6 Stacks and Queues==

	===Recursive method to remove all items from stack===		===Recursive method to remove all items from stack===

Admin: /* All possible subsets */

2017-06-04T17:29:42Z

All possible subsets

← Older revision		Revision as of 17:29, 4 June 2017
Line 336:		Line 336:

	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.

			See [[StacksQueues/Subsets]] for continued analysis.

	=Flags=		=Flags=

Admin: /* All possible subsets */

2017-06-04T17:28:52Z

All possible subsets

← Older revision		Revision as of 17:28, 4 June 2017
Line 301:		Line 301:
	===All possible subsets===		===All possible subsets===

	Use stacks S and queues Q to generate all possible subsets of an n-element set T without using recursion.		'''Question: Use stacks S and queues Q to generate all possible subsets of an n-element set T without using recursion.'''

	T = {1, 2, 3, 4}		Example: T = {1, 2, 3, 4}

	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}

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

	<math>		<math>
Line 311:		Line 313:
	</math>		</math>

	fo the ~~exmaple~~, ~~that's~~ 4 choose 3,		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>		<math>
Line 318:		Line 320:

	corresponding to the 4 possible subsets given above.		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.

	=Flags=		=Flags=

Admin: /* All possible subsets */

2017-06-04T09:13:26Z

All possible subsets

← Older revision		Revision as of 09:13, 4 June 2017
Line 310:		Line 310:
	C(n,k) = \dfrac{n!}{(n-k)! k!}		C(n,k) = \dfrac{n!}{(n-k)! k!}
	</math>		</math>

			fo the exmaple, that's 4 choose 3,

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

			corresponding to the 4 possible subsets given above.

	=Flags=		=Flags=