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 orgwikiheap27salgorithm pure python implementation of the iterative heap s algorithm returning all permutations of a list heaps heaps0 0 heaps1 1 1 1 1 1 heaps1 2 3 1 2 3 2 1 3 3 1 2 1 3 2 2 3 1 3 2 1 from itertools import permutations sortedheaps1 2 3 sortedpermutations1 2 3 true allsortedheapsx sortedpermutationsx for x in 0 1 1 1 2 3 true 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
def heaps(arr: list) -> list:
    

    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))