-1
____________end_if
________end_for
____end_if
Claim:_If_array__has_length_,_then_performing_Heap's_algorithm_will_either_result_in__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__being_unaltered,_depending_if__is_even_or_odd,_respectively.
Basis:_The_claim_above_trivially_holds_true_for__as_Heap's_algorithm_will_simply_return__unaltered_in_order.
Induction:_Assume_the_claim_holds_true_for_some_._We_will_then_need_to_handle_two_cases_for_:__is_even_or_odd.
If,_for_,__is_even,_then_the_subset_of_the_first__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_th_iteration_of_the_for-loop,_where_,_the_th_element_in__will_be_swapped_into_the_last_position_of__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_th_and_last_elements_are_swapped,_the_array_will_at_last_experience_a_rotation._To_illustrate_the_above,_look_below_for_the_case_
1,2,3,4_..._Original_Array
1,2,3,4_..._1st_iteration_(Permute_subset)
4,2,3,1_..._1st_iteration_(Swap_1st_element_into_"buffer")
4,2,3,1_..._2nd_iteration_(Permute_subset)
4,1,3,2_..._2nd_iteration_(Swap_2nd_element_into_"buffer")
4,1,3,2_..._3rd_iteration_(Permute_subset)
4,1,2,3_..._3rd_iteration_(Swap_3rd_element_into_"buffer")
4,1,2,3_..._4th_iteration_(Permute_subset)
4,1,2,3_..._4th_iteration_(Swap_4th_element_into_"buffer")_..._The_altered_array_is_a_rotated_version_of_the_original
If,_for_,__is_odd,_then_the_subset_of_the_first__elements_will_be_rotated_after_performing_Heap's_Algorithm_on_the_first__elements._Notice_that,_after_1_iteration_of_the_for-loop,_when_performing_Heap's_Algorithm_on_,__is_rotated_to_the_right_by_1._By_the_induction_hypothesis,_it_is_assumed_that_the_first__elements_will_rotate._After_this_rotation,_the_first_element_of__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__times,_and_the_array_will_revert_to_its_original_state._This_is_illustrated_below_for_the_case_.
1,2,3,4,5_..._Original_Array
4,1,2,3,5_..._1st_iteration_(Permute_subset/Rotate_subset)
5,1,2,3,4_..._1st_iteration_(Swap)
3,5,1,2,4_..._2nd_iteration_(Permute_subset/Rotate_subset)
4,5,1,2,3_..._2nd_iteration_(Swap)
2,4,5,1,3_..._3rd_iteration_(Permute_subset/Rotate_subset)
3,4,5,1,2_..._3rd_iteration_(Swap)
1,3,4,5,2_..._4th_iteration_(Permute_subset/Rotate_subset)
2,3,4,5,1_..._4th_iteration_(Swap)
5,2,3,4,1_..._5th_iteration_(Permute_subset/Rotate_subset)
1,2,3,4,5_..._5th_iteration_(Swap)_..._The_final_state_of_the_array_is_in_the_same_order_as_the_original
The_induction_proof_for_the_claim_is_now_complete,_which_will_now_lead_to_why_Heap's_Algorithm_creates_all_permutations_of_array_._Once_again_we_will_prove_by_induction_the_correctness_of_Heap's_Algorithm.
Basis:_Heap's_Algorithm_trivially_permutes_an_array__of_size__as_outputting__is_the_one_and_only_permutation_of_.
Induction:_Assume_Heap's_Algorithm_permutes_an_array_of_size_._Using_the_results_from_the_previous_proof,_every_element_of__will_be_in_the_"buffer"_once_when_the_first__elements_are_permuted._Because_permutations_of_an_array_can_be_made_by_altering_some_array__through_the_removal_of_an_element__from__then_tacking_on__to_each_permutation_of_the_altered_array,_it_follows_that_Heap's_Algorithm_permutes_an_array_of_size_,_for_the_"buffer"_in_essence_holds_the_removed_element,_being_tacked_onto_the_permutations_of_the_subarray_of_size_._Because_each_iteration_of_Heap's_Algorithm_has_a_different_element_of__occupying_the_buffer_when_the_subarray_is_permuted,_every_permutation_is_generated_as_each_element_of__has_a_chance_to_be_tacked_onto_the_permutations_of_the_array__without_the_buffer_element.
_Frequent_mis-implementations
It_is_tempting_to_simplify_the_recursive_version_given_above_by_reducing_the_instances_of_recursive_calls._For_example,_as:
procedure_generate(k_:_integer,_A_:_array_of_any):
____if_k_=_1_then
________output(A)
____else
________//_Recursively_call_once_for_each_k
________for_i_:=_0;_i_<_k;_i_+=_1_do
____________generate(k_-_1,_A)
____________//_swap_choice_dependent_on_parity_of_k_(even_or_odd)
____________if_k_is_even_then
________________//_no-op_when_i__k-1
________________swap(A__A_-1
____________else
________________//_XXX_incorrect_additional_swap_when_ik-1
________________swap(A__A_-1_
____________end_if
________end_for
____end_if
This_implementation_will_succeed_in_producing_all_permutations_but_does_not_minimize_movement._As_the_recursive_ [i,_A_
____________end_if
____________output(A)
____________//_Swap_has_occurred_ending_the_for-loop._Simulate_the_increment_of_the_for-loop_counter
____________c_+=_1
____________//_Simulate_recursive_call_reaching_the_base_case_by_bringing_the_pointer_to_the_base_case_analog_in_the_array
____________i_:=_1
________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.
____________c_:=_0
____________i_+=_1
________end_if
____end_while
_Proof
In_this_proof,_we'll_use_the_implementation_below_as_Heap's_Algorithm._While_it_is_not_optimal_(see_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.
procedure_generate(k_:_integer,_A_:_array_of_any):
____if_k_=_1_then
________output(A)
____else
________for_i_:=_0;_i_<_k;_i_+=_1_do
____________generate(k_-_1,_A)
____________if_k_is_even_then
________________swap(A__A_-1
____________else
________________swap(A__A_-1
____________end_if
________end_for
____end_if
Claim:_If_array__has_length_,_then_performing_Heap's_algorithm_will_either_result_in__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__being_unaltered,_depending_if__is_even_or_odd,_respectively.
Basis:_The_claim_above_trivially_holds_true_for__as_Heap's_algorithm_will_simply_return__unaltered_in_order.
Induction:_Assume_the_claim_holds_true_for_some_._We_will_then_need_to_handle_two_cases_for_:__is_even_or_odd.
If,_for_,__is_even,_then_the_subset_of_the_first__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_th_iteration_of_the_for-loop,_where_,_the_th_element_in__will_be_swapped_into_the_last_position_of__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_th_and_last_elements_are_swapped,_the_array_will_at_last_experience_a_rotation._To_illustrate_the_above,_look_below_for_the_case_
1,2,3,4_..._Original_Array
1,2,3,4_..._1st_iteration_(Permute_subset)
4,2,3,1_..._1st_iteration_(Swap_1st_element_into_"buffer")
4,2,3,1_..._2nd_iteration_(Permute_subset)
4,1,3,2_..._2nd_iteration_(Swap_2nd_element_into_"buffer")
4,1,3,2_..._3rd_iteration_(Permute_subset)
4,1,2,3_..._3rd_iteration_(Swap_3rd_element_into_"buffer")
4,1,2,3_..._4th_iteration_(Permute_subset)
4,1,2,3_..._4th_iteration_(Swap_4th_element_into_"buffer")_..._The_altered_array_is_a_rotated_version_of_the_original
If,_for_,__is_odd,_then_the_subset_of_the_first__elements_will_be_rotated_after_performing_Heap's_Algorithm_on_the_first__elements._Notice_that,_after_1_iteration_of_the_for-loop,_when_performing_Heap's_Algorithm_on_,__is_rotated_to_the_right_by_1._By_the_induction_hypothesis,_it_is_assumed_that_the_first__elements_will_rotate._After_this_rotation,_the_first_element_of__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__times,_and_the_array_will_revert_to_its_original_state._This_is_illustrated_below_for_the_case_.
1,2,3,4,5_..._Original_Array
4,1,2,3,5_..._1st_iteration_(Permute_subset/Rotate_subset)
5,1,2,3,4_..._1st_iteration_(Swap)
3,5,1,2,4_..._2nd_iteration_(Permute_subset/Rotate_subset)
4,5,1,2,3_..._2nd_iteration_(Swap)
2,4,5,1,3_..._3rd_iteration_(Permute_subset/Rotate_subset)
3,4,5,1,2_..._3rd_iteration_(Swap)
1,3,4,5,2_..._4th_iteration_(Permute_subset/Rotate_subset)
2,3,4,5,1_..._4th_iteration_(Swap)
5,2,3,4,1_..._5th_iteration_(Permute_subset/Rotate_subset)
1,2,3,4,5_..._5th_iteration_(Swap)_..._The_final_state_of_the_array_is_in_the_same_order_as_the_original
The_induction_proof_for_the_claim_is_now_complete,_which_will_now_lead_to_why_Heap's_Algorithm_creates_all_permutations_of_array_._Once_again_we_will_prove_by_induction_the_correctness_of_Heap's_Algorithm.
Basis:_Heap's_Algorithm_trivially_permutes_an_array__of_size__as_outputting__is_the_one_and_only_permutation_of_.
Induction:_Assume_Heap's_Algorithm_permutes_an_array_of_size_._Using_the_results_from_the_previous_proof,_every_element_of__will_be_in_the_"buffer"_once_when_the_first__elements_are_permuted._Because_permutations_of_an_array_can_be_made_by_altering_some_array__through_the_removal_of_an_element__from__then_tacking_on__to_each_permutation_of_the_altered_array,_it_follows_that_Heap's_Algorithm_permutes_an_array_of_size_,_for_the_"buffer"_in_essence_holds_the_removed_element,_being_tacked_onto_the_permutations_of_the_subarray_of_size_._Because_each_iteration_of_Heap's_Algorithm_has_a_different_element_of__occupying_the_buffer_when_the_subarray_is_permuted,_every_permutation_is_generated_as_each_element_of__has_a_chance_to_be_tacked_onto_the_permutations_of_the_array__without_the_buffer_element.
_Frequent_mis-implementations
It_is_tempting_to_simplify_the_recursive_version_given_above_by_reducing_the_instances_of_recursive_calls._For_example,_as:
procedure_generate(k_:_integer,_A_:_array_of_any):
____if_k_=_1_then
________output(A)
____else
________//_Recursively_call_once_for_each_k
________for_i_:=_0;_i_<_k;_i_+=_1_do
____________generate(k_-_1,_A)
____________//_swap_choice_dependent_on_parity_of_k_(even_or_odd)
____________if_k_is_even_then
________________//_no-op_when_i__k-1
________________swap(A__A_-1
____________else
________________//_XXX_incorrect_additional_swap_when_ik-1
________________swap(A__A_-1_
____________end_if
________end_for
____end_if
This_implementation_will_succeed_in_producing_all_permutations_but_does_not_minimize_movement._As_the_recursive_Call_stack">call-stacks_unwind,_it_results_in_additional_swaps_at_each_level._Half_of_these_will_be_Null_function.html" ;"title="Call_stack.html" ;"title=".html" ;"title="[i">[i, A
end if
output(A)
// Swap has occurred ending the for-loop. Simulate the increment of the for-loop counter
c += 1
// Simulate recursive call reaching the base case by bringing the pointer to the base case analog in the array
i := 1
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.
c := 0
i += 1
end if
end while
Proof
In this proof, we'll use the implementation below as Heap's Algorithm. While it is not optimal (see 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.
procedure generate(k : integer, A : array of any):
if k = 1 then
output(A)
else
for i := 0; i < k; i += 1 do
generate(k - 1, A)
if k is even then
swap(A A -1
else
swap(A A -1
end if
end for
end if
Claim: If array has length , then performing Heap's algorithm will either result in 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 being unaltered, depending if is even or odd, respectively.
Basis: The claim above trivially holds true for as Heap's algorithm will simply return unaltered in order.
Induction: Assume the claim holds true for some . We will then need to handle two cases for : is even or odd.
If, for , is even, then the subset of the first 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 th iteration of the for-loop, where , the th element in will be swapped into the last position of 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 th and last elements are swapped, the array will at last experience a rotation. To illustrate the above, look below for the case
1,2,3,4 ... Original Array
1,2,3,4 ... 1st iteration (Permute subset)
4,2,3,1 ... 1st iteration (Swap 1st element into "buffer")
4,2,3,1 ... 2nd iteration (Permute subset)
4,1,3,2 ... 2nd iteration (Swap 2nd element into "buffer")
4,1,3,2 ... 3rd iteration (Permute subset)
4,1,2,3 ... 3rd iteration (Swap 3rd element into "buffer")
4,1,2,3 ... 4th iteration (Permute subset)
4,1,2,3 ... 4th iteration (Swap 4th element into "buffer") ... The altered array is a rotated version of the original
If, for , is odd, then the subset of the first elements will be rotated after performing Heap's Algorithm on the first elements. Notice that, after 1 iteration of the for-loop, when performing Heap's Algorithm on , is rotated to the right by 1. By the induction hypothesis, it is assumed that the first elements will rotate. After this rotation, the first element of 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 times, and the array will revert to its original state. This is illustrated below for the case .
1,2,3,4,5 ... Original Array
4,1,2,3,5 ... 1st iteration (Permute subset/Rotate subset)
5,1,2,3,4 ... 1st iteration (Swap)
3,5,1,2,4 ... 2nd iteration (Permute subset/Rotate subset)
4,5,1,2,3 ... 2nd iteration (Swap)
2,4,5,1,3 ... 3rd iteration (Permute subset/Rotate subset)
3,4,5,1,2 ... 3rd iteration (Swap)
1,3,4,5,2 ... 4th iteration (Permute subset/Rotate subset)
2,3,4,5,1 ... 4th iteration (Swap)
5,2,3,4,1 ... 5th iteration (Permute subset/Rotate subset)
1,2,3,4,5 ... 5th iteration (Swap) ... The final state of the array is in the same order as the original
The induction proof for the claim is now complete, which will now lead to why Heap's Algorithm creates all permutations of array . Once again we will prove by induction the correctness of Heap's Algorithm.
Basis: Heap's Algorithm trivially permutes an array of size as outputting is the one and only permutation of .
Induction: Assume Heap's Algorithm permutes an array of size . Using the results from the previous proof, every element of will be in the "buffer" once when the first elements are permuted. Because permutations of an array can be made by altering some array through the removal of an element from then tacking on to each permutation of the altered array, it follows that Heap's Algorithm permutes an array of size , for the "buffer" in essence holds the removed element, being tacked onto the permutations of the subarray of size . Because each iteration of Heap's Algorithm has a different element of occupying the buffer when the subarray is permuted, every permutation is generated as each element of has a chance to be tacked onto the permutations of the array without the buffer element.
Frequent mis-implementations
It is tempting to simplify the recursive version given above by reducing the instances of recursive calls. For example, as:
procedure generate(k : integer, A : array of any):
if k = 1 then
output(A)
else
// Recursively call once for each k
for i := 0; i < k; i += 1 do
generate(k - 1, A)
// swap choice dependent on parity of k (even or odd)
if k is even then
// no-op when i k-1
swap(A A -1
else
// XXX incorrect additional swap when ik-1
swap(A A -1
end if
end for
end if
This implementation will succeed in producing all permutations but does not minimize movement. As the recursive Call stack">call-stacks unwind, it results in additional swaps at each level. Half of these will be Null function">no-ops of and where but when is odd, it results in additional swaps of the with the element.
These additional swaps significantly alter the order of the prefix elements.
The additional swaps can be avoided by either adding an additional recursive call before the loop and looping times (as above) or looping times and checking that is less than as in:
procedure generate(k : integer, A : array of any):
if k = 1 then
output(A)
else
// Recursively call once for each k
for i := 0; i < k; i += 1 do
generate(k - 1, A)
// avoid swap when ik-1
if (i < k - 1)
// swap choice dependent on parity of k
if k is even then
swap(A A -1
else
swap(A A -1
end if
end if
end for
end if
The choice is primarily aesthetic but the latter results in checking the value of twice as often.
See also
* Steinhaus–Johnson–Trotter algorithm
References
{{Reflist
Combinatorial algorithms
Permutations