You can use immutable, singly linked lists to generate partial permutations in $O(n \operatorname{choose} k)$ operations and memory, which is likely optimal. Here's an example in the Scala programming language:
class PartialPermutations( n: Int, k: Int ):
require(n >= k)
require(0 <= k)
def foreach( action: List[Int] => Unit ): Unit =
def recursion( n: Int, k: Int, sample: List[Int] ): Unit =
if k == 0 then
action(sample)
else
for i <- n to k by -1 do
recursion(i-1, k-1, i-1 :: sample);
end for
end if
end recursion
recursion(n, k, List.empty[Int])
end foreach
end PartialPermutations
for x <- PartialPermutations(8,3) do
println(x)
end for
Note that the samples are returned in descending reverse lexicographical order. An ascending standard lexicographical ordering can be achieved with a few modifications.
The basic idea of the algorithm is to:
- If $k = 0$, return an empty list
- Take $\operatorname{partialPermutations}(n-1,k-1)$ and append $n-1$ to each of it
- Take $\operatorname{partialPermutations}(n-2,k-1)$ and append $n-2$ to each of it
- ...
- Take $\operatorname{partialPermutations}(k-1,k-1)$ and append $k-1$ to each of it
While this performance is fancy in theory it will likely not give You any performance benefit in practice, because whatever you do with these partial permutations is very likely an $\mathcal{O}\left(k\cdot\left(n \operatorname{choose} k\right)\right)$ operation anyways. So here is a slightly simpler array-based $\mathcal{O}\left(k\cdot\left(n \operatorname{choose} k\right)\right)$ implementation in JavaScript:
function* partialPermutations( n, k )
{
const sample = new Array(k)
function* recursion( n, k ) {
if( k <= 0 )
yield sample.slice() // <- make a copy
else for( let i=n; i-- >= k; i ) {
sample[k-1] = i
yield* recursion(i, k-1)
}
}
yield* recursion(n,k)
}
for( const x of partialPermutations(8,3) )
console.log(x)