Le défi

Pour un ensemble donné de n entiers, écrivez un programme qui affichera son index lexicographique.

Les règles

• L'entrée ne doit être qu'un ensemble d'entiers non négatifs uniques séparés par des espaces.
• Vous devez sortir l'index lexicographique (plage de 0 à n! -1 inclus) de la permutation.
• Aucune bibliothèque de permutation ou intégration de permutation ne peut être utilisée.
• Vous ne pouvez pas générer l'ensemble de permutations ou tout sous-ensemble de permutations de l'entrée pour vous aider à trouver l'index.
• Vous ne pouvez pas non plus incrémenter ou décrémenter la permutation donnée à la permutation suivante / précédente (lexicographiquement).
• Points bonus (-10 octets) si vous trouvez un moyen de le faire sans utiliser de factoriels.
• Le temps d'exécution doit être inférieur à 1 minute pour n = 100
• Le plus court code par nombre d'octets gagne
• Gagnant choisi mardi (22 juillet 2014)

En savoir plus sur les permutations

• http://www.monkeyphysics.com/articles/read/26/numbering_permutations.html
• Fonctionnement du groupe de permutation
• http://lin-ear-th-inking.blogspot.com/2012/11/enumerating-permutations-using.html

Exemples

0 1 2 --> 0
0 2 1 --> 1
1 0 2 --> 2
1 2 0 --> 3
2 0 1 --> 4
2 1 0 --> 5
0 1 2 3 4 5 6 7 --> 0
0 1 2 3 4 5 7 6 --> 1
0 1 2 3 4 6 5 7 --> 2
1 3 5 17        --> 0
781 780 779 13  --> 23
81 62 19 12 11 8 2 0 --> 40319
195 124 719 1 51 6 3 --> 4181

GolfScript, 12 (22 caractères - 10 bonus)

~]0\.,{.,@*\.(@$?@+\}*

Points bonus pour ne pas utiliser les factoriels. L'entrée doit être donnée sur STDIN dans le format déstructuré dans la question. Vous pouvez essayer le code en ligne .

CJam, 31 ans, avec factoriels

q~]{__(f<0+:+\,,(;1+:**\(;}h]:+

Python 2 (77 = 87-10)

p=map(int,raw_input().split())
s=0
while p:s=s*len(p)+sorted(p).index(p.pop(0))
print s

Tellement lisible. Beaucoup intégré. Sensationnel.

Nous utilisons le fait que l'indice lexicographique d'une permutation est la somme sur les éléments des permutations du nombre d'inversions au-dessus de cet élément (valeurs après mais en dessous) multiplié par la factorielle du nombre d'éléments après. Plutôt que d'évaluer cette expression polynomiale terme par terme, nous utilisons quelque chose qui ressemble à la méthode de Horner .

Plutôt que de boucler sur les indices de tableau, nous supprimons à plusieurs reprises le premier élément de la liste et traitons les autres éléments. L'expression sorted(p).index(p.pop(0))compte le nombre d'inversions au-delà du premier indice en prenant sa position dans la liste triée, tout en effectuant la suppression.

Malheureusement, j'ai dû utiliser Python 2 et prendre 4 caractères de plus pour raw_input(bien que -1 pour print) car dans Python 3 le map(int,...)produit un objet de carte, qui ne prend pas en charge les opérations de liste,

Pyth (13 = 23-10)

JVPwdWJ=Z+*ZlJXovNJ;J)Z

Un portage de ma réponse Python .

Une traduction Python (avec des trucs non pertinents filtrés):

Z=0
J=rev(split(input()," "))
while J:
 Z=plus(times(Z,len(J)),index(order(lambda N:eval(N),J),J.pop()))
print(Z)

Les numéros d'entrée restent des chaînes mais sont triés en entiers en utilisant eval comme clé. La liste est inversée, ce qui popprend l'avant plutôt que l'arrière.

Cobra - 202

De toute évidence, Cobra n'est pas vraiment en compétition dans celui-ci.

class P
    var n=0
    var t=CobraCore.commandLineArgs[1:]
    def main
        .f(.t[0:0])
    def f(l as List<of String>)
        if.t.count==l.count,print if(.t<>l,'',.n+=1)
        else,for i in.t.sorted,if i not in l,.f(l+[i])

J, 5 octets (15-10)

#\.#.+/@(<{.)\.

Cela fonctionne en temps O ( n ² ) et est capable de gérer facilement n = 100.

Usage

   f =: #\.#.+/@(<{.)\.
   f 0 1 2
0
   f 0 2 1
1
   f 1 0 2
2
   f 1 2 0
3
   f 2 0 1
4
   f 2 1 0
5
   f 0 1 2 3 4 5 6 7
0
   f 0 1 2 3 4 5 7 6
1
   f 0 1 2 3 4 6 5 7
2
   f 1 3 5 17
0
   f 781 780 779 13
23
   f 81 62 19 12 11 8 2 0
40319
   f 195 124 719 1 51 6 3
4181
   NB. A. is the builtin for permutation indexing
   timex 'r =: f 927 A. i. 100'
0.000161
   r
927

Explication

#\.#.+/@(<{.)\.  Input: array P
             \.  For each suffix of P
          {.       Take the head
         <         Test if it is greater than each of that suffix
     +/@           Sum, count the number of times it is greater
#\.              Get the length of each suffix of P
   #.            Convert to decimal using a mixed radix