Partial Permutations

28 Nov 2020 - Hadron DaVinci

A partial permutation is known as a P(n,k) problem which means we must select permutations
of size k out of n objects. There are numerous algorithms for calculating partial permutations
but I wanted one that seemed more intuitive.

I’ll discuss a custom partial permutation approach created by modifying a full permutation algorithm.

Problem

Given array A, calculate the partial permutations when selecting 2 items.
A = [3, 6, 9], k = 2

Epiphanies

Using results obtained from doing full permutations, we can extract some epiphanies.
Here is the full permutation of [3, 6, 9]:

    (3, 6, 9)
    (3, 9, 6)
    (6, 3, 9)
    (6, 9, 3)
    (9, 6, 3)
    (9, 3, 6)

(1) The full permutation contains information for all its partial permutations.
Specifically, for each partial permutation, we can use the result of the full permutation
and take the first kth elements to obtain non-unique results for P(n, k).
I will replace omitted elements with the * character.

Permutation([3, 6, 9], k=2) gives us:

    (3, 6, *)
    (3, 9, *)
    (6, 3, *)
    (6, 9, *)
    (9, 6, *)
    (9, 3, *)

Permutation([3, 6, 9], k=1) gives us:

    (3, *, *)
    (3, *, *)
    (6, *, *)
    (6, *, *)
    (9, *, *)
    (9, *, *)

Permutation([3, 6, 9], k=0) gives us:

    (*, *, *)
    (*, *, *)
    (*, *, *)
    (*, *, *)
    (*, *, *)
    (*, *, *)   

Method

Time Complexity: Factorial
Spatial Complexity: n

Method Summary
Use epiphany from above and modify a full-permutation algorithm so it takes the first kth elements
and skips non-unique permutations.

The steps are exactly the same as described here except the following has changed:

The generator is within a wrapper function called partial_permute.
this allows us to modify the input information once such as:

determining length of A

setting k as the length of A if k is None

defining generator so the default ci is 0

The generator only yields when ci == k

behavior is controlled by a proxy with variable called should_yield

When the generator yields, it only yields the first kth elements in A

Solution

from typing import Callable


def partial_permute(a, k=None) -> Callable[[int], tuple]:
    """
    Returns generator that does partial permutations.
    When doing P(a, k), this code still does the work of P(a)
    but skips yielding the non unique tuples.

    :param a: an iterable
    :param k: size of selection
    :return: a partial permutation generator
    """
    full_length = len(a)
    should_yield = False

    if k is None:
        k = full_length

    def generate(ci: int = 0) -> tuple:
        """
        Generates tuples of size k
        :param ci: the current index
        :yields: a tuple of selection size k
        """
        nonlocal should_yield
        if ci == k:
            should_yield = True

        if should_yield and ci == full_length:
            should_yield = False
            yield tuple(a[0: k])
        else:
            for i in range(ci, full_length):
                a[ci], a[i] = a[i], a[ci]
                yield from generate(ci + 1)
                a[ci], a[i] = a[i], a[ci]

    return generate()



# Try Code
A = [3, 6, 9]
for p in partial_permute(A, 2):
    print(p)

Result

(3, 6)
(3, 9)
(6, 3)
(6, 9)
(9, 6)
(9, 3)

Files

method1.py