BuringStraw

Purpose#

Calculate the position of a permutation in all permutations.

Derivation#

Follow the process in the PPT.

Example: For the set {1,2,3}, what is the position of {3,2,1} in all permutations?

Before {3,2,1}, there are three cases:

1. The first item < 3:

   It must be before {3,2,1}, at this point, the first item has two choices, the last two items can be any, so there are a total of

   possibilities.

2. The first item = 3:

   If the second item < 2, the result is less than {3,2,1}.

3. The first two items are equal:

   There is no permutation smaller than {3,2,1}.

In total, there are 2*2!+1*1!+0=5 possibilities.

Calculation Formula#

where pi represents the number of elements smaller than ai in the unselected elements.

Reverse Calculation#

Given a position, calculate the permutation result.

Example: For the set {1,2,3,4,5,6}, find the 100th permutation (counting from 0).

Um... let's just refer to the PPT.