Combinatorics¶

Permutation using Recursion¶

Definition 4

A $k$-permutation of $n$ items $a_0,\dots,a_{n-1}$ is an ordered tuple

\[ (a_{i_0},\dots,a_{i_{k-1}}) \]

of $k$ out of the $n$ objects, where $0\leq i_0,\dots,i_{k-1}<n$ are distinct indices. An $n$-permutation of $n$ objects is simply called a permutation of $n$ objects.

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

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

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

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 recursion. (There are also other algorithms.)

Proposition 4

A $k$-permutation of $n$ satisfies the recurrence relation:

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} ) \]

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$.} }]\]

The following implements the 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))

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

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

Note

The comma in (a[i],) is not a typo. Without commas, (...) does not create a tuple.
a[:i] returns a tuple of a[0] up to and excluding a[i]. *a[:i] unpacks the tuple such that its items are separate arguments to permutation.
Similarly, *a[i + 1:] provides items as separate arguments starting from a[i + 1] until the last item in a.
[... for ...] generates a list of $k$-permutations, and output.extend([...]) added the list to the end of the output list.

Exercise One of the base cases of the recusion happens when $k=0$, in which case there is only one $k$-permutation, namely the empty tuple $()$, and so the function returns [()]. There is another base case of the recursion. Explain the condition of that base case and its return value.

YOUR ANSWER HERE

Number of permutations¶

Computing permutations using recursion is slow. Why?
There are simply too many permutations even for a reasonably small $n$.

if input("Run? [Y/n]").lower() != "n":
    n = 10
    output = permutation(*range(1, n + 1))
    print("# permutations:", len(output))

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

Proposition 5

The number $P_n$ of ($n-$)permutations of $n$ items satisfies the following recurrence:

(9)¶\[\begin{split} P_n = \begin{cases} n P_{n-1} & n>0\\ 1 & n=0\\ 0 & \text{otherwise.} \end{cases} \end{split}\]

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

Exercise Implement the above recurrence equation.

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

Hint

Ensure all base cases are covered, and can run efficiently for large $n$.

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

Proposition 6

The number $P_{n,k}$ of $k$-permutations of $n$ items is given by the formula

(10)¶\[\begin{split} P_{n,k} = \begin{cases} \frac{P_n}{P_{n-k}} & 0\leq k \leq n\\ 0 & \text{otherwise.} \end{cases} \end{split}\]

Exercise Extend the function num_permutation to allow for a optional argument k.

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

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

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

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)

Proposition 7

permutation_sequence maintains the following invariance at the beginning of each iteration:

output is the list of $k$-permutations, and
idx_left[m] is the list of indices of arguments not yet in output[m].

A $(k+1)$-permutation (in next_output) can then be generated by appending an argument (with an index from idx_left) to a $k$-permutation (in output).

Is iteration significantly faster?

if input("Run? [Y/n]").lower() != "n":
    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$,

(11)¶\[ 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.}}.\]

Exercise Use the yield statement to write the function num_permutation_sequence(n) that returns a generator of $P_{n,k}$ with k from 0 to n.

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

Exercise Extend the function num_permutation_sequence(n) so that calling send(0) method causes the generator to increment $n$ instead of $k$ for the next number to generate. i.e., for $0\leq k \leq n$,

\[\dots P_{n,k-1}\to P_{n,k} \xrightarrow{\text{send(0)}} P_{n+1,k} \to P_{n+1,k+1}\dots\]

where $\to$ without labels is the normal transition without calling the send method.

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

Hint

By (11),

\[P_{n+1,k}=P_{n,k} \times \frac{n+1}{n-k+1}.\]

# 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 remove duplicates),
and then convert the set back to a list.

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

Deduplicated: [(1, 2, 1), (2, 1, 1), (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 remove 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))

Deduplicated:  [(1, 2, 1), (2, 1, 1), (1, 1, 2)]
Original:  [(1, 1, 2), (1, 2, 1), (1, 1, 2), (1, 2, 1), (2, 1, 1), (2, 1, 1)]

Exercise: Create a decorator to eliminate duplicate input positional arguments instead of the ouput, i.e.,
permutation(1,1,2) will return the same result as permutation(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 remove 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__

CS1302

Combinatorics¶

Permutation using Recursion¶

Number of permutations¶

Permutation using Iteration¶

Deduplication using Decorator¶