/
NikolayIvkin
/
TheAlgorithms_Python
Обзор
Документация
Войти
/
NikolayIvkin
/
TheAlgorithms_Python
Код
Запросы
2
Задачи
Вики
Пакеты
0
Релизы
0
Аналитика
Безопасность
master
divide_and_conquer/heaps_algorithm_iterative.py
60 строк
2 KB
Guillaume Rochedix
Heaps algorithm iterative (#2505)
29 сен 2020, 13:38
Не верифицирован
29 сен 2020, 13:38
04322e6
Код
Авторство
О чём код?
""" Heap's (iterative) 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 iterative Heap's algorithm, 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(n: int, arr: list): c = [0] * n res.append(tuple(arr)) i = 0 while i < n: if c[i] < i: if i % 2 == 0: arr[0], arr[i] = arr[i], arr[0] else: arr[c[i]], arr[i] = arr[i], arr[c[i]] res.append(tuple(arr)) c[i] += 1 i = 0 else: c[i] = 0 i += 1 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))