Combinatorics - CS1302

from __init__ import install_dependencies

await install_dependencies()

%reload_ext divewidgets

Permutation using recursion¶

For examples:

The list of (3-)permutations of 1,2,3 is:

[(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)]

The list of 2-permutations of 1,2,3 is:

[(1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2)]

The list of 4-permutation of 1,2,3 is:

[]

In the above, we used

a tuple delimited by () such as (1,2,3) to store items of a permutation, and
a list delimited by [] such as [(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)] to store all the permutations.

Generating permutations is a fundamental problem in computing and combinatorics. A simple way to generate permutations is by the following recurrence relation. (There are also other algorithms.)

Proposition 1

A $k$ -permutation of $n$ satisfies the recurrence relation for $0\leq k \leq n$ :

Removing the first element of a $k$ -permutation of $n$ objects gives a different $(k-1)$ -permutation of the remaining $n-1$ objects.

(a_{i_0}, \underbrace{a_{i_1},\dots,a_{i_{k-1}}}_{\text{($k-1$)-permutation of $a_{i_1},\dots,a_{i_{k-1}}$.}\kern-5em} )

(2)

Reversing the above removal process gives a way of constructing a $k$ -permutation from a $(k-1)$ -permutation.
E.g., the permutations of $1,2,3$ can be constructed as follows:

[\overbrace{({\color{red} 1}, {\color{blue}{2, 3}}), ({\color{red} 1}, {\color{blue}{3, 2}})}^{\text{prepend 1 to permutations of $2,3$.} }, \overbrace{({\color{red} 2}, {\color{blue}{1, 3}}), ({\color{red} 2}, {\color{blue}{3, 1}})}^{\text{prepend 2 to permutations of $1,3$.} }, \overbrace{({\color{red} 3}, {\color{blue}{1, 2}}), ({\color{red} 3}, {\color{blue}{2, 1}})}^{\text{prepend 3 to permutations of $1,2$.} }]

(3)

The following implements the recurrence equation as a recursion:

def permutation(*a, k=None):
    """Construct all (k-)permutations of the position arguments.

    Parameters
    ----------
    *a: object, object, ...
        n items specified as positional arguments
    k: int
        Optional argument indicating the size of each permutation. 
        Default: number n of items specified in *a.

    Returns
    -------
    list:
        List of all k-permutations represented as ordered tuples of the n objects.
    """
    n = len(a)
    output = []
    if k is None:
        k = n
    if 0 < k <= n:
        for i in range(n):
            output.extend(
                [(a[i],) + p for p in permutation(*a[:i], *a[i + 1 :], k=k - 1)]
            )
    elif k == 0:
        return [()]
    return output


print(permutation(1, 2, 3))
print(permutation(1, 2, 3, k=2))

In particular, the recurrence is implemented by the for loop:

        ...
        for i in range(n):
            output.extend([(a[i], ) + p
                           for p in permutation(*a[:i], *a[i + 1:], k=k - 1)])
        ...

In the above code, (a[i],) + p creates a $k$ -permutation of the items in a by concatenating for each index i

a singleton tuple (a[i],) and
a $(k-1)$ -permutation p of all elements but a[i].

(See the example in the recurrence relation described earlier.)

YOUR ANSWER HERE

Number of permutations¶

Computing permutations using recursion is slow. Why?

There are too many permutations, even for a reasonably small $n$ . Try running the following code in a new console:

n = 10
output = permutation(*range(1, n + 1))
print(f"# {n}-permutations:", len(output))

Quite surprisingly, the number of permutations can be calculated significantly faster without enumerating all the permutations.

The quantity is fundamental in the field of combinatorics with enormous applications.

def num_permutation(n):
    """Compute the number of permutations.

    Parameters
    ----------
    n: int
        Number of items.

    Return
    ------
    int:
        Number of permutations of n items.
    """
    # YOUR CODE HERE
    raise NotImplementedError

Source

# tests
assert num_permutation(10) == 3628800
assert num_permutation(0) == 1
assert num_permutation(-1) == 0

def num_permutation(n, k=None):
    """Compute the number of k-permutations of n items.

    Parameters
    ----------
    n: int
        Number of items to permute.
    k: int
        Optional argument indicating the size of each permutation.
        Default: n

    Returns
    -------
    int:
        Number of k-permutations of n items.
    """
    # YOUR CODE HERE
    raise NotImplementedError

Source

# tests
assert isinstance(num_permutation(0), int)
assert num_permutation(3) == 6
assert num_permutation(3, 0) == 1
assert num_permutation(3, 2) == 6
assert num_permutation(10, 5) == 30240

Permutation using iteration¶

The following function permutation_sequence(*a) returns a generator that generates the list of $k$ -permutations one-by-one for $k$ from 0 to len(a).

def permutation_sequence(*a):
    """Returns a generator for the k-permutations of the positional arguments
    for k from 0 to len(a)."""
    n = len(a)
    output, idx_left = [()], [tuple(range(n))]
    for k in range(n + 1):
        yield output
        next_output, next_idx_left = [], []
        for m in range(len(idx_left)):
            for j in range(len(idx_left[m])):
                i = idx_left[m][j]
                next_output.append(output[m] + (a[i],))
                next_idx_left.append(idx_left[m][:j] + idx_left[m][j + 1 :])
        output, idx_left = next_output, next_idx_left


for permutation_list in permutation_sequence(1, 2, 3):
    print(permutation_list)

Unlike the recursive function permutation, the above generates a $k$ -permutation $(a_{i_0},\dots,a_{i_{k-1}})$ of $n$ items iteratively by

choosing $i_j$ for $j$ from 0 to $k-1$ such that
$i_j$ is not already chosen, i.e., $i_j\not\in \{i_0,\dots,i_{j-1}\}$ .

E.g., the permutations of $1,2,3$ is generated iteratively as follows:

1
1,2
- (1,2,3)
1,3
- (1,3,2)
2
2,1
- (2,1,3)
2,3
- (2,3,1)
3
3,1
- (3,1,2)
3,2
- (3,2,1)

Is iteration significantly faster?

Try running the following code in a new console:

n = 10
for k, permutation_list in enumerate(permutation_sequence(*range(1, n + 1))):
    print("# {}-permutations of {} items: {}".format(k, n, len(permutation_list)))

Unfortunately, there is not much improvement. Nevertheless, we can efficiently compute the number of $k$ -permutations based on the previously computed number of $k-1$ -permutations:

For $k$ from 0 to $n$ ,

P_{n,k} = \underbrace{\overbrace{n\times (n-1)\times \cdots }^{P_{n,k-1}\text{ if }k>0}\times(n-k+1)}_{\text{$k$ terms in the product.}}.

(6)

def num_permutation_sequence(n):
    output = 1
    for k in range(0, n + 1):
        # YOUR CODE HERE
        raise NotImplementedError

Source

# tests
assert [m for m in num_permutation_sequence(3)] == [1, 3, 6, 6]
assert [m for m in num_permutation_sequence(10)] == [
    1,
    10,
    90,
    720,
    5040,
    30240,
    151200,
    604800,
    1814400,
    3628800,
    3628800]

def num_permutation_sequence(n):
    # YOUR CODE HERE
    raise NotImplementedError

Source

# tests
g = num_permutation_sequence(3)
assert (next(g), next(g), g.send(0), next(g), next(g), next(g), g.send(0)) == (
    1,
    3,
    4,
    12,
    24,
    24,
    120)

Deduplication using Decorator¶

An issue with the function permutation is that it regards arguments at different positions as distinct, even if they may have the same value. E.g.,
permutation(1,1,2) returns [(1, 1, 2), (1, 2, 1), (1, 1, 2), (1, 2, 1), (2, 1, 1), (2, 1, 1)]
where each distinct permutation appears twice.

To remove duplicates from a list, we can

convert the list to a set (which automatically removes duplicates),
and then convert the set back to a list.

print("Deduplicated:", list(set(permutation(1, 1, 2))))

Using a decorator, we can fix permutation without rewriting the function.

import functools


def deduplicate_output(f):
    """Takes in a function f that returns a list possibly with duplicates,
    returns a decorator that removes duplicates from the output list."""

    @functools.wraps(f)
    def wrapper(*args, **kwargs):
        return list(set(f(*args, **kwargs)))

    return wrapper


permutation = deduplicate_output(permutation)
print("Deduplicated: ", permutation(1, 1, 2))
permutation = permutation.__wrapped__
print("Original: ", permutation(1, 1, 2))

def deduplicate_input(f):
    """Takes in a function f that takes a variable number of arguments
    possibly with duplicates, returns a decorator that removes duplicates
    in the positional argument."""

    @functools.wraps(f)
    def wrapper(*args, **kwargs):
        # YOUR CODE HERE
        raise NotImplementedError

    return wrapper

Source

# tests
permutation = deduplicate_input(permutation)
try:
    assert set(permutation(1, 1, 2)) == set([(1, 2), (2, 1)])
finally:
    permutation = permutation.__wrapped__