FilesExpand file tree

Factorial

/

heaps_algorithm.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

56 lines (46 loc) · 1.5 KB

Factorial

/

heaps_algorithm.py

Copy path

Top

File metadata and controls

• Code
• Blame

56 lines (46 loc) · 1.5 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

"""

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.

"""

def 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

"""

if len(arr) <= 1:

return [tuple(arr)]

res = []

def generate(k: int, arr: list):

if k == 1:

res.append(tuple(arr[:]))

return

generate(k - 1, arr)

for i in range(k - 1):

if k % 2 == 0: # k is even

arr[i], arr[k - 1] = arr[k - 1], arr[i]

else: # k is odd

arr[0], arr[k - 1] = arr[k - 1], arr[0]

generate(k - 1, arr)

generate(len(arr), arr)

return res

if __name__ == "__main__":

user_input = input("Enter numbers separated by a comma:\n").strip()

arr = [int(item) for item in user_input.split(",")]

print(heaps(arr))