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.
- Swap element in position n with one of the other elements in the following way.
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?