Skip to content

Instantly share code, notes, and snippets.

@andyg0808

andyg0808/heaps.py

Created May 31, 2020
Embed
What would you like to do?
Heap's algorithm in Python
from typing import List
def swap(A, i, j):
temp = A[i]
A[i] = A[j]
A[j] = temp
def generate(k: int, A: List):
if k == 1:
return [A.copy()]
else:
res = generate(k - 1, A)
for i in range(k - 1):
if k % 2 == 0:
swap(A, i, k - 1)
else:
swap(A, 0, k - 1)
res = res + generate(k - 1, A)
return res
def yield_generate(k: int, A: List):
if k == 1:
yield A.copy()
else:
yield from generate(k - 1, A)
for i in range(k - 1):
if k % 2 == 0:
swap(A, i, k - 1)
else:
swap(A, 0, k - 1)
yield from generate(k - 1, A)
l = list(range(14))
val = yield_generate(len(l), l)
for i in val:
print(i)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment