Enumerating all partial permutations of given length in lexicographic order

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.

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

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

StackExchange Computer Science Q#133662, answer score: 4