# Efficient algorithms to generate partial permutations?

I want to efficiently generate partial permutations.

That is, I want to generate the set of ordered arrangements of K distinct elements selected from a set from N items. For example, with the set ABCDE where N=5, if K=2, then the partial permutation set is AB, AC, AD, AE, BA, BC, BD, BE, CA, CB, CD, CE, DA, DB, DC, DE, EA, EB, EC, ED.

The obvious way to do this is to repeatedly concatenate lists, and add/remove items from lists. I'm looking for a more efficient algorithm.

There are multiple algorithms for efficiently generating the full set of permutations of a set of N items, but I have not know of any that generate the set of partial permutations.

• You can combine an efficient generator of combinations with an efficient generator of permutations. Aug 12 at 13:06

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)