1
$\begingroup$

I'm just trying to write a little algorithm. I've got nine objects, so there's 9! permutations. My question is, is there a way of turning a number from 1 to 9! into a permutation?

for example, f(1)=[1,2,3,4,5,6,7,8,9], f(2)=[1,2,3,4,5,6,7,9,8] or something similar.

Each number should have a unique ordering, and vice versa.

I know it's possible to write out everything into an array, but that's very memory taxing. Is there a simpler way of doing it?

Improve this question
$\endgroup$
1
  • $\begingroup$ This is called permutation unranking. See this Wikipedia section for an approach (see in particular the example for the 2982nd permutation of {0..6}). Essentially, divide your number by 8! to get the first digit. Then remove that digit from the set and proceed in similar fashion for the remaining 8 digits. $\endgroup$
    – Cătălin Frâncu
    Commented Jun 20, 2022 at 8:36

1 Answer 1

Reset to default
2
$\begingroup$

Use the factorial number system.

See also https://oeis.org/wiki/Ranking_and_unranking_functions, Given a permutation of 0..N-1, determine the index of that permutation in the lexicographic ordering of all permutations of 0..N-1, in linear time for more background.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.