Efficiently calculate next permutation of length k from n choices

Question

I need to efficiently calculate the next permutation of length k from n choices. Wikipedia lists a great algorithm for computing the next permutation of length n from n choices.

The best thing I can come up with is using that algorithm (or the Steinhaus–Johnson–Trotter algorithm), and then just only considering the first k items of the list, and iterating again whenever the changes are all above that position.

Constraints:

• The algorithm must calculate the next permutation given nothing more than the current permutation. If it needs to generate a list of all permutations, it will take up too much memory.
• It must be able to compute a permutation of only length k of n (this is where the other algorithm fails

Non-constraints:

• Don't care if it's in-place or not
• I don't care if it's in lexographical order, or any order for that matter
• I don't care too much how efficiently it computes the next permutation, within reason of course, it can't give me the next permutation by making a list of all possible ones each time.

Answer 1

You can break this problem down into two parts:

1) Find all subsets of size k from a set of size n.

2) For each such subset, find all permutations of a subset of size k.

The referenced Wikipedia article provides an algorithm for part 2, so I won't repeat it here. The algorithm for part 1 is pretty similar. For simplicity, I'll describe it for "find all subsets of size k of the integers [0...n-1].

1) Start with the subset [0...k-1]

2) To get the next subset, given a subset S:

2a) Find the smallest j such that j ∈ S ∧ j+1 ∉ S. If j == n-1, there is no next subset; we're done.

2b) The elements less than j form a sequence i...j-1 (since if any of those values were missing, j wouldn't be minimal). If i is not 0, replace these elements with i-i...j-i-1. Replace element j with element j+1.