Algorithm to create permutations, including omissions-CodePudding

I am trying to find an algorithm that allows me to create all permutations/combinations of list elements, including the ones that occur when each of them are omitted.

For example, a list that contains

[a, b, c]

should produce the standard permutations

[a, b, c], [a, c, b], [b, a, c], [b, c, a], [c, b, a], [c, a, b]

but also these ones that result when one of the list entries is omitted

[a, b], [a, c], [b, a], [b, c], [c, a], [c, b]

and

[a], [b], [c]

Anyone have an idea for the best approach here? Unfortunately, Heap's algorithm only generates the standard permutations and I have not found any other algorithm that would give me the entire spectrum of permutations I need.

CodePudding user response：

I solved it by recursively calling Heap's algorithm, with each recursion containing a loop that removes one element, respectively, per iteration. This shrinks the list and iteratively removes each entry once per recursion, then permuting the leftovers.

CodePudding user response：

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.