Algorithms/Combinatorics and Heuristics - Revision history

Admin: Fix math syntax errors: remove blank line inside math tag, fix \exp{...} to \exp(...), remove stray slash before Category:Combinatorics (via update-page on MediaWiki MCP Server)

2026-06-05T23:30:26Z

Fix math syntax errors: remove blank line inside math tag, fix \exp{...} to \exp(...), remove stray slash before Category:Combinatorics (via update-page on MediaWiki MCP Server)

← Older revision		Revision as of 23:30, 5 June 2026
Line 1:		Line 1:

	=Notes=		=Notes=

Line 167:		Line 168:
	<math>		<math>
	P(n-1) = \dfrac{1}{n-1} \qquad P(n) = 1 \qquad P(n-1,n) = \dfrac{1}{n-1}		P(n-1) = \dfrac{1}{n-1} \qquad P(n) = 1 \qquad P(n-1,n) = \dfrac{1}{n-1}

	</math>		</math>

Line 209:		Line 209:

	<math>		<math>
	P(s_i, s_j, T) = \exp{ \left( \dfrac{s_i - s_j}{k_B T} \right) }		P(s_i, s_j, T) = \exp\left( \dfrac{s_i - s_j}{k_B T} \right)
	</math>		</math>

Line 221:		Line 221:

	<math>		<math>
	P(s_i, s_j, T) = \exp{ \left( \dfrac{C(s_i) - C(s_j)}{k T} \right) }		P(s_i, s_j, T) = \exp\left( \dfrac{C(s_i) - C(s_j)}{k T} \right)
	</math>		</math>

Line 299:		Line 299:

	[[Category:AOCP]]		[[Category:AOCP]]
	/[[Category:Combinatorics]]		[[Category:Combinatorics]]
	[[Category:Heuristics]]		[[Category:Heuristics]]
	[[Category:Skiena]]		[[Category:Skiena]]
	[[Category:Recursion]]		[[Category:Recursion]]
	[[Category:Backtracking]]		[[Category:Backtracking]]

Admin: /* Skiena Chapter 7 */

2017-08-06T21:47:18Z

Skiena Chapter 7

← Older revision		Revision as of 21:47, 6 August 2017
Line 3:		Line 3:
	==Skiena Chapter 7==		==Skiena Chapter 7==

	This chapter covers the basic ideas of searching for solutions for combinatorial/permutation problems		This chapter covers the basic ideas of searching for solutions for combinatorial/permutation problems.

			Three principal techniques covered:
			* Random sampling (Monte Carlo method)
			* Local search
			* Simulated annealing

	===Combinatorial problems and solutions===		===Combinatorial problems and solutions===

Admin: /* Combinatorial problems and solutions */

2017-08-06T21:46:43Z

Combinatorial problems and solutions

← Older revision		Revision as of 21:46, 6 August 2017
Line 36:		Line 36:
	* new array each time, inside each method, so set of possible solutions is not passed around - copy is created so free to modify/not restore		* new array each time, inside each method, so set of possible solutions is not passed around - copy is created so free to modify/not restore
	* Stubs used fror method calls like processing solution, making move, unmaking move - this enables application of the same function to different problems		* Stubs used fror method calls like processing solution, making move, unmaking move - this enables application of the same function to different problems

	~~Example: Construct all possible subsets~~
	* Each element doubles the number of subsets that can be created
	* Number of subsets with 1 element in the set: 2 subsets (empty/full)
	* Number of subsets with 2 elements in the set: 4 subsets
	* Number of subsets with n elements in the set: 2^n subsets

	When solving, the main question is, how do you represent a set?		When solving, the main question is, how do you represent a set?
Line 49:		Line 43:
	* Can use bit vector - an array of booleans - indicating whether an element is a member of a particular set or not		* Can use bit vector - an array of booleans - indicating whether an element is a member of a particular set or not
	* The order in which sets are constructed depends on the set S construction procedure, called above		* The order in which sets are constructed depends on the set S construction procedure, called above

			===Generating Permutations===

			Example: Construct all possible subsets
			* Each element doubles the number of subsets that can be created
			* Number of subsets with 1 element in the set: 2 subsets (empty/full)
			* Number of subsets with 2 elements in the set: 4 subsets
			* Number of subsets with n elements in the set: 2^n subsets

	Constructing permutations:		Constructing permutations:
Line 61:		Line 63:
	** element i of an array can be any eleent that has not already appearedd		** element i of an array can be any eleent that has not already appearedd
	* complicated bit vector solution - basically, it says, who's in this permutation - then it adds items that aren't already in the solution to the new permutations		* complicated bit vector solution - basically, it says, who's in this permutation - then it adds items that aren't already in the solution to the new permutations

			===More Examples===

	Shortest path:		Shortest path:

Admin: /* Examples and Applications */

2017-08-04T22:30:23Z

Examples and Applications

← Older revision		Revision as of 22:30, 4 August 2017
Line 249:		Line 249:
	* Independent set (largest subgraphs in G with no edges containing both endpoints in S)		* Independent set (largest subgraphs in G with no edges containing both endpoints in S)
	* Circuit board placement - minimizing aspect ratio, minimizing total wire length (rectangular modules r1, r2, ..., rn with dimensions Hi x Li and wires wij connecting the modules)		* Circuit board placement - minimizing aspect ratio, minimizing total wire length (rectangular modules r1, r2, ..., rn with dimensions Hi x Li and wires wij connecting the modules)

			==Skiena End of Chapter Questions==

			Skiena Chapter 7 Problem 14 - [[String Permutations]] - write a function to find all permutations of the letters in a particular string. For example, "HELLO".


	=Examples and Applications=		=Examples and Applications=

Admin: /* Examples and Applications */

2017-07-26T19:18:31Z

Examples and Applications

← Older revision		Revision as of 19:18, 26 July 2017
Line 254:		Line 254:
	[[Project Euler]] provides fantastic examples of combinatoric problems that often have astronomical problem spaces that can be cleverly traversed much faster with a few tricks.		[[Project Euler]] provides fantastic examples of combinatoric problems that often have astronomical problem spaces that can be cleverly traversed much faster with a few tricks.

	[[Project Euler/501\|Problem 501]] is an excellent example of this.		[[Project Euler/501\|Project Euler Problem 501]] is an excellent example of this.

			[[Project Euler/502\|Project Euler Problem 502]] is another excellent combinatoric search question.

	=Related Pages=		=Related Pages=

Admin: /* Flags */

2017-07-21T22:19:08Z

Flags

← Older revision		Revision as of 22:19, 21 July 2017
Line 280:		Line 280:
	{{AlgorithmsFlag}}		{{AlgorithmsFlag}}

	[[Category:Combinatorics]]		{{AOCPFlag}}

			[[Category:AOCP]]
			/[[Category:Combinatorics]]
	[[Category:Heuristics]]		[[Category:Heuristics]]
	[[Category:Skiena]]		[[Category:Skiena]]
	[[Category:Recursion]]		[[Category:Recursion]]
	[[Category:Backtracking]]		[[Category:Backtracking]]

Admin: /* Combinatorics Problems */

2017-07-20T22:03:35Z

Combinatorics Problems

← Older revision		Revision as of 22:03, 20 July 2017
Line 272:		Line 272:
	* [[AOCP/Binomial_Coefficients#The_Zeta_Family\|The Zeta Family]] picks a monogram		* [[AOCP/Binomial_Coefficients#The_Zeta_Family\|The Zeta Family]] picks a monogram
	* [[AOCP/Binomial_Coefficients#Sum_of_Sequence\|Sum of binomial sequence]]		* [[AOCP/Binomial_Coefficients#Sum_of_Sequence\|Sum of binomial sequence]]

			[[AOCP/Generating Functions]] page:
			* [[AOCP/Generating Funtions#Knuth_AOCP_Section_1.2.9_Problem_1\|Art of Computer Programming, Section 1.2.9, Problem 1]]

	=Flags=		=Flags=

Admin: /* Combinatorics Problems */

2017-07-20T21:44:44Z

Combinatorics Problems

← Older revision		Revision as of 21:44, 20 July 2017
Line 267:		Line 267:

	Collected combinatorics problems across this wiki.		Collected combinatorics problems across this wiki.
	* [[AOCP/Binomial_Coefficients#Knuth_AOCP_Section_1.2.5_Problem_36~~]] - Problem 36 from~~ Section 1.2.5 ~~of AOCP~~
	* [[AOCP/Binomial_Coefficients#The_Zeta_Family]] ~~- Zeta Family and picking~~ a monogram		[[AOCP/Binomial Coefficients]] page:
	* [[AOCP/Binomial_Coefficients#Sum_of_Sequence~~]] -~~ Sum of sequence ~~of binomial coefficients~~		* [[AOCP/Binomial_Coefficients#Knuth_AOCP_Section_1.2.5_Problem_36\|Art of Computer Programming, Section 1.2.5, Problem 36]]
			* [[AOCP/Binomial_Coefficients#The_Zeta_Family\|The Zeta Family]] picks a monogram
			* [[AOCP/Binomial_Coefficients#Sum_of_Sequence\|Sum of binomial sequence]]

	=Flags=		=Flags=

Admin: /* Combinatorics Problems */

2017-07-20T21:43:43Z

Combinatorics Problems

← Older revision		Revision as of 21:43, 20 July 2017
Line 267:		Line 267:

	Collected combinatorics problems across this wiki.		Collected combinatorics problems across this wiki.
			* [[AOCP/Binomial_Coefficients#Knuth_AOCP_Section_1.2.5_Problem_36]] - Problem 36 from Section 1.2.5 of AOCP
			* [[AOCP/Binomial_Coefficients#The_Zeta_Family]] - Zeta Family and picking a monogram
			* [[AOCP/Binomial_Coefficients#Sum_of_Sequence]] - Sum of sequence of binomial coefficients

	=Flags=		=Flags=

Admin: /* Related Pages */

2017-07-20T10:17:57Z

← Older revision		Revision as of 10:17, 20 July 2017
Line 263:		Line 263:
	* [[AOCP/Permutations]]		* [[AOCP/Permutations]]
	* [[AOCP/Multisets]]		* [[AOCP/Multisets]]

			=Combinatorics Problems=

			Collected combinatorics problems across this wiki.

	=Flags=		=Flags=