AOCP/Generating Permutations and Tuples - Revision history

Unknown user: /* Arbitrary string permutations */

2020-07-23T05:37:52Z

Arbitrary string permutations

← Older revision		Revision as of 05:37, 23 July 2020
Line 22:		Line 22:

	<math>		<math>
	0 \leq a_j < m_j \qquad for 1 \leq j \leq n		0 \leq a_j < m_j \qquad \mbox{for } 1 \leq j \leq n
	</math>		</math>

2020-07-23T05:27:54Z

Arbitrary string permutations

← Older revision		Revision as of 05:27, 23 July 2020
Line 29:		Line 29:
	This is a multiset problem, where we have the multiset <math>\{ m_1 \cdot a_1, m_2 \cdot a_2, \dots, m_n \cdot a_n \}</math>		This is a multiset problem, where we have the multiset <math>\{ m_1 \cdot a_1, m_2 \cdot a_2, \dots, m_n \cdot a_n \}</math>

	~~Thien~~ the task is essentially the same as repeatedly adding unity to the number <math>\left[ a_1, a_2, a_3, \dots, a_n \right]</math> in the mixed-radix number system <math>\left[ m_1, m_2, \dots, m_n \right]</math>		Then the task is essentially the same as repeatedly adding unity to the number <math>\left[ a_1, a_2, a_3, \dots, a_n \right]</math> in the mixed-radix number system <math>\left[ m_1, m_2, \dots, m_n \right]</math>

	==Algorithm M==		==Algorithm M==

2019-03-17T21:54:26Z

2017-08-06T21:47:39Z

Alternative Formulation

2017-08-06T21:43:26Z

Flags

2017-08-06T21:41:33Z

Algorithm M

2017-08-06T21:41:19Z

Algorithm G

← Older revision		Revision as of 21:41, 6 August 2017
Line 141:		Line 141:
	==Algorithm G==		==Algorithm G==

			Algorithm G = gray binary generation algorithm

			This algorithm visits all binary tuples <math>(a_{n-1}, a_{n-2}, \dots, a_1, a_0)</math>

			Start with <math>(0, 0, \dots, 0, 0)</math> and change one bit at a time

			<pre>
			# Initialize
			set a_j <- 0 for 0 <= j < n
			set a_infty <- 0


			# Visit
			visit the n-tuple (a_{n-1}, ..., a_1, a_0)


			# Change Parity
			set a_infty <- 1 - a_infty


			# Choose j
			if a_infty = 1:
			set j <- 0
			else:
			let j >= 1 be minimum such that a_{j-1} = 1
			after kth time performing this step, j = rho(k)
			(rho is the ruler function)


			# Complement Coordinate j
			if j = n:
			terminate
			else:
			a_j <- 1 - a_j
			return to Visit step
			</pre>

	=Flags=		=Flags=

2017-08-06T21:34:55Z

Mixed Radix Algorithm

← Older revision		Revision as of 21:34, 6 August 2017
Line 31:		Line 31:
	Thien the task is essentially the same as repeatedly adding unity to the number <math>\left[ a_1, a_2, a_3, \dots, a_n \right]</math> in the mixed-radix number system <math>\left[ m_1, m_2, \dots, m_n \right]</math>		Thien the task is essentially the same as repeatedly adding unity to the number <math>\left[ a_1, a_2, a_3, \dots, a_n \right]</math> in the mixed-radix number system <math>\left[ m_1, m_2, \dots, m_n \right]</math>

	==~~Mixed Radix~~ Algorithm==		==Algorithm M==

			Algorithm M = mixed radix generation algorithm

	Algorithm for mixed-radix generation of permutations: this algorithm is a generalization of the "sequentially add one to the given number" approach		Algorithm for mixed-radix generation of permutations: this algorithm is a generalization of the "sequentially add one to the given number" approach

2017-08-06T21:34:31Z

Flags

@@ Line 78: / Line 78: @@
 				visit the n-tuple (a_1, a_2, a_3, a_4)
 </pre>
 =Flags=

2017-08-06T21:19:56Z

Add-One Mixed Radix Agorithm

← Older revision		Revision as of 21:19, 6 August 2017
Line 1:		Line 1:
	Algorithms for generating all permutations and tuples		Algorithms for generating all permutations and tuples

	=Add-One Mixed Radix Agorithm=		=Add-One Mixed Radix Generation Agorithm=

	==Binary string permutations==		==Binary string permutations==