0
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ You can combine an efficient generator of combinations with an efficient generator of permutations. $\endgroup$ Aug 12 at 13:06

1 Answer 1

0
$\begingroup$

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)
$\endgroup$

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.