Combinatorics - CS1302

%reload_ext divewidgets

if not input('Load JupyterAI? [Y/n]').lower()=='n':
    %reload_ext jupyter_ai

Load JupyterAI? [Y/n]

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.

Proposition 1

A $k$ -permutation of $n$ satisfies the recurrence relation for $1\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{\scriptsize $(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{\scriptsize prepend 1 to permutations of $2,3$.} }, \overbrace{({\color{red} 2}, {\color{blue}{1, 3}}), ({\color{red} 2}, {\color{blue}{3, 1}})}^{\text{\scriptsize prepend 2 to permutations of $1,3$.} }, \overbrace{({\color{red} 3}, {\color{blue}{1, 2}}), ({\color{red} 3}, {\color{blue}{2, 1}})}^{\text{\scriptsize 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
permutation_v1 = '\n'.join(In[-1].split('\n')[:-1]) # to query AI later

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

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?

Let us first improve the recursion using a helper function as follows:

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.
    """
    def permutation_helper(a, k, output, current=[]):
        if k==0:
            output.append(tuple(current))
        else:
            for i in range(len(a)):
                current.append(a[i])
                permutation_helper([*a[:i], *a[i + 1 :]], k-1, output, current)
                current.pop()

    n = len(a)
    if k is None:
        k = n
    if 0 <= k <= n:
        permutation_helper(a, k, output:=[])
    return output
permutation_v2 = '\n'.join(In[-1].split('\n')[:-1]) # to query AI later

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

%%ai
Explain briefly why the second implementation is better than the first?
--
{permutation_v1}
--
{permutation_v2}

Loading...

if input("Execute? [Y/n]").lower!='n': # don't remove this check/fence, or auto-grading will fail
    n = 10
    output = permutation(*range(1, n + 1))
    print(f"# {n}-permutations:", len(output))

Execute? [Y/n]

# 10-permutations: 3628800

😈: Do you want to see a crash?

Re-run the above cell with n = 11 instead to use up your memory.

There are too many permutations, even for a reasonably small $n$ .

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

# hidden tests

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

# hidden tests

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 tests

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

# hidden tests

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

# hidden tests