Indication 1

une permutation de taille $n$ peut être construite à partir d'une permutation de taille $n-1$ en rajoutant le nombre $n$ à toutes les positions possible.

Par exemple, à partir de la permutation $12$, on construit

$12~3$

$1~3~2$

$3~12$.

Et à partir de la permutation $21$, on construit

$21~3$

$2~3~1$

$3~21$

Indication 2

Les permutations de l'ensemble [1,2,3] par ordre lex sont dans l'ordre :

• les permutations commençant par 1, suivi des permutations de l'ensemble [2,3] dans l'ordre lex
• les permutations commençant par 2, suivi des permutations de l'ensemble [1,3] dans l'ordre lex
• les permutations commençant par 3, suivi des permutations de l'ensemble [1,2] dans l'ordre lex

Remarquez qu'il faudra faire plusieurs appels récursifs : 1 pour chaque valeur de l'ensemble.

Indication 3

Si votre permutation commence par un nombre $k$, vous savez déjà que toutes les permutations qui commencent par $k' < k$ avec $k'$ dans la liste des nombres sont plus petites dans l'ordre lexicographique : combien sont-elles ? A ce nombre, vous devez ajouter le rang de votre permutation parmi celles qui commencent par $k$ (récursion...).

Indication 4

Si votre liste $s$ est de taille $n$, les indices vont de 0 à $n! -1$. Quels sont les indices des permtuations qui commencent par le premier nombre de la liste ? Par le second ? Etc. Ce raisonnement s'applique récursivement.