Algorithm to create permutations, including omissions

Here's a simple implementation of Heap's algorithm in Python, written as a generator. It might not be the presentation you're used to, since it uses a mid-tested loop, which was how it was initially presented by Robert Sedgewick, but it has exactly the same sequence of steps. (Unfortunately, Python doesn't have a mid-tested loop construct, so this version has a useless test at the beginning as well.)

def heap_perm(it):
    def helper(n):
        if n == 0:
            yield A[:]
        else:
            for i in range(n):
                yield from helper(n-1)
                if i < n - 1:
                    if n % 2:
                        A[0], A[n-1] = A[n-1], A[0]
                    else:
                        A[i], A[n-1] = A[n-1], A[i]

    A = list(it)
    yield from helper(len(A))

An important aspect of the order of permutations generated by this algorithm is that all the permutations with a particular suffix are output consecutively, regardless of the length of the suffix. So if we want all the suffixes as well, we just need to produce the suffix when we first encounter it, which is just before the recursion. If you put these two functions side by side, you'll see how similar they are.

def heap_subset_perm(it):
    def helper(n):
        for i in range(n):
            yield A[n-1:]
            yield from helper(n-1)
            if i < n - 1:
                if n % 2:
                    A[0], A[n-1] = A[n-1], A[0]
                else:
                    A[i], A[n-1] = A[n-1], A[i]

    A = list(it)
    yield from helper(len(A))

In the sample run, I right-justified the output so that the suffix property is more visible:

>>> for p in heap_subset_perm("abcd"):
...     print(f"{str(p):>20}")
... 
               ['d']
          ['c', 'd']
     ['b', 'c', 'd']
['a', 'b', 'c', 'd']
     ['a', 'c', 'd']
['b', 'a', 'c', 'd']
          ['b', 'd']
     ['a', 'b', 'd']
['c', 'a', 'b', 'd']
     ['c', 'b', 'd']
['a', 'c', 'b', 'd']
          ['a', 'd']
     ['c', 'a', 'd']
['b', 'c', 'a', 'd']
     ['b', 'a', 'd']
['c', 'b', 'a', 'd']
               ['c']
          ['a', 'c']
     ['b', 'a', 'c']
['d', 'b', 'a', 'c']
     ['d', 'a', 'c']
['b', 'd', 'a', 'c']
          ['b', 'c']
     ['d', 'b', 'c']
['a', 'd', 'b', 'c']
     ['a', 'b', 'c']
['d', 'a', 'b', 'c']
          ['d', 'c']
     ['a', 'd', 'c']
['b', 'a', 'd', 'c']
     ['b', 'd', 'c']
['a', 'b', 'd', 'c']
               ['b']
          ['d', 'b']
     ['c', 'd', 'b']
['a', 'c', 'd', 'b']
     ['a', 'd', 'b']
['c', 'a', 'd', 'b']
          ['c', 'b']
     ['a', 'c', 'b']
['d', 'a', 'c', 'b']
     ['d', 'c', 'b']
['a', 'd', 'c', 'b']
          ['a', 'b']
     ['d', 'a', 'b']
['c', 'd', 'a', 'b']
     ['c', 'a', 'b']
['d', 'c', 'a', 'b']
               ['a']
          ['b', 'a']
     ['c', 'b', 'a']
['d', 'c', 'b', 'a']
     ['d', 'b', 'a']
['c', 'd', 'b', 'a']
          ['c', 'a']
     ['d', 'c', 'a']
['b', 'd', 'c', 'a']
     ['b', 'c', 'a']
['d', 'b', 'c', 'a']
          ['d', 'a']
     ['b', 'd', 'a']
['c', 'b', 'd', 'a']
     ['c', 'd', 'a']
['b', 'c', 'd', 'a']

You could do the same thing with a permutation generator which produced permutations in prefix order, such as the lexicographically ordered generator implemented in itertools.