divide_and_conquer.heaps_algorithm

Heap’s algorithm returns the list of all permutations possible from a list. It minimizes movement by generating each permutation from the previous one by swapping only two elements. More information: https://en.wikipedia.org/wiki/Heap%27s_algorithm.

Attributes

user_input

Functions

heaps(→ list)

Pure python implementation of the Heap's algorithm (recursive version),

Module Contents

divide_and_conquer.heaps_algorithm.heaps(arr: list) → list

Pure python implementation of the Heap’s algorithm (recursive version), returning all permutations of a list. >>> heaps([]) [()] >>> heaps([0]) [(0,)] >>> heaps([-1, 1]) [(-1, 1), (1, -1)] >>> heaps([1, 2, 3]) [(1, 2, 3), (2, 1, 3), (3, 1, 2), (1, 3, 2), (2, 3, 1), (3, 2, 1)] >>> from itertools import permutations >>> sorted(heaps([1,2,3])) == sorted(permutations([1,2,3])) True >>> all(sorted(heaps(x)) == sorted(permutations(x)) … for x in ([], [0], [-1, 1], [1, 2, 3])) True

divide_and_conquer.heaps_algorithm.user_input