4
$\begingroup$

I need to generate all unique tuples of length k chosen from a series of unique, positive integers. In my case n choose k will have n=10, 1 <= k <= 10; and the series I am choosing from is { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 } .

For each chosen tuple, all of its permutations need to be present in the output. For example, for k = 2, the chosen tuple (0, 1) needs to have both (0, 1) and (1, 0) in the output. The output overall needs to be in lexicographic order, which in turn implies that lexicographic ordering of permutations within a given chosen combination is not enough.

I'm following along with

https://www.cs.utexas.edu/users/djimenez/utsa/cs3343/lecture25.html

which offers a simple recursive algorithm to generate combinations. Their recommendation to do this:

Note that you can get all permutations of n things taken k at a time by simply calling perm (v, maxk, 0); at the base case of combinations. This generates all k! permutations of each of the n C k combinations, taking O(k! n (n C k)) = O((n+1)!/(n-k)!) time.

gets me 90% of the way there, but yields result tuples in an order that is not useful to me. For k=2 it yields

[0, 1]
[1, 0]
[0, 2]
[2, 0]
...

where I would want it to yield

[0, 1]
[0, 2]
[0, 3]
[0, 4]
[0, 5]
[0, 6]
[0, 7]
[0, 8]
[0, 9]
[1, 0]
[1, 2]
...

Is there a modification to this algorithm - or a different one - that will do this? I hope it doesn't require putting everything in memory and then applying an in-place sort.

Improve this question
$\endgroup$
6
  • 3
    $\begingroup$ Go over all possible choices of the first number. Within each one, go over all remaining choices of the second number. And so on. $\endgroup$
    – Yuval Filmus
    Dec 26, 2020 at 15:07
  • $\begingroup$ @YuvalFilmus I guess that requires hanging onto a set of "remaining choices". The recursive solution would require one such set at each depth. Is there a way to do this non-recursively? $\endgroup$
    – Reinderien
    Dec 26, 2020 at 15:11
  • $\begingroup$ To solve this iteratively, find a way to compute the next combination given the current one. Be resourceful. It might help to keep track with elements are already taken. $\endgroup$
    – Yuval Filmus
    Dec 26, 2020 at 15:12
  • 1
    $\begingroup$ You could read how Python does this in the itertools module. There is a Python reference and C implementation. The Python version is written in quite idiomatic Python. $\endgroup$
    – Peilonrayz
    Dec 26, 2020 at 16:48
  • 1
    $\begingroup$ @Peilonrayz That's very promising. I've taken the liberty of copying and simplifying that source and it works quite well. $\endgroup$
    – Reinderien
    Dec 26, 2020 at 19:36

4 Answers 4

Reset to default
4
$\begingroup$

Here is a simple iterative solution. We maintain two arrays, an output array $L$, and a Boolean array $A$, which keeps track of the elements currently in $L$. We update $A$ as we add and remove elements from $L$.

We initialize $L$ with $0,\ldots,k-1$, which is also our first output. Now we repeatedly try to "increment" $L$. If successful, we output the incremented $L$, and try to increment $L$ again. If unsuccessful, we have gone through all combinations, and can terminate.

In order to increment $L$, we start by trying to increment position $k-1$ (this is the rightmost position). We do so by scanning the array $A$ starting at $L[k-1] + 1$, until we find an element $x$ which is not in $L$. If this search is successful, we replace $L[k-1]$ with $x$. Otherwise, we try to do the same for $L[k-2],\ldots,L[0]$, until successful; if all of these fail, we declare failure (and terminate).

Suppose that we have successfully replaced $L[j]$. If $j = k-1$, we're done. Otherwise, we have to update $L[j+1],\ldots,L[k-1]$, which we do by scanning $A$ starting at $0$, inserting the first $k-j-1$ elements not already in $L$.

Here is a Python implementation:

def gen(n, k): 
    A = [True] * k + [False] * (n-k) 
    L = list(range(k)) 
    yield tuple(L) 
    while True: 
        j = k - 1 
        while j >= 0: 
            A[L[j]] = False 
            t = L[j] + 1 
            while t < n and A[t]: 
                t += 1 
            if t < n: 
                A[t] = True 
                L[j] = t 
                r = 0 
                j += 1 
                while j < k: 
                    while A[r]: 
                        r += 1 
                    A[r] = True 
                    L[j] = r 
                    j += 1 
                yield tuple(L)
                break 
            else: 
                j -= 1 
        if j == -1: 
            break

An even simpler recursive solution simply iterates over all possible choices of the first element; within these, iterates over all possible choices of the second element; and so on.

Here is a Python implementation:

def gen_rec(n, k, L=[]): 
    if len(L) == k: 
        yield tuple(L) 
    for i in range(n): 
        if i not in L: 
            yield from gen_rec(n, k, L + [i])
Improve this answer
$\endgroup$
4
$\begingroup$

The most appealing solution so far seems to be a spin on Python's own permutations function (source) that can be slightly simplified for this use case; thanks @Peilonrayz:

def combinations(r: int, n: int=10) -> Iterable[Sequence[int]]:
    pool = range(n)
    indices = list(pool)
    cycles = list(range(n, n-r, -1))
    r_range = range(r-1, -1, -1)

    yield pool[:r]

    while True:
        for i in r_range:
            cycles[i] -= 1

            if cycles[i] > 0:
                j = cycles[i]
                indices[i], indices[-j] = indices[-j], indices[i]
                yield indices[:r]
                break

            indices[i:] = indices[i+1:] + indices[i:i+1]
            cycles[i] = n - i
        else:
            return

As best as I can tell, the way this works:

  • This is an iterative algorithm that swaps elements in a mutable list indices of length n from which r elements will be chosen; these elements will always be chosen from the beginning of the list
  • indices starts with a list of elements to be chosen in their original order
  • A secondary mutable list cycles of length r controls which elements are swapped
  • On an inner condition based on cycles, only two elements are exchanged with each other and one output tuple is produced. If that condition is false, an output tuple is not produced, and instead indices sees a portion of its elements shifted left by one position, with the middle element being bumped to the end.

I don't think transcribing the code above into pseudocode has much value, so instead I'll output a dump that illustrates the value of these control variables over a few iterations where n=10, r=3:

indices=[0, 1, 3, 2, 4, 5, 6, 7, 8, 9] cycles=[10, 9, 7] i=2, indices 2 and 3 were exchanged, output [0, 1, 3]
indices=[0, 1, 4, 2, 3, 5, 6, 7, 8, 9] cycles=[10, 9, 6] i=2, indices 2 and 4 were exchanged, output [0, 1, 4]
indices=[0, 1, 5, 2, 3, 4, 6, 7, 8, 9] cycles=[10, 9, 5] i=2, indices 2 and 5 were exchanged, output [0, 1, 5]
indices=[0, 1, 6, 2, 3, 4, 5, 7, 8, 9] cycles=[10, 9, 4] i=2, indices 2 and 6 were exchanged, output [0, 1, 6]
indices=[0, 1, 7, 2, 3, 4, 5, 6, 8, 9] cycles=[10, 9, 3] i=2, indices 2 and 7 were exchanged, output [0, 1, 7]
indices=[0, 1, 8, 2, 3, 4, 5, 6, 7, 9] cycles=[10, 9, 2] i=2, indices 2 and 8 were exchanged, output [0, 1, 8]
indices=[0, 1, 9, 2, 3, 4, 5, 6, 7, 8] cycles=[10, 9, 1] i=2, indices 2 and 9 were exchanged, output [0, 1, 9]
indices=[0, 1, 9, 2, 3, 4, 5, 6, 7, 8], shifting at 2:
        [      \2, 3, 4, 5, 6, 7, 8,/9]

indices=[0, 2, 1, 3, 4, 5, 6, 7, 8, 9] cycles=[10, 8, 8] i=1, indices 1 and 2 were exchanged, output [0, 2, 1]
indices=[0, 2, 3, 1, 4, 5, 6, 7, 8, 9] cycles=[10, 8, 7] i=2, indices 2 and 3 were exchanged, output [0, 2, 3]
indices=[0, 2, 4, 1, 3, 5, 6, 7, 8, 9] cycles=[10, 8, 6] i=2, indices 2 and 4 were exchanged, output [0, 2, 4]
indices=[0, 2, 5, 1, 3, 4, 6, 7, 8, 9] cycles=[10, 8, 5] i=2, indices 2 and 5 were exchanged, output [0, 2, 5]
indices=[0, 2, 6, 1, 3, 4, 5, 7, 8, 9] cycles=[10, 8, 4] i=2, indices 2 and 6 were exchanged, output [0, 2, 6]
indices=[0, 2, 7, 1, 3, 4, 5, 6, 8, 9] cycles=[10, 8, 3] i=2, indices 2 and 7 were exchanged, output [0, 2, 7]
indices=[0, 2, 8, 1, 3, 4, 5, 6, 7, 9] cycles=[10, 8, 2] i=2, indices 2 and 8 were exchanged, output [0, 2, 8]
indices=[0, 2, 9, 1, 3, 4, 5, 6, 7, 8] cycles=[10, 8, 1] i=2, indices 2 and 9 were exchanged, output [0, 2, 9]
indices=[0, 2, 9, 1, 3, 4, 5, 6, 7, 8], shifting at 2:
        [      \1, 3, 4, 5, 6, 7, 8,/9]

indices=[0, 3, 1, 2, 4, 5, 6, 7, 8, 9] cycles=[10, 7, 8] i=1, indices 1 and 3 were exchanged, output [0, 3, 1]
indices=[0, 3, 2, 1, 4, 5, 6, 7, 8, 9] cycles=[10, 7, 7] i=2, indices 2 and 3 were exchanged, output [0, 3, 2]
indices=[0, 3, 4, 1, 2, 5, 6, 7, 8, 9] cycles=[10, 7, 6] i=2, indices 2 and 4 were exchanged, output [0, 3, 4]
indices=[0, 3, 5, 1, 2, 4, 6, 7, 8, 9] cycles=[10, 7, 5] i=2, indices 2 and 5 were exchanged, output [0, 3, 5]
indices=[0, 3, 6, 1, 2, 4, 5, 7, 8, 9] cycles=[10, 7, 4] i=2, indices 2 and 6 were exchanged, output [0, 3, 6]
indices=[0, 3, 7, 1, 2, 4, 5, 6, 8, 9] cycles=[10, 7, 3] i=2, indices 2 and 7 were exchanged, output [0, 3, 7]
indices=[0, 3, 8, 1, 2, 4, 5, 6, 7, 9] cycles=[10, 7, 2] i=2, indices 2 and 8 were exchanged, output [0, 3, 8]
indices=[0, 3, 9, 1, 2, 4, 5, 6, 7, 8] cycles=[10, 7, 1] i=2, indices 2 and 9 were exchanged, output [0, 3, 9]
indices=[0, 3, 9, 1, 2, 4, 5, 6, 7, 8], shifting at 2:
        [      \1, 2, 4, 5, 6, 7, 8,/9]

indices=[0, 4, 1, 2, 3, 5, 6, 7, 8, 9] cycles=[10, 6, 8] i=1, indices 1 and 4 were exchanged, output [0, 4, 1]
indices=[0, 4, 2, 1, 3, 5, 6, 7, 8, 9] cycles=[10, 6, 7] i=2, indices 2 and 3 were exchanged, output [0, 4, 2]
indices=[0, 4, 3, 1, 2, 5, 6, 7, 8, 9] cycles=[10, 6, 6] i=2, indices 2 and 4 were exchanged, output [0, 4, 3]
indices=[0, 4, 5, 1, 2, 3, 6, 7, 8, 9] cycles=[10, 6, 5] i=2, indices 2 and 5 were exchanged, output [0, 4, 5]
indices=[0, 4, 6, 1, 2, 3, 5, 7, 8, 9] cycles=[10, 6, 4] i=2, indices 2 and 6 were exchanged, output [0, 4, 6]
indices=[0, 4, 7, 1, 2, 3, 5, 6, 8, 9] cycles=[10, 6, 3] i=2, indices 2 and 7 were exchanged, output [0, 4, 7]
indices=[0, 4, 8, 1, 2, 3, 5, 6, 7, 9] cycles=[10, 6, 2] i=2, indices 2 and 8 were exchanged, output [0, 4, 8]
indices=[0, 4, 9, 1, 2, 3, 5, 6, 7, 8] cycles=[10, 6, 1] i=2, indices 2 and 9 were exchanged, output [0, 4, 9]
indices=[0, 4, 9, 1, 2, 3, 5, 6, 7, 8], shifting at 2:
        [      \1, 2, 3, 5, 6, 7, 8,/9]

indices=[0, 5, 1, 2, 3, 4, 6, 7, 8, 9] cycles=[10, 5, 8] i=1, indices 1 and 5 were exchanged, output [0, 5, 1]
indices=[0, 5, 2, 1, 3, 4, 6, 7, 8, 9] cycles=[10, 5, 7] i=2, indices 2 and 3 were exchanged, output [0, 5, 2]
indices=[0, 5, 3, 1, 2, 4, 6, 7, 8, 9] cycles=[10, 5, 6] i=2, indices 2 and 4 were exchanged, output [0, 5, 3]
indices=[0, 5, 4, 1, 2, 3, 6, 7, 8, 9] cycles=[10, 5, 5] i=2, indices 2 and 5 were exchanged, output [0, 5, 4]
indices=[0, 5, 6, 1, 2, 3, 4, 7, 8, 9] cycles=[10, 5, 4] i=2, indices 2 and 6 were exchanged, output [0, 5, 6]
indices=[0, 5, 7, 1, 2, 3, 4, 6, 8, 9] cycles=[10, 5, 3] i=2, indices 2 and 7 were exchanged, output [0, 5, 7]
indices=[0, 5, 8, 1, 2, 3, 4, 6, 7, 9] cycles=[10, 5, 2] i=2, indices 2 and 8 were exchanged, output [0, 5, 8]
indices=[0, 5, 9, 1, 2, 3, 4, 6, 7, 8] cycles=[10, 5, 1] i=2, indices 2 and 9 were exchanged, output [0, 5, 9]
indices=[0, 5, 9, 1, 2, 3, 4, 6, 7, 8], shifting at 2:
        [      \1, 2, 3, 4, 6, 7, 8,/9]

indices=[0, 6, 1, 2, 3, 4, 5, 7, 8, 9] cycles=[10, 4, 8] i=1, indices 1 and 6 were exchanged, output [0, 6, 1]
indices=[0, 6, 2, 1, 3, 4, 5, 7, 8, 9] cycles=[10, 4, 7] i=2, indices 2 and 3 were exchanged, output [0, 6, 2]
indices=[0, 6, 3, 1, 2, 4, 5, 7, 8, 9] cycles=[10, 4, 6] i=2, indices 2 and 4 were exchanged, output [0, 6, 3]
indices=[0, 6, 4, 1, 2, 3, 5, 7, 8, 9] cycles=[10, 4, 5] i=2, indices 2 and 5 were exchanged, output [0, 6, 4]
indices=[0, 6, 5, 1, 2, 3, 4, 7, 8, 9] cycles=[10, 4, 4] i=2, indices 2 and 6 were exchanged, output [0, 6, 5]
indices=[0, 6, 7, 1, 2, 3, 4, 5, 8, 9] cycles=[10, 4, 3] i=2, indices 2 and 7 were exchanged, output [0, 6, 7]
indices=[0, 6, 8, 1, 2, 3, 4, 5, 7, 9] cycles=[10, 4, 2] i=2, indices 2 and 8 were exchanged, output [0, 6, 8]
indices=[0, 6, 9, 1, 2, 3, 4, 5, 7, 8] cycles=[10, 4, 1] i=2, indices 2 and 9 were exchanged, output [0, 6, 9]
indices=[0, 6, 9, 1, 2, 3, 4, 5, 7, 8], shifting at 2:
        [      \1, 2, 3, 4, 5, 7, 8,/9]

indices=[0, 7, 1, 2, 3, 4, 5, 6, 8, 9] cycles=[10, 3, 8] i=1, indices 1 and 7 were exchanged, output [0, 7, 1]
indices=[0, 7, 2, 1, 3, 4, 5, 6, 8, 9] cycles=[10, 3, 7] i=2, indices 2 and 3 were exchanged, output [0, 7, 2]
indices=[0, 7, 3, 1, 2, 4, 5, 6, 8, 9] cycles=[10, 3, 6] i=2, indices 2 and 4 were exchanged, output [0, 7, 3]
indices=[0, 7, 4, 1, 2, 3, 5, 6, 8, 9] cycles=[10, 3, 5] i=2, indices 2 and 5 were exchanged, output [0, 7, 4]
indices=[0, 7, 5, 1, 2, 3, 4, 6, 8, 9] cycles=[10, 3, 4] i=2, indices 2 and 6 were exchanged, output [0, 7, 5]
indices=[0, 7, 6, 1, 2, 3, 4, 5, 8, 9] cycles=[10, 3, 3] i=2, indices 2 and 7 were exchanged, output [0, 7, 6]
indices=[0, 7, 8, 1, 2, 3, 4, 5, 6, 9] cycles=[10, 3, 2] i=2, indices 2 and 8 were exchanged, output [0, 7, 8]
indices=[0, 7, 9, 1, 2, 3, 4, 5, 6, 8] cycles=[10, 3, 1] i=2, indices 2 and 9 were exchanged, output [0, 7, 9]
indices=[0, 7, 9, 1, 2, 3, 4, 5, 6, 8], shifting at 2:
        [      \1, 2, 3, 4, 5, 6, 8,/9]

indices=[0, 8, 1, 2, 3, 4, 5, 6, 7, 9] cycles=[10, 2, 8] i=1, indices 1 and 8 were exchanged, output [0, 8, 1]
indices=[0, 8, 2, 1, 3, 4, 5, 6, 7, 9] cycles=[10, 2, 7] i=2, indices 2 and 3 were exchanged, output [0, 8, 2]
indices=[0, 8, 3, 1, 2, 4, 5, 6, 7, 9] cycles=[10, 2, 6] i=2, indices 2 and 4 were exchanged, output [0, 8, 3]
indices=[0, 8, 4, 1, 2, 3, 5, 6, 7, 9] cycles=[10, 2, 5] i=2, indices 2 and 5 were exchanged, output [0, 8, 4]
indices=[0, 8, 5, 1, 2, 3, 4, 6, 7, 9] cycles=[10, 2, 4] i=2, indices 2 and 6 were exchanged, output [0, 8, 5]
indices=[0, 8, 6, 1, 2, 3, 4, 5, 7, 9] cycles=[10, 2, 3] i=2, indices 2 and 7 were exchanged, output [0, 8, 6]
indices=[0, 8, 7, 1, 2, 3, 4, 5, 6, 9] cycles=[10, 2, 2] i=2, indices 2 and 8 were exchanged, output [0, 8, 7]
indices=[0, 8, 9, 1, 2, 3, 4, 5, 6, 7] cycles=[10, 2, 1] i=2, indices 2 and 9 were exchanged, output [0, 8, 9]
indices=[0, 8, 9, 1, 2, 3, 4, 5, 6, 7], shifting at 2:
        [      \1, 2, 3, 4, 5, 6, 7,/9]

indices=[0, 9, 1, 2, 3, 4, 5, 6, 7, 8] cycles=[10, 1, 8] i=1, indices 1 and 9 were exchanged, output [0, 9, 1]
indices=[0, 9, 2, 1, 3, 4, 5, 6, 7, 8] cycles=[10, 1, 7] i=2, indices 2 and 3 were exchanged, output [0, 9, 2]
indices=[0, 9, 3, 1, 2, 4, 5, 6, 7, 8] cycles=[10, 1, 6] i=2, indices 2 and 4 were exchanged, output [0, 9, 3]
indices=[0, 9, 4, 1, 2, 3, 5, 6, 7, 8] cycles=[10, 1, 5] i=2, indices 2 and 5 were exchanged, output [0, 9, 4]
indices=[0, 9, 5, 1, 2, 3, 4, 6, 7, 8] cycles=[10, 1, 4] i=2, indices 2 and 6 were exchanged, output [0, 9, 5]
indices=[0, 9, 6, 1, 2, 3, 4, 5, 7, 8] cycles=[10, 1, 3] i=2, indices 2 and 7 were exchanged, output [0, 9, 6]
indices=[0, 9, 7, 1, 2, 3, 4, 5, 6, 8] cycles=[10, 1, 2] i=2, indices 2 and 8 were exchanged, output [0, 9, 7]
indices=[0, 9, 8, 1, 2, 3, 4, 5, 6, 7] cycles=[10, 1, 1] i=2, indices 2 and 9 were exchanged, output [0, 9, 8]
indices=[0, 9, 8, 1, 2, 3, 4, 5, 6, 7], shifting at 2:
        [      \1, 2, 3, 4, 5, 6, 7,/8]

indices=[0, 9, 1, 2, 3, 4, 5, 6, 7, 8], shifting at 1:
        [    \1, 2, 3, 4, 5, 6, 7, 8,/9]

indices=[1, 0, 2, 3, 4, 5, 6, 7, 8, 9] cycles=[9, 9, 8] i=0, indices 0 and 1 were exchanged, output [1, 0, 2]
indices=[1, 0, 3, 2, 4, 5, 6, 7, 8, 9] cycles=[9, 9, 7] i=2, indices 2 and 3 were exchanged, output [1, 0, 3]
indices=[1, 0, 4, 2, 3, 5, 6, 7, 8, 9] cycles=[9, 9, 6] i=2, indices 2 and 4 were exchanged, output [1, 0, 4]
indices=[1, 0, 5, 2, 3, 4, 6, 7, 8, 9] cycles=[9, 9, 5] i=2, indices 2 and 5 were exchanged, output [1, 0, 5]
indices=[1, 0, 6, 2, 3, 4, 5, 7, 8, 9] cycles=[9, 9, 4] i=2, indices 2 and 6 were exchanged, output [1, 0, 6]
indices=[1, 0, 7, 2, 3, 4, 5, 6, 8, 9] cycles=[9, 9, 3] i=2, indices 2 and 7 were exchanged, output [1, 0, 7]
indices=[1, 0, 8, 2, 3, 4, 5, 6, 7, 9] cycles=[9, 9, 2] i=2, indices 2 and 8 were exchanged, output [1, 0, 8]
indices=[1, 0, 9, 2, 3, 4, 5, 6, 7, 8] cycles=[9, 9, 1] i=2, indices 2 and 9 were exchanged, output [1, 0, 9]
indices=[1, 0, 9, 2, 3, 4, 5, 6, 7, 8], shifting at 2:
        [      \2, 3, 4, 5, 6, 7, 8,/9]

indices=[1, 2, 0, 3, 4, 5, 6, 7, 8, 9] cycles=[9, 8, 8] i=1, indices 1 and 2 were exchanged, output [1, 2, 0]
indices=[1, 2, 3, 0, 4, 5, 6, 7, 8, 9] cycles=[9, 8, 7] i=2, indices 2 and 3 were exchanged, output [1, 2, 3]
indices=[1, 2, 4, 0, 3, 5, 6, 7, 8, 9] cycles=[9, 8, 6] i=2, indices 2 and 4 were exchanged, output [1, 2, 4]
indices=[1, 2, 5, 0, 3, 4, 6, 7, 8, 9] cycles=[9, 8, 5] i=2, indices 2 and 5 were exchanged, output [1, 2, 5]
indices=[1, 2, 6, 0, 3, 4, 5, 7, 8, 9] cycles=[9, 8, 4] i=2, indices 2 and 6 were exchanged, output [1, 2, 6]
indices=[1, 2, 7, 0, 3, 4, 5, 6, 8, 9] cycles=[9, 8, 3] i=2, indices 2 and 7 were exchanged, output [1, 2, 7]
indices=[1, 2, 8, 0, 3, 4, 5, 6, 7, 9] cycles=[9, 8, 2] i=2, indices 2 and 8 were exchanged, output [1, 2, 8]
indices=[1, 2, 9, 0, 3, 4, 5, 6, 7, 8] cycles=[9, 8, 1] i=2, indices 2 and 9 were exchanged, output [1, 2, 9]
indices=[1, 2, 9, 0, 3, 4, 5, 6, 7, 8], shifting at 2:
        [      \0, 3, 4, 5, 6, 7, 8,/9]

indices=[1, 3, 0, 2, 4, 5, 6, 7, 8, 9] cycles=[9, 7, 8] i=1, indices 1 and 3 were exchanged, output [1, 3, 0]
indices=[1, 3, 2, 0, 4, 5, 6, 7, 8, 9] cycles=[9, 7, 7] i=2, indices 2 and 3 were exchanged, output [1, 3, 2]
indices=[1, 3, 4, 0, 2, 5, 6, 7, 8, 9] cycles=[9, 7, 6] i=2, indices 2 and 4 were exchanged, output [1, 3, 4]
indices=[1, 3, 5, 0, 2, 4, 6, 7, 8, 9] cycles=[9, 7, 5] i=2, indices 2 and 5 were exchanged, output [1, 3, 5]
indices=[1, 3, 6, 0, 2, 4, 5, 7, 8, 9] cycles=[9, 7, 4] i=2, indices 2 and 6 were exchanged, output [1, 3, 6]
indices=[1, 3, 7, 0, 2, 4, 5, 6, 8, 9] cycles=[9, 7, 3] i=2, indices 2 and 7 were exchanged, output [1, 3, 7]
indices=[1, 3, 8, 0, 2, 4, 5, 6, 7, 9] cycles=[9, 7, 2] i=2, indices 2 and 8 were exchanged, output [1, 3, 8]
indices=[1, 3, 9, 0, 2, 4, 5, 6, 7, 8] cycles=[9, 7, 1] i=2, indices 2 and 9 were exchanged, output [1, 3, 9]
indices=[1, 3, 9, 0, 2, 4, 5, 6, 7, 8], shifting at 2:
        [      \0, 2, 4, 5, 6, 7, 8,/9]

indices=[1, 4, 0, 2, 3, 5, 6, 7, 8, 9] cycles=[9, 6, 8] i=1, indices 1 and 4 were exchanged, output [1, 4, 0]
indices=[1, 4, 2, 0, 3, 5, 6, 7, 8, 9] cycles=[9, 6, 7] i=2, indices 2 and 3 were exchanged, output [1, 4, 2]
indices=[1, 4, 3, 0, 2, 5, 6, 7, 8, 9] cycles=[9, 6, 6] i=2, indices 2 and 4 were exchanged, output [1, 4, 3]
indices=[1, 4, 5, 0, 2, 3, 6, 7, 8, 9] cycles=[9, 6, 5] i=2, indices 2 and 5 were exchanged, output [1, 4, 5]
indices=[1, 4, 6, 0, 2, 3, 5, 7, 8, 9] cycles=[9, 6, 4] i=2, indices 2 and 6 were exchanged, output [1, 4, 6]
indices=[1, 4, 7, 0, 2, 3, 5, 6, 8, 9] cycles=[9, 6, 3] i=2, indices 2 and 7 were exchanged, output [1, 4, 7]
indices=[1, 4, 8, 0, 2, 3, 5, 6, 7, 9] cycles=[9, 6, 2] i=2, indices 2 and 8 were exchanged, output [1, 4, 8]
indices=[1, 4, 9, 0, 2, 3, 5, 6, 7, 8] cycles=[9, 6, 1] i=2, indices 2 and 9 were exchanged, output [1, 4, 9]
indices=[1, 4, 9, 0, 2, 3, 5, 6, 7, 8], shifting at 2:
        [      \0, 2, 3, 5, 6, 7, 8,/9]

indices=[1, 5, 0, 2, 3, 4, 6, 7, 8, 9] cycles=[9, 5, 8] i=1, indices 1 and 5 were exchanged, output [1, 5, 0]
indices=[1, 5, 2, 0, 3, 4, 6, 7, 8, 9] cycles=[9, 5, 7] i=2, indices 2 and 3 were exchanged, output [1, 5, 2]
indices=[1, 5, 3, 0, 2, 4, 6, 7, 8, 9] cycles=[9, 5, 6] i=2, indices 2 and 4 were exchanged, output [1, 5, 3]
indices=[1, 5, 4, 0, 2, 3, 6, 7, 8, 9] cycles=[9, 5, 5] i=2, indices 2 and 5 were exchanged, output [1, 5, 4]
indices=[1, 5, 6, 0, 2, 3, 4, 7, 8, 9] cycles=[9, 5, 4] i=2, indices 2 and 6 were exchanged, output [1, 5, 6]
indices=[1, 5, 7, 0, 2, 3, 4, 6, 8, 9] cycles=[9, 5, 3] i=2, indices 2 and 7 were exchanged, output [1, 5, 7]
indices=[1, 5, 8, 0, 2, 3, 4, 6, 7, 9] cycles=[9, 5, 2] i=2, indices 2 and 8 were exchanged, output [1, 5, 8]
indices=[1, 5, 9, 0, 2, 3, 4, 6, 7, 8] cycles=[9, 5, 1] i=2, indices 2 and 9 were exchanged, output [1, 5, 9]
indices=[1, 5, 9, 0, 2, 3, 4, 6, 7, 8], shifting at 2:
        [      \0, 2, 3, 4, 6, 7, 8,/9]

indices=[1, 6, 0, 2, 3, 4, 5, 7, 8, 9] cycles=[9, 4, 8] i=1, indices 1 and 6 were exchanged, output [1, 6, 0]
indices=[1, 6, 2, 0, 3, 4, 5, 7, 8, 9] cycles=[9, 4, 7] i=2, indices 2 and 3 were exchanged, output [1, 6, 2]
indices=[1, 6, 3, 0, 2, 4, 5, 7, 8, 9] cycles=[9, 4, 6] i=2, indices 2 and 4 were exchanged, output [1, 6, 3]
indices=[1, 6, 4, 0, 2, 3, 5, 7, 8, 9] cycles=[9, 4, 5] i=2, indices 2 and 5 were exchanged, output [1, 6, 4]
indices=[1, 6, 5, 0, 2, 3, 4, 7, 8, 9] cycles=[9, 4, 4] i=2, indices 2 and 6 were exchanged, output [1, 6, 5]
indices=[1, 6, 7, 0, 2, 3, 4, 5, 8, 9] cycles=[9, 4, 3] i=2, indices 2 and 7 were exchanged, output [1, 6, 7]
indices=[1, 6, 8, 0, 2, 3, 4, 5, 7, 9] cycles=[9, 4, 2] i=2, indices 2 and 8 were exchanged, output [1, 6, 8]
indices=[1, 6, 9, 0, 2, 3, 4, 5, 7, 8] cycles=[9, 4, 1] i=2, indices 2 and 9 were exchanged, output [1, 6, 9]
indices=[1, 6, 9, 0, 2, 3, 4, 5, 7, 8], shifting at 2:
        [      \0, 2, 3, 4, 5, 7, 8,/9]

indices=[1, 7, 0, 2, 3, 4, 5, 6, 8, 9] cycles=[9, 3, 8] i=1, indices 1 and 7 were exchanged, output [1, 7, 0]
indices=[1, 7, 2, 0, 3, 4, 5, 6, 8, 9] cycles=[9, 3, 7] i=2, indices 2 and 3 were exchanged, output [1, 7, 2]
indices=[1, 7, 3, 0, 2, 4, 5, 6, 8, 9] cycles=[9, 3, 6] i=2, indices 2 and 4 were exchanged, output [1, 7, 3]
indices=[1, 7, 4, 0, 2, 3, 5, 6, 8, 9] cycles=[9, 3, 5] i=2, indices 2 and 5 were exchanged, output [1, 7, 4]
indices=[1, 7, 5, 0, 2, 3, 4, 6, 8, 9] cycles=[9, 3, 4] i=2, indices 2 and 6 were exchanged, output [1, 7, 5]
indices=[1, 7, 6, 0, 2, 3, 4, 5, 8, 9] cycles=[9, 3, 3] i=2, indices 2 and 7 were exchanged, output [1, 7, 6]
indices=[1, 7, 8, 0, 2, 3, 4, 5, 6, 9] cycles=[9, 3, 2] i=2, indices 2 and 8 were exchanged, output [1, 7, 8]
indices=[1, 7, 9, 0, 2, 3, 4, 5, 6, 8] cycles=[9, 3, 1] i=2, indices 2 and 9 were exchanged, output [1, 7, 9]
indices=[1, 7, 9, 0, 2, 3, 4, 5, 6, 8], shifting at 2:
        [      \0, 2, 3, 4, 5, 6, 8,/9]

indices=[1, 8, 0, 2, 3, 4, 5, 6, 7, 9] cycles=[9, 2, 8] i=1, indices 1 and 8 were exchanged, output [1, 8, 0]
indices=[1, 8, 2, 0, 3, 4, 5, 6, 7, 9] cycles=[9, 2, 7] i=2, indices 2 and 3 were exchanged, output [1, 8, 2]
indices=[1, 8, 3, 0, 2, 4, 5, 6, 7, 9] cycles=[9, 2, 6] i=2, indices 2 and 4 were exchanged, output [1, 8, 3]
indices=[1, 8, 4, 0, 2, 3, 5, 6, 7, 9] cycles=[9, 2, 5] i=2, indices 2 and 5 were exchanged, output [1, 8, 4]
indices=[1, 8, 5, 0, 2, 3, 4, 6, 7, 9] cycles=[9, 2, 4] i=2, indices 2 and 6 were exchanged, output [1, 8, 5]
indices=[1, 8, 6, 0, 2, 3, 4, 5, 7, 9] cycles=[9, 2, 3] i=2, indices 2 and 7 were exchanged, output [1, 8, 6]
indices=[1, 8, 7, 0, 2, 3, 4, 5, 6, 9] cycles=[9, 2, 2] i=2, indices 2 and 8 were exchanged, output [1, 8, 7]
indices=[1, 8, 9, 0, 2, 3, 4, 5, 6, 7] cycles=[9, 2, 1] i=2, indices 2 and 9 were exchanged, output [1, 8, 9]
indices=[1, 8, 9, 0, 2, 3, 4, 5, 6, 7], shifting at 2:
        [      \0, 2, 3, 4, 5, 6, 7,/9]

indices=[1, 9, 0, 2, 3, 4, 5, 6, 7, 8] cycles=[9, 1, 8] i=1, indices 1 and 9 were exchanged, output [1, 9, 0]
indices=[1, 9, 2, 0, 3, 4, 5, 6, 7, 8] cycles=[9, 1, 7] i=2, indices 2 and 3 were exchanged, output [1, 9, 2]
indices=[1, 9, 3, 0, 2, 4, 5, 6, 7, 8] cycles=[9, 1, 6] i=2, indices 2 and 4 were exchanged, output [1, 9, 3]
indices=[1, 9, 4, 0, 2, 3, 5, 6, 7, 8] cycles=[9, 1, 5] i=2, indices 2 and 5 were exchanged, output [1, 9, 4]
indices=[1, 9, 5, 0, 2, 3, 4, 6, 7, 8] cycles=[9, 1, 4] i=2, indices 2 and 6 were exchanged, output [1, 9, 5]
indices=[1, 9, 6, 0, 2, 3, 4, 5, 7, 8] cycles=[9, 1, 3] i=2, indices 2 and 7 were exchanged, output [1, 9, 6]
indices=[1, 9, 7, 0, 2, 3, 4, 5, 6, 8] cycles=[9, 1, 2] i=2, indices 2 and 8 were exchanged, output [1, 9, 7]
indices=[1, 9, 8, 0, 2, 3, 4, 5, 6, 7] cycles=[9, 1, 1] i=2, indices 2 and 9 were exchanged, output [1, 9, 8]
indices=[1, 9, 8, 0, 2, 3, 4, 5, 6, 7], shifting at 2:
        [      \0, 2, 3, 4, 5, 6, 7,/8]

indices=[1, 9, 0, 2, 3, 4, 5, 6, 7, 8], shifting at 1:
        [    \0, 2, 3, 4, 5, 6, 7, 8,/9]

...

indices=[9, 8, 7, 0, 1, 2, 3, 4, 5, 6] cycles=[1, 1, 1] i=2, indices 2 and 9 were exchanged, output [9, 8, 7]
indices=[9, 8, 7, 0, 1, 2, 3, 4, 5, 6], shifting at 2:
        [      \0, 1, 2, 3, 4, 5, 6,/7]

indices=[9, 8, 0, 1, 2, 3, 4, 5, 6, 7], shifting at 1:
        [    \0, 1, 2, 3, 4, 5, 6, 7,/8]

indices=[9, 0, 1, 2, 3, 4, 5, 6, 7, 8], shifting at 0:
        [  \0, 1, 2, 3, 4, 5, 6, 7, 8,/9]

As to the details on how and why exactly this works - the answer is complicated and requires theoretical understanding of permutation cycles that I frankly don't have.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Can you add an explanation of how this works? $\endgroup$
    – Yuval Filmus
    Dec 26, 2020 at 19:40
  • $\begingroup$ @YuvalFilmus OK; I tried. $\endgroup$
    – Reinderien
    Dec 26, 2020 at 20:41
  • $\begingroup$ I'm not sure your explanation explains why the code works. $\endgroup$
    – Yuval Filmus
    Dec 26, 2020 at 22:05
  • $\begingroup$ @YuvalFilmus You're right, it doesn't; I've linked to a (long, detailed and tricky) answer that tackles this in depth. $\endgroup$
    – Reinderien
    Dec 26, 2020 at 22:12
3
$\begingroup$

The way Raymond Hettinger's itertools permutations works is by following the cyclical nature of permutations. And converting from a recursive to iterative function.

Establishing a recursive pattern

We can build a recursive function to show us the underlying pattern. We can build off of Yuval Filmus's recursive solution. However we should change the code to show all the values. So we can pass L and a list to pick to pick from.

def permutations(n, k):
    def inner(l, r):
        print(l, r)
        if len(l) == n:
            yield tuple(l)
        else:
            for v in r:
                _r = r[:]
                _r.remove(v)
                yield from inner(l + [v], _r)
    return inner([], list(range(k)))

If we run the above code we should be able to start seeing a pattern. This pattern is the same regardless of depth. I have grouped the output by depth and highlighted some numbers to make the pattern more obvious.

[] [0, 1, 2, 3, 4, 5, 6]

[⓪] [①, 2, 3, 4, 5, 6]
[①] [0, ②, 3, 4, 5, 6]
[②] [0, 1, ③, 4, 5, 6]
[③] [0, 1, 2, ④, 5, 6]
[④] [0, 1, 2, 3, ⑤, 6]
[⑤] [0, 1, 2, 3, 4, ⑥]
[6] [0, 1, 2, 3, 4, 5]

[0, ①] [②, 3, 4, 5, 6]
[0, ②] [1, ③, 4, 5, 6]
[0, ③] [1, 2, ④, 5, 6]
[0, ④] [1, 2, 3, ⑤, 6]
[0, ⑤] [1, 2, 3, 4, ⑥]
[0, 6] [1, 2, 3, 4, 5]

[1, ⓪] [②, 3, 4, 5, 6]
[1, ②] [0, ③, 4, 5, 6]
[1, ③] [0, 2, ④, 5, 6]
[1, ④] [0, 2, 3, ⑤, 6]
[1, ⑤] [0, 2, 3, 4, ⑥]
[1, 6] [0, 2, 3, 4, 5]

...

[0, 1, ②] [③, 4, 5, 6]
[0, 1, ③] [2, ④, 5, 6]
[0, 1, ④] [2, 3, ⑤, 6]
[0, 1, ⑤] [2, 3, 4, ⑥]
[0, 1, 6] [2, 3, 4, 5]

[0, 2, ①] [③, 4, 5, 6]
[0, 2, ③] [1, ④, 5, 6]
[0, 2, ④] [1, 3, ⑤, 6]
[0, 2, ⑤] [1, 3, 4, ⑥]
[0, 2, 6] [1, 3, 4, 5]

...

Optimizing the recursive solution

From this we can see rather than building a new list we can just swap indexes. After we have swapped to the end of the 'chunk' we have to revert the list to how it was when we entered the function so the caller doesn't get messed up.

def permutations(n, k):
    def inner(l, r):
        i = len(l)
        if i == n:
            yield tuple(l)
        else:
            l.append(r.pop(0))
            yield from inner(l, r)
            for j in range(len(r)):
                l[-1], r[j] = r[j], l[-1]
                yield from inner(l, r)
            r.append(l.pop())
    return inner([], list(range(k)))

We can join l and r together to make a single list. If we always return the first n values then it doesn't matter if the two are combined.

def permutations(n, k):
    def inner(i):
        if i == n:
            yield pool[:n]
        else:
            yield from inner(i + 1)
            for j in reversed(range(1, cycles[i])):
                pool[i], pool[-j] = pool[-j], pool[i]
                yield from inner(i + 1)
            pool[i:] = pool[i + 1:] + pool[i:i + 1]
    pool = list(range(k))
    cycles = list(range(k, k-n, -1))
    return inner(0)

Converting to an iterative algorithm

First we get n=1 working. This is really simple as it's just as simple for loop. Which is the body of the recursive function anyway.

def permutations(n, k):
    pool = list(range(k))
    cycles = list(range(k, k-n, -1))
    i = 0
    yield pool[:n]
    for j in reversed(range(1, cycles[i])):
        pool[i], pool[-j] = pool[-j], pool[i]
        yield pool[:n]
    pool[i:] = pool[i + 1:] + pool[i:i + 1]

Now the biggest challenge is getting the code to work with n=1 and n=2. To do this we can use a while True and a for loop. This is somewhat complicated so I'll show you how you could write a itertools.product function.

def product(n, k):
    pool = [0] * n
    yield tuple(pool)
    while True:
        for i in reversed(range(n)):
            pool[i] += 1
            if pool[i] != k:
                yield tuple(pool)
                break
            pool[i] = 0
        else:
            return

We can now convert permutations to work the same way for any n.

def permutations(n, k):
    pool = list(range(k))
    cycles = list(range(k, k - n, -1))
    r_range = range(n - 1, -1, -1)
    yield pool[:n]
    while True:
        for i in r_range:
            cycles[i] -= 1
            if cycles[i] > 0:
                j = cycles[i]
                pool[i], pool[-j] = pool[-j], pool[i]
                yield pool[:n]
                break
            pool[i:] = pool[i + 1:] + pool[i:i + 1]
            cycles[i] = k - i
        else:
            return
Improve this answer
$\endgroup$
4
  • $\begingroup$ Wait what? Why is this recursive? $\endgroup$
    – Reinderien
    Dec 26, 2020 at 23:48
  • $\begingroup$ @Reinderien sorry bit strapped for time at the moment, my answer may be a bit lacking at the end. Will happily expand tomorrow. The 'final' code isn't recursive but if you add the for loop back in it will magically line up. Try with 2,7 and you should be able to see clearly. The recursion comes from cycle if you ignore the swapping then it loops 5 times then 1 once for the 6, then 5 again... So it loops 7*6*5 times flattening the recursion. Please could you be a little more specific please whilst I'm asleep and I'll try my best to explain better tomorrow :) $\endgroup$
    – Peilonrayz
    Dec 27, 2020 at 0:37
  • $\begingroup$ I have a very simplistic understanding of "recursive" - this function doesn't call itself, so you must be operating under a more subtle definition than one I'm familiar with. $\endgroup$
    – Reinderien
    Dec 27, 2020 at 4:14
  • 1
    $\begingroup$ @Reinderien Oh, yeah I mean it in more non-CS way. For example writing the Fibonacci sequence as an iterative function doesn't detract from the recursive nature of the Fibonacci sequence. Additionally the CS definition is a bit odd; if you perform the stack manipulation yourself rather than leaving it to Python your recursive algorithm suddenly becomes non-recursive. Even though you've not actually changed how your code works - it's an iterative stack either way. Regardless I rewrote my answer because I wasn't happy with what I'd posted before. $\endgroup$
    – Peilonrayz
    Dec 27, 2020 at 12:02
2
$\begingroup$

The problem of iterating all partial permutations is closely related to the problem of generating a uniform random sequence $U$ of $k$ (u)nique integers from $0 \le U[j] < n$. The usual solution to that problem is first to generate a uniform (r)andom sequence of numbers $R$ satisfying

  • $|R| = k$
  • $0 \le R[j] < n - j$

then covert $R$ to $U$. So for example, given $R$, the $U$ would be:

$$\begin{array} {c|c} R & U \\ \hline [0, 0, 0] & [0, 1, 2] \\ [0, 0, 1] & [0, 1, 3] \\ [1, 1, 1] & [1, 2, 3] \\ [7, 0, 7] & [7, 0, 8] \\ \end{array}$$

So if $R[a] = x$ then $U[a] = y$, where $y$ is the $x'th$ smallest natural number, skipping those in $U[0 .. a-1]$. Generating $U$ from $R$ is typically done in $O(k(\log k)^2)$ time. $U[j]$ is calculated by doing a (very complicated) binary search a sorted set of the first $U[0..j-1]$ already calculated elements.

A partial permutation iterator can be written by enumerating $R$ in lexicographical ordering, then converting $R$ to $U$ in the usual way.

It can also be done much better though, because the iterator makes updates to $R$, $U$, and the (s)orted set of $U$ (call it $S$) in a predictable way. Each next() call of the permutation iterator changes $R$ in the following way:

  • $R[0 .. z-1]$ doesn't change
  • $R[z]$ is incremented by 1
  • $R[z+1 .. k]$ is set to 0

(for some index $z$). This means that $U[0 .. z - 1]$ doesn't change each iteration. So each iteration we can do the following steps:

  • $S$ can be shrunk to $|S| = z-1$ by removing $U[z .. k]$ (from the previous iteration) from it.
  • $U[z]$ can be calculated by looking at $R[z]$ and the current $S$
  • Insert $U[z]$ into $S$
  • $U[z + 1..k]$ can be calculated by enumerating a counter $c$ from zero, and if $c$ is not in $S$ then append it to the end of $U$, stop when $U$ is full.
  • $U[z + 1 .. k]$ can be inserted into the sorted $S$ to make $|S| = k$ (for the sake of the next iteration of the iterator) using the same technique as merge from mergesort

Each of the above steps can be done in linear $O(k)$ time.

This algorithm has a lot of overhead, so if $k$ is predictably small, it will be faster to do something like

for (U[0]=0; U[0] < n; U[0]++) {   
    for (U[1]=0; U[1] < n; U[1]++) {
        if (U[0] == U[1]) continue;
        // do your thing here
    }
 }

And if $n = k$ then a total permutation iterator will also be much faster. This $O(k)$ algorithm is almost entirely theoretical, since you'd need something like $k$ to be a small fraction of $n$, but large enough to not do the above forloop technique, for it to be ideal.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Wikipedia used to have an article on the problem of generating a random set of $k$ unique natural numbers less than $n$, but I can't find it anymore. If anyone can find a link to the details of that problem I'd appreciate it, my searches haven't turned anything up. $\endgroup$
    – DanielV
    Dec 27, 2020 at 18:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.