Heap's algorithm - Revision history

MarSch: /* Details of the algorithm */

2025-01-06T13:59:15Z

Details of the algorithm

← Previous revision		Revision as of 13:59, 6 January 2025
Line 41:		Line 41:
	<syntaxhighlight lang="pascal">		<syntaxhighlight lang="pascal">
	procedure permutations(n : integer, A : array of any):		procedure permutations(n : integer, A : array of any):
	// c is an encoding of the stack state. c[k] encodes the for-loop counter for when ~~generate~~(k - 1, A) is called		// c is an encoding of the stack state.
			// c[k] encodes the for-loop counter for when permutations(k - 1, A) is called
	c : array of int		c : array of int

MarSch: complete changing name of procedure to permutations and change comments of main algorithm

2025-01-06T13:33:49Z

complete changing name of procedure to permutations and change comments of main algorithm

← Previous revision		Revision as of 13:33, 6 January 2025
Line 14:		Line 14:

	<syntaxhighlight lang="pascal">		<syntaxhighlight lang="pascal">
			// Output the k! permutations of A in which the first k elements are permuted in all ways.
⚫	procedure ~~generate~~(k : integer, A : array of any):
			// To get all permutations of A, use k := length of A.
			//
			// If, k > length of A, will try to access A out of bounds.
			// If k <= 0 there will be no output (empty array has no permutations)
		⚫	procedure permutations(k : integer, A : array of any):
	if k = 1 then		if k = 1 then
	output(A)		output(A)
	else		else
	// ~~Generate~~ permutations with ~~k-th~~ ~~unaltered~~		// permutations with last element fixed
	// ~~Initially~~ k ~~= length(~~A)		permutations(k - 1, A)
		⚫	// permutations with last element swapped out
	generate(k - 1, A)

⚫	// ~~Generate~~ permutations ~~for~~ ~~k-th~~ swapped ~~with each k-1 initial~~
	for i := 0; i < k-1; i += 1 do		for i := 0; i < k-1; i += 1 do
	// Swap choice dependent on parity of k (even or odd)
	if k is even then		if k is even then
	swap(A[i], A[k-1]) ~~// zero-indexed, the k-th is at k-1~~		swap(A[i], A[k-1])
	else		else
	swap(A[0], A[k-1])		swap(A[0], A[k-1])
	end if		end if
	~~generate~~(k - 1, A)		permutations(k - 1, A)
	end for		end for
	end if		end if
Line 38:		Line 40:

	<syntaxhighlight lang="pascal">		<syntaxhighlight lang="pascal">
	procedure ~~generate~~(n : integer, A : array of any):		procedure permutations(n : integer, A : array of any):
	// c is an encoding of the stack state. c[k] encodes the for-loop counter for when generate(k - 1, A) is called		// c is an encoding of the stack state. c[k] encodes the for-loop counter for when generate(k - 1, A) is called
	c : array of int		c : array of int
Line 63:		Line 65:
	i := 1		i := 1
	else		else
	// Calling ~~generate~~(i+1, A) has ended as the while-loop terminated. Reset the state and simulate popping the stack by incrementing the pointer.		// Calling permutations(i+1, A) has ended as the while-loop terminated. Reset the state and simulate popping the stack by incrementing the pointer.
	c[i] := 0		c[i] := 0
	i += 1		i += 1
Line 141:		Line 143:

	<syntaxhighlight lang="pascal">		<syntaxhighlight lang="pascal">
	procedure ~~generate~~(k : integer, A : array of any):		procedure permutations(k : integer, A : array of any):
	if k = 1 then		if k = 1 then
	output(A)		output(A)
Line 148:		Line 150:
	// Recursively call once for each k		// Recursively call once for each k
	for i := 0; i < k; i += 1 do		for i := 0; i < k; i += 1 do
	~~generate~~(k - 1, A)		permutations(k - 1, A)
	// swap choice dependent on parity of k (even or odd)		// swap choice dependent on parity of k (even or odd)
	if k is even then		if k is even then
Line 193:		Line 195:

	<syntaxhighlight lang="pascal">		<syntaxhighlight lang="pascal">
	procedure ~~generate~~(k : integer, A : array of any):		procedure permutations(k : integer, A : array of any):
	if k = 1 then		if k = 1 then
	output(A)		output(A)
Line 200:		Line 202:
	// Recursively call once for each k		// Recursively call once for each k
	for i := 0; i < k; i += 1 do		for i := 0; i < k; i += 1 do
	~~generate~~(k - 1, A)		permutations(k - 1, A)
	// avoid swap when i==k-1		// avoid swap when i==k-1
	if (i < k - 1)		if (i < k - 1)

MarSch: /* Proof */ make second case of induction more clear

2025-01-06T13:03:38Z

Proof: make second case of induction more clear

← Previous revision		Revision as of 13:03, 6 January 2025
Line 96:		Line 96:
	Claim: If array A has length {{mvar\|n}}, then <code>permutations(n, A)</code> will result in either A being unchanged, if {{mvar\|n}} is odd, or, if {{mvar\|n}} is even, then A is rotated to the right by 1 (last element shifted in front of other elements).		Claim: If array A has length {{mvar\|n}}, then <code>permutations(n, A)</code> will result in either A being unchanged, if {{mvar\|n}} is odd, or, if {{mvar\|n}} is even, then A is rotated to the right by 1 (last element shifted in front of other elements).

	~~Basis~~: If array {{mvar\|A}} has length 1, then <code>permutations(1, A)</code> will output A and stop, so A is unchanged. Since 1 is odd, this is what was claimed, so the claim is true for arrays of length 1.		Base: If array {{mvar\|A}} has length 1, then <code>permutations(1, A)</code> will output A and stop, so A is unchanged. Since 1 is odd, this is what was claimed, so the claim is true for arrays of length 1.

	Induction: If the claim is true for arrays of length {{math\|l}} ≥ 1, then we show that the claim is true for arrays of length {{math\|l}}+1 (together with the base case this proves that the claim is true for arrays of all lengths). Since the claim depends on whether {{math\|l}} is odd or even, we prove each case separately.		Induction: If the claim is true for arrays of length {{math\|l}} ≥ 1, then we show that the claim is true for arrays of length {{math\|l}}+1 (together with the base case this proves that the claim is true for arrays of all lengths). Since the claim depends on whether {{math\|l}} is odd or even, we prove each case separately.

	If {{math\|l}} is odd, then, by the induction hypothesis, for an array A of length {{math\|l}}, <code>permutations(l, A)</code> will not change A, and for the claim to hold for arrays of length {{math\|l}}+1, we need to show that <code>permutations(l+1, A)</code> rotates A to the right by 1. Doing <code>permutations(l+1, A)</code> will first do <code>permutations(l, A)</code> (leaving A unchanged since {{math\|l}} is odd) and then in each iteration {{math\|i}} of the for-loop, swap the elements in positions {{math\|i}} and {{math\|l}} (the last position) in A. The first swap puts element {{math\|l}} (the last element) in position 0, and element 0 in position {{math\|l}}. The next swap puts the element in position {{math\|l}} (where the previous iteration put original element 0) in position 1 and element 1 in position {{math\|l}}. In the final iteration, the swap puts element {{math\|l}}-1 is in position {{math\|l}}, and the element in position {{math\|l}} (where the previous iteration put original element {{math\|l}}-2) in position {{math\|l}}-1. To illustrate the above, look below for the case <math>n = 4~~</math>~~		If {{math\|l}} is odd, then, by the induction hypothesis, for an array A of length {{math\|l}}, <code>permutations(l, A)</code> will not change A, and for the claim to hold for arrays of length {{math\|l}}+1 (which is even), we need to show that <code>permutations(l+1, A)</code> rotates A to the right by 1 position. Doing <code>permutations(l+1, A)</code> will first do <code>permutations(l, A)</code> (leaving A unchanged since {{math\|l}} is odd) and then in each iteration {{math\|i}} of the for-loop, swap the elements in positions {{math\|i}} and {{math\|l}} (the last position) in A. The first swap puts element {{math\|l}} (the last element) in position 0, and element 0 in position {{math\|l}}. The next swap puts the element in position {{math\|l}} (where the previous iteration put original element 0) in position 1 and element 1 in position {{math\|l}}. In the final iteration, the swap puts element {{math\|l}}-1 is in position {{math\|l}}, and the element in position {{math\|l}} (where the previous iteration put original element {{math\|l}}-2) in position {{math\|l}}-1. To illustrate the above, look below for the case {{math\|n}} = 4.

	<pre>		<pre>
	1,2,3,4 ... ~~Original~~ ~~Array~~		1,2,3,4 ... original array
	1,2,3,4 ... 1st iteration (~~Permute~~ ~~subset~~)		1,2,3,4 ... 1st iteration (permute subarray)
	4,2,3,1 ... 1st iteration (~~Swap~~ 1st element into ~~"buffer"~~)		4,2,3,1 ... 1st iteration (swap 1st element into last position)
	4,2,3,1 ... 2nd iteration (~~Permute~~ ~~subset~~)		4,2,3,1 ... 2nd iteration (permute subarray)
	4,1,3,2 ... 2nd iteration (~~Swap~~ 2nd element into ~~"buffer"~~)		4,1,3,2 ... 2nd iteration (swap 2nd element into last position)
	4,1,3,2 ... 3rd iteration (~~Permute~~ ~~subset~~)		4,1,3,2 ... 3rd iteration (permute subarray)
	4,1,2,3 ... 3rd iteration (~~Swap~~ 3rd element into ~~"buffer"~~)		4,1,2,3 ... 3rd iteration (swap 3rd element into last position)
	4,1,2,3 ... 4th iteration (~~Permute~~ ~~subset~~)		4,1,2,3 ... 4th iteration (permute subarray)
	4,1,2,3 ... 4th iteration (~~Swap~~ 4th element into ~~"buffer"~~) ~~...~~ The altered array is a rotated version of the original		4,1,2,3 ... 4th iteration (swap 4th element into last position)
			The altered array is a rotated version of the original
	</pre>		</pre>

	If, for {{~~mvar~~\|A}}, <~~math~~>~~n=i+1~~</~~math~~> is ~~odd,~~ ~~then~~ the ~~subset~~ of the ~~first~~ {{~~mvar~~\|i}} ~~elements~~ ~~will~~ be ~~rotated~~ ~~after~~ ~~performing~~ ~~Heap's~~ ~~Algorithm~~ on ~~the~~ ~~first~~ ~~{{mvar\|i}}~~ ~~elements~~. ~~Notice~~ ~~that~~, ~~after~~ 1 iteration of the for-loop, ~~when~~ ~~performing~~ ~~Heap's~~ ~~Algorithm~~ on {{~~mvar~~\|A}}, {{~~mvar~~\|A}} is ~~rotated~~ to the ~~right~~ by 1. By ~~the~~ ~~induction~~ ~~hypothesis,~~ it is ~~assumed~~ ~~that~~ the first {{~~mvar~~\|i}} elements ~~will~~ ~~rotate.~~ ~~After this rotation,~~ the first ~~element~~ of ~~{{mvar\|A}}~~ ~~will~~ be ~~swapped~~ ~~into~~ the ~~buffer~~ ~~which,~~ ~~when~~ ~~combined~~ ~~with~~ ~~the~~ ~~previous~~ ~~rotation~~ ~~operation,~~ ~~will~~ in ~~essence~~ ~~perform~~ a ~~rotation~~ on the array. ~~Perform~~ ~~this~~ ~~rotation~~ ~~operation~~ ~~{{mvar\|n}}~~ ~~times,~~ ~~and~~ ~~the~~ ~~array will revert~~ to ~~its~~ ~~original~~ ~~state~~. ~~This~~ is ~~illustrated~~ below for the case <math>n = 5~~</math>~~.		If {{math\|l}} is even, then, by the induction hypothesis, for an array A of length {{math\|l}}, <code>permutations(l, A)</code> rotates A to the right by 1 position, and for the claim to hold for arrays of length {{math\|l}}+1 (which is odd), we need to show that <code>permutations(l+1, A)</code> leaves A unchanged. Doing <code>permutations(l+1, A)</code> will in each iteration {{math\|i}} of the for-loop, first do <code>permutations(l, A)</code> (rotating the first {{math\|l}} elements of A by 1 position since {{math\|l}} is even) and then, swap the elements in positions 0 and {{math\|l}} (the last position) in A. Rotating the first {{math\|l}} elements and then swapping the first and last elements is equivalent to rotating the entire array. Since there are as many iterations of the loop as there are elements in the array, the entire array is rotated until each element returns to where it started. To illustrate the above, look below for the case {{math\|n}} = 5.
	<pre>		<pre>
	1,2,3,4,5 ... ~~Original~~ ~~Array~~		1,2,3,4,5 ... original array
	4,1,2,3,5 ... 1st iteration (~~Permute~~ ~~subset/Rotate~~ ~~subset~~)		4,1,2,3,5 ... 1st iteration (permute subarray, which rotates it)
	5,1,2,3,4 ... 1st iteration (~~Swap~~)		5,1,2,3,4 ... 1st iteration (swap)
	3,5,1,2,4 ... 2nd iteration (~~Permute~~ ~~subset/Rotate~~ ~~subset~~)		3,5,1,2,4 ... 2nd iteration (permute subarray, which rotates it)
	4,5,1,2,3 ... 2nd iteration (~~Swap~~)		4,5,1,2,3 ... 2nd iteration (swap)
	2,4,5,1,3 ... 3rd iteration (~~Permute~~ ~~subset/Rotate~~ ~~subset~~)		2,4,5,1,3 ... 3rd iteration (permute subarray, which rotates it)
	3,4,5,1,2 ... 3rd iteration (~~Swap~~)		3,4,5,1,2 ... 3rd iteration (swap)
	1,3,4,5,2 ... 4th iteration (~~Permute~~ ~~subset/Rotate~~ ~~subset~~)		1,3,4,5,2 ... 4th iteration (permute subarray, which rotates it)
	2,3,4,5,1 ... 4th iteration (~~Swap~~)		2,3,4,5,1 ... 4th iteration (swap)
	5,2,3,4,1 ... 5th iteration (~~Permute~~ ~~subset/Rotate~~ ~~subset~~)		5,2,3,4,1 ... 5th iteration (permute subarray, which rotates it)
	1,2,3,4,5 ... 5th iteration (~~Swap~~) ~~...~~ The final state of the array is in the same order as the original		1,2,3,4,5 ... 5th iteration (swap)
			The final state of the array is in the same order as the original
	</pre>		</pre>

MarSch: /* Proof */ make first case of induction more clear

2025-01-06T11:21:56Z

Proof: make first case of induction more clear

← Previous revision		Revision as of 11:21, 6 January 2025
Line 94:		Line 94:
	</syntaxhighlight>		</syntaxhighlight>

	Claim: If array ~~{{mvar\|~~A}} has length {{mvar\|n}}, then <code>permutations(n, A)</code> will result in ~~one~~ of ~~two~~ ~~possibilities.~~ If {{mvar\|n}} is odd, ~~then {{mvar\|A}} is unaltered.~~ If {{mvar\|n}} is even, then ~~{{mvar\|~~A}} is "rotated" to the right by 1 (last element shifted in front of other elements).		Claim: If array A has length {{mvar\|n}}, then <code>permutations(n, A)</code> will result in either A being unchanged, if {{mvar\|n}} is odd, or, if {{mvar\|n}} is even, then A is rotated to the right by 1 (last element shifted in front of other elements).

	Basis: If array {{mvar\|A}} has length 1, then <code>permutations(1, A)</code> will output A and stop, so A is ~~unaltered~~. Since 1 is odd, this is what was claimed, so the claim ~~holds~~.		Basis: If array {{mvar\|A}} has length 1, then <code>permutations(1, A)</code> will output A and stop, so A is unchanged. Since 1 is odd, this is what was claimed, so the claim is true for arrays of length 1.

	Induction: ~~Assume~~ the claim ~~holds~~ true for ~~some~~ ~~<math>i~~ ~~\geq~~ ~~1</~~math>. We ~~will~~ then ~~need~~ to ~~handle~~ ~~two~~ ~~cases~~ for <math>i+1~~</math>:~~ <math~~>i+1</math>~~ is ~~even~~ or ~~odd~~.		Induction: If the claim is true for arrays of length {{math\|l}} ≥ 1, then we show that the claim is true for arrays of length {{math\|l}}+1 (together with the base case this proves that the claim is true for arrays of all lengths). Since the claim depends on whether {{math\|l}} is odd or even, we prove each case separately.

			If {{math\|l}} is odd, then, by the induction hypothesis, for an array A of length {{math\|l}}, <code>permutations(l, A)</code> will not change A, and for the claim to hold for arrays of length {{math\|l}}+1, we need to show that <code>permutations(l+1, A)</code> rotates A to the right by 1. Doing <code>permutations(l+1, A)</code> will first do <code>permutations(l, A)</code> (leaving A unchanged since {{math\|l}} is odd) and then in each iteration {{math\|i}} of the for-loop, swap the elements in positions {{math\|i}} and {{math\|l}} (the last position) in A. The first swap puts element {{math\|l}} (the last element) in position 0, and element 0 in position {{math\|l}}. The next swap puts the element in position {{math\|l}} (where the previous iteration put original element 0) in position 1 and element 1 in position {{math\|l}}. In the final iteration, the swap puts element {{math\|l}}-1 is in position {{math\|l}}, and the element in position {{math\|l}} (where the previous iteration put original element {{math\|l}}-2) in position {{math\|l}}-1. To illustrate the above, look below for the case <math>n = 4</math>

	If, for {{mvar\|A}}, <math>n=i+1</math> is even, then the subset of the first {{mvar\|i}} elements will remain unaltered after performing Heap's Algorithm on the subarray, as assumed by the induction hypothesis. By performing Heap's Algorithm on the subarray and then performing the swapping operation, in the {{mvar\|k}}th iteration of the for-loop, where <math>k \leq i+1</math>, the {{mvar\|k}}th element in {{mvar\|A}} will be swapped into the last position of {{mvar\|A}} which can be thought as a kind of "buffer". By swapping the 1st and last element, then swapping 2nd and last, all the way until the {{mvar\|n}}th and last elements are swapped, the array will at last experience a rotation. To illustrate the above, look below for the case <math>n = 4</math>
	<pre>		<pre>
	1,2,3,4 ... Original Array		1,2,3,4 ... Original Array

MarSch: /* Proof */ include preconditions and proper way to call algorithm, make claim more precise and explain base case

2025-01-06T10:04:55Z

Proof: include preconditions and proper way to call algorithm, make claim more precise and explain base case

← Previous revision		Revision as of 10:04, 6 January 2025
Line 71:		Line 71:

	==Proof==		==Proof==
	In this proof, we'll use the ~~implementation~~ below as Heap's ~~Algorithm~~. While it is not optimal (it does not minimize moves, which is described in the section below), the implementation is ~~nevertheless still~~ correct and will produce all permutations~~. The reason for using the below implementation is that the analysis is easier, and certain patterns can be easily illustrated~~.		In this proof, we'll use the below implementation as Heap's algorithm as it makes the analysis easier, and certain patterns can be easily illustrated. While it is not optimal (it does not minimize moves, which is described in the section below), the implementation is correct and will produce all permutations.
	<syntaxhighlight lang="pascal">		<syntaxhighlight lang="pascal">
			// Output the k! permutations of A in which the first k elements are permuted in all ways.
⚫	procedure ~~generate~~(k : integer, A : array of any):
			// To get all permutations of A, use k := length of A.
			//
			// If, k > length of A, will try to access A out of bounds.
			// If k <= 0 there will be no output (empty array has no permutations)
		⚫	procedure permutations(k : integer, A : array of any):
	if k = 1 then		if k = 1 then
	output(A)		output(A)
	else		else
	for i := 0; i < k; i += 1 do		for i := 0; i < k; i += 1 do
	~~generate~~(k - 1, A)		permutations(k - 1, A)
	if k is even then		if k is even then
	swap(A[i], A[k-1])		swap(A[i], A[k-1])
Line 89:		Line 94:
	</syntaxhighlight>		</syntaxhighlight>

	Claim: If array {{mvar\|A}} has length {{mvar\|n}}, then ~~performing~~ ~~Heap's algorithm~~ will ~~either~~ result in {{mvar\|A}} ~~being~~ ~~"rotated"~~ to ~~the~~ ~~right~~ by 1 ~~(i.e.~~ ~~each~~ ~~element~~ is ~~shifted~~ to the right ~~with~~ ~~the~~ last element ~~occupying the first position) or result~~ in ~~{{mvar\|A}}~~ ~~being~~ ~~unaltered,~~ ~~depending on if {{mvar\|n}} is even or odd, respectively~~.		Claim: If array {{mvar\|A}} has length {{mvar\|n}}, then <code>permutations(n, A)</code> will result in one of two possibilities. If {{mvar\|n}} is odd, then {{mvar\|A}} is unaltered. If {{mvar\|n}} is even, then {{mvar\|A}} is "rotated" to the right by 1 (last element shifted in front of other elements).

			Basis: If array {{mvar\|A}} has length 1, then <code>permutations(1, A)</code> will output A and stop, so A is unaltered. Since 1 is odd, this is what was claimed, so the claim holds.
	Basis: The claim above trivially holds true for <math>n=1</math> as Heap's algorithm will simply return {{mvar\|A}} unaltered in order.

	Induction: Assume the claim holds true for some <math>i \geq 1</math>. We will then need to handle two cases for <math>i+1</math>: <math>i+1</math> is even or odd.		Induction: Assume the claim holds true for some <math>i \geq 1</math>. We will then need to handle two cases for <math>i+1</math>: <math>i+1</math> is even or odd.

MarSch: /* Proof */

2025-01-06T09:00:04Z

Proof

← Previous revision		Revision as of 09:00, 6 January 2025
Line 89:		Line 89:
	</syntaxhighlight>		</syntaxhighlight>

	Claim: If array {{mvar\|A}} has length {{mvar\|n}}, then performing Heap's algorithm will either result in {{mvar\|A}} being "rotated" to the right by 1 (i.e. each element is shifted to the right with the last element occupying the first position) or result in {{mvar\|A}} being unaltered, depending if {{mvar\|n}} is even or odd, respectively.		Claim: If array {{mvar\|A}} has length {{mvar\|n}}, then performing Heap's algorithm will either result in {{mvar\|A}} being "rotated" to the right by 1 (i.e. each element is shifted to the right with the last element occupying the first position) or result in {{mvar\|A}} being unaltered, depending on if {{mvar\|n}} is even or odd, respectively.

	Basis: The claim above trivially holds true for <math>n=1</math> as Heap's algorithm will simply return {{mvar\|A}} unaltered in order.		Basis: The claim above trivially holds true for <math>n=1</math> as Heap's algorithm will simply return {{mvar\|A}} unaltered in order.

2A01:799:913:BB00:4EFA:7411:67F6:D94A: // minor edit

2024-10-08T04:44:39Z

// minor edit

← Previous revision		Revision as of 04:44, 8 October 2024
Line 63:		Line 63:
	i := 1		i := 1
	else		else
	// Calling generate(i+1, A) has ended as the ~~for~~-loop terminated. Reset the state and simulate popping the stack by incrementing the pointer.		// Calling generate(i+1, A) has ended as the while-loop terminated. Reset the state and simulate popping the stack by incrementing the pointer.
	c[i] := 0		c[i] := 0
	i += 1		i += 1

2A01:799:913:BB00:4EFA:7411:67F6:D94A: // minor error in a comment

2024-10-08T04:43:29Z

// minor error in a comment

← Previous revision		Revision as of 04:43, 8 October 2024
Line 58:		Line 58:
	end if		end if
	output(A)		output(A)
	// Swap has occurred ending the ~~for~~-loop. Simulate the increment of the ~~for~~-loop counter		// Swap has occurred ending the while-loop. Simulate the increment of the while-loop counter
	c[i] += 1		c[i] += 1
	// Simulate recursive call reaching the base case by bringing the pointer to the base case analog in the array		// Simulate recursive call reaching the base case by bringing the pointer to the base case analog in the array

OAbot: Open access bot: doi updated in citation with #oabot.

2024-01-01T02:25:20Z

Open access bot: doi updated in citation with #oabot.

← Previous revision		Revision as of 02:25, 1 January 2024
Line 4:		Line 4:
	[[File:Wheel diagram Heap's algorithm.svg\|thumb\|Wheel diagram of all permutations of length <math>n=4</math> generated by Heap's algorithm, where each permutation is color-coded (1=blue, 2=green, 3=yellow, 4=red).]]		[[File:Wheel diagram Heap's algorithm.svg\|thumb\|Wheel diagram of all permutations of length <math>n=4</math> generated by Heap's algorithm, where each permutation is color-coded (1=blue, 2=green, 3=yellow, 4=red).]]

	'''Heap's [[algorithm]]''' generates all possible [[permutation]]s of {{math\|''n''}} objects. It was first proposed by B. R. Heap in 1963.<ref name="Heap">{{cite journal\|last=Heap\|first=B. R.\|title=Permutations by Interchanges\|journal=The Computer Journal\|year=1963\|volume=6\|issue=3\|pages=293–4\|doi=10.1093/comjnl/6.3.293\|doi-access=free}}</ref> The algorithm minimizes movement: it generates each permutation from the previous one by interchanging a single pair of elements; the other {{math\|''n''−2}} elements are not disturbed. In a 1977 review of permutation-generating algorithms, [[Robert Sedgewick (computer scientist)\|Robert Sedgewick]] concluded that it was at that time the most effective algorithm for generating permutations by computer.<ref>{{Cite journal \| last1 = Sedgewick \| first1 = R. \| title = Permutation Generation Methods \| doi = 10.1145/356689.356692 \| journal = ACM Computing Surveys \| volume = 9 \| issue = 2 \| pages = 137–164\| year = 1977 \| s2cid = 12139332 }}</ref>		'''Heap's [[algorithm]]''' generates all possible [[permutation]]s of {{math\|''n''}} objects. It was first proposed by B. R. Heap in 1963.<ref name="Heap">{{cite journal\|last=Heap\|first=B. R.\|title=Permutations by Interchanges\|journal=The Computer Journal\|year=1963\|volume=6\|issue=3\|pages=293–4\|doi=10.1093/comjnl/6.3.293\|doi-access=free}}</ref> The algorithm minimizes movement: it generates each permutation from the previous one by interchanging a single pair of elements; the other {{math\|''n''−2}} elements are not disturbed. In a 1977 review of permutation-generating algorithms, [[Robert Sedgewick (computer scientist)\|Robert Sedgewick]] concluded that it was at that time the most effective algorithm for generating permutations by computer.<ref>{{Cite journal \| last1 = Sedgewick \| first1 = R. \| title = Permutation Generation Methods \| doi = 10.1145/356689.356692 \| journal = ACM Computing Surveys \| volume = 9 \| issue = 2 \| pages = 137–164\| year = 1977 \| s2cid = 12139332 \| doi-access = free }}</ref>

	The [[sequence]] of permutations of {{math\|''n''}} objects generated by Heap's algorithm is the beginning of the sequence of permutations of {{math\|''n''+1}} objects. So there is one infinite sequence of permutations generated by Heap's algorithm {{OEIS\|A280318}}.		The [[sequence]] of permutations of {{math\|''n''}} objects generated by Heap's algorithm is the beginning of the sequence of permutations of {{math\|''n''+1}} objects. So there is one infinite sequence of permutations generated by Heap's algorithm {{OEIS\|A280318}}.

Kubanczyk: /* Proof */

2023-10-31T10:35:00Z

Proof

← Previous revision		Revision as of 10:35, 31 October 2023
Line 71:		Line 71:

	==Proof==		==Proof==
	In this proof, we'll use the implementation below as Heap's Algorithm. While it is not optimal (~~see~~ section below)~~{{Clarify\|date=March 2020}}~~, the implementation is nevertheless still correct and will produce all permutations. The reason for using the below implementation is that the analysis is easier, and certain patterns can be easily illustrated.		In this proof, we'll use the implementation below as Heap's Algorithm. While it is not optimal (it does not minimize moves, which is described in the section below), the implementation is nevertheless still correct and will produce all permutations. The reason for using the below implementation is that the analysis is easier, and certain patterns can be easily illustrated.
	<syntaxhighlight lang="pascal">		<syntaxhighlight lang="pascal">
	procedure generate(k : integer, A : array of any):		procedure generate(k : integer, A : array of any):

← Previous revision		Revision as of 02:25, 1 January 2024
Line 4:		Line 4:
	[[File:Wheel diagram Heap's algorithm.svg\|thumb\|Wheel diagram of all permutations of length <math>n=4</math> generated by Heap's algorithm, where each permutation is color-coded (1=blue, 2=green, 3=yellow, 4=red).]]		[[File:Wheel diagram Heap's algorithm.svg\|thumb\|Wheel diagram of all permutations of length <math>n=4</math> generated by Heap's algorithm, where each permutation is color-coded (1=blue, 2=green, 3=yellow, 4=red).]]

	'''Heap's [[algorithm]]''' generates all possible [[permutation]]s of {{math\|''n''}} objects. It was first proposed by B. R. Heap in 1963.<ref name="Heap">{{cite journal\|last=Heap\|first=B. R.\|title=Permutations by Interchanges\|journal=The Computer Journal\|year=1963\|volume=6\|issue=3\|pages=293–4\|doi=10.1093/comjnl/6.3.293\|doi-access=free}}</ref> The algorithm minimizes movement: it generates each permutation from the previous one by interchanging a single pair of elements; the other {{math\|''n''−2}} elements are not disturbed. In a 1977 review of permutation-generating algorithms, [[Robert Sedgewick (computer scientist)\|Robert Sedgewick]] concluded that it was at that time the most effective algorithm for generating permutations by computer.<ref>{{Cite journal \| last1 = Sedgewick \| first1 = R. \| title = Permutation Generation Methods \| doi = 10.1145/356689.356692 \| journal = ACM Computing Surveys \| volume = 9 \| issue = 2 \| pages = 137–164\| year = 1977 \| s2cid = 12139332 }}</ref>		'''Heap's [[algorithm]]''' generates all possible [[permutation]]s of {{math\|''n''}} objects. It was first proposed by B. R. Heap in 1963.<ref name="Heap">{{cite journal\|last=Heap\|first=B. R.\|title=Permutations by Interchanges\|journal=The Computer Journal\|year=1963\|volume=6\|issue=3\|pages=293–4\|doi=10.1093/comjnl/6.3.293\|doi-access=free}}</ref> The algorithm minimizes movement: it generates each permutation from the previous one by interchanging a single pair of elements; the other {{math\|''n''−2}} elements are not disturbed. In a 1977 review of permutation-generating algorithms, [[Robert Sedgewick (computer scientist)\|Robert Sedgewick]] concluded that it was at that time the most effective algorithm for generating permutations by computer.<ref>{{Cite journal \| last1 = Sedgewick \| first1 = R. \| title = Permutation Generation Methods \| doi = 10.1145/356689.356692 \| journal = ACM Computing Surveys \| volume = 9 \| issue = 2 \| pages = 137–164\| year = 1977 \| s2cid = 12139332 \| doi-access = free }}</ref>

	The [[sequence]] of permutations of {{math\|''n''}} objects generated by Heap's algorithm is the beginning of the sequence of permutations of {{math\|''n''+1}} objects. So there is one infinite sequence of permutations generated by Heap's algorithm {{OEIS\|A280318}}.		The [[sequence]] of permutations of {{math\|''n''}} objects generated by Heap's algorithm is the beginning of the sequence of permutations of {{math\|''n''+1}} objects. So there is one infinite sequence of permutations generated by Heap's algorithm {{OEIS\|A280318}}.