CODEWITHSUNDEEP
permutation
user1805103
user1805103

Reputation: 129

Generating Permutations without Repetition Using Index

Suppose you have a sequence of numbers, e.g., {1, 2, 3, 4, 5). from which you want all the permutations without repetition, choosing two elements.

Thus, {1,2}, {1,3}, {1,4}, {1,5}, {2,1}, {2,3}, {2,4} ...

Given an index of the permutation number, e.g., the 6th permutation, is there some easy approach to calculate what that permutation (here {2,4} using zero indexing) looks like?

I see approaches for combinations like: https://math.stackexchange.com/questions/1368526/fast-way-to-get-a-combination-given-its-position-in-reverse-lexicographic-or

I am looking for something similar for my problem. I am using C++.

I have looked at Gray Codes, Lermer Codes, Combinadics, Factoradics, etc. but none of these seem quite right.

Thanks for any help.

Upvotes: 1

Views: 558

Answers (1)

weston
weston

Reputation: 54791

If you imagine the pairs filling a grid, wrapping to a new row each time the first number has to change. There will be sequence.length-1 columns.

{1,2}, {1,3}, {1,4}, {1,5},
{2,1}, {2,3}, {2,4}, {2,5},
{3,1}, {3,2}, {3,4}, {3,5},
{4,1}, {4,2}, {4,3}, {4,5},
{5,1}, {5,2}, {5,3}, {5,4},

Find the row and column of the permutation number and then look up the values from the sequence.

val s // sequence
val p // 0 based permutation number

val row = p / (s.length-1) // integer divide (round down)
val col = p % (s.length-1) // remainder
if (col >= row) {
    col = col + 1 // to prevent repeat
}
val pair = { s[row], s[col] }

Example:

val s = {1, 2, 3, 4, 5} //sequence
val p  = 6
row = 1  (6 / 4 rounded down)
col = 2  (remainer of 6 / 4)
col -> 3 increase as larger than or equal to first index
val pair = { 2, 4 }

Upvotes: 2

Related Questions