Numeração de permutação

9

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

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
Kyle McCormick
fonte
11
Podemos ter mais tempo até que um vencedor seja escolhido? Três dias é muito pouco tempo.
Xnor

Respostas:

4

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 .

Howard
fonte
Haha não é exatamente o que eu estava procurando quando disse "sem usar fatoriais", mas acho que conta. Kudos
Kyle McCormick
4

CJam, 31, com fatoriais

q~]{__(f<0+:+\,,(;1+:**\(;}h]:+
jimmy23013
fonte
Por que ainda estou votando? A resposta do GolfScript pode ser reescrita no CJam com apenas 23 caracteres.
jimmy23013
6
Porque as pessoas gostam da sua resposta.
see
1

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,

xnor
fonte
1

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.

xnor
fonte
1

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])
Furioso
fonte
0

J, 5 bytes (15 - 10)

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

Isso é executado no tempo O ( n 2 ) 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
milhas
fonte