Archived

This topic is now archived and is closed to further replies.

Generating Nth Permutation

This topic is 5481 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

Recommended Posts

I''m looking for a way to generate the Nth permutation of a lexographically order set. I know of STL''s next_permutation(), but I''d like to be able to get the Nth without generating the other N-1 (if this is possible). Does the STL include any algorithms that can do this? Are there any license-free C++ libraries available online? Alternatively, are there any good websites that explain this technique? Thanks

Share on other sites
I would try to solve this recursively by determining one digit at a time. For instance, assume your set was 1234, and you want permutation 8.
If we assume the first digit is 1, there are 3! = 6 orderings of the rest of the digits. So the first digit can''t be 1. Now, let''s assume that it''s 2(and now we want permutation 8-6=2). There are still 3! orderings, which is > 2, so we have determined that the first digit is 2. Now, apply this algorithm recursively to the rest of the set.

1. 1
2. 2
3. 3
Rutin
15
4. 4
5. 5

• 13
• 26
• 10
• 11
• 9
• Forum Statistics

• Total Topics
633728
• Total Posts
3013575
×