O desafio

Para um determinado conjunto de n números inteiros, escreva um programa que produzirá seu índice lexicográfico.

As regras

• A entrada deve ser apenas um conjunto de números inteiros não negativos separados por espaços.
• Você deve gerar o índice lexicográfico (intervalo de 0 a n! -1, inclusive) da permutação.
• Nenhuma biblioteca de permutação ou embutidos de permutação podem ser usados.
• Você não pode gerar o conjunto de permutações ou qualquer subconjunto de permutações da entrada para ajudá-lo a encontrar o índice.
• Você também não pode aumentar ou diminuir a permutação fornecida para a permutação seguinte / anterior (lexicograficamente).
• Pontos de bônus (-10 bytes) se você encontrar uma maneira de concluir isso sem usar fatoriais.
• O tempo de execução deve ser menor que 1 minuto para n = 100
• O código mais curto pela contagem de bytes ganha
• Vencedor escolhido terça-feira (22 de julho de 2014)

Mais sobre permutações

• http://www.monkeyphysics.com/articles/read/26/numbering_permutations.html
• Operação do grupo de permutação
• http://lin-ear-th-inking.blogspot.com/2012/11/enumerating-permutations-using.html

Exemplos

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 caracteres - 10 bônus)

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

Pontos de bônus por não usar fatoriais. A entrada deve ser fornecida no STDIN no formato descrito na pergunta. Você pode tentar o código online .

CJam, 31, com fatoriais

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

Tão legível. Muito embutido. Uau.

Utilizamos o fato de que o índice lexicográfico de uma permutação é a soma dos elementos das permutações do número de inversões acima desse elemento (valores após ele, mas abaixo dele) multiplicado pelo fatorial do número de elementos após ele. Em vez de avaliar essa expressão polinomial, termo a termo, usamos algo semelhante ao método de Horner .

Em vez de repetir os índices da matriz, removemos repetidamente o primeiro elemento da lista e processamos os elementos restantes. A expressão sorted(p).index(p.pop(0))conta o número de inversões após o primeiro índice, assumindo sua posição na lista classificada e, ao mesmo tempo, removendo.

Infelizmente, eu tive que usar o Python 2 e pegar mais 4 caracteres para raw_input(embora -1 para print) porque no Python 3 ele map(int,...)produz um objeto de mapa, que não suporta operações de lista,

Pitão (13 = 23-10)

JVPwdWJ=Z+*ZlJXovNJ;J)Z

Uma porta da minha resposta Python .

Uma tradução Python (com algumas coisas irrelevantes filtradas):

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)

Os números de entrada permanecem seqüências de caracteres, mas são classificados como ints usando eval como a chave. A lista é invertida, de modo que popassume a frente e não a traseira.

Cobra - 202

Obviamente, o Cobra não está realmente competindo neste.

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 bytes (15 - 10)

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

Isso é executado no tempo O ( n ² ) e é capaz de lidar com n = 100 facilmente.

Uso

   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

Explicação

#\.#.+/@(<{.)\.  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