Efficient algorithms to generate partial permutations?

Question

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.

Answer 1

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)