Skip to main content
3 of 3
added 42 characters in body
Ana
  • 21
  • 3

Heap's Algorithm for k-permutations?

Heap's Algorithm enumerates the permutations of a set of N objects. It's described as:

  • Permute the elements in positions 1 to n−1 by applying this algorithm to those elements.
  • Apply the following steps n−1 times. Increment counter i=1 after each iteration.
    • Swap element in position n with one of the other elements in the following way.
      • If n is odd, swap elements in positions 1 and n
      • If n is even, swap elements in position i and n
    • Permute the elements in positions 1 to n−1 by applying this algorithm to those elements.

How can Heap's Algorithm be used to generate the k-permutations of N objects? That is, given a set of N objects, enumerate the ordered selection of k items from the N objects. How would the above algorithm be changed?

Ana
  • 21
  • 3