Combinatorics - CS1302

CS1302 Introduction to Computer Programming

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

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

# HIDDEN

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

# 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

# HIDDEN

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

# 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]

# HIDDEN

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

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

# HIDDEN

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

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

# HIDDEN