Wyzwanie

Dla danego zestawu n liczb całkowitych napisz program, który wyświetli jego indeks leksykograficzny.

Zasady

• Dane wejściowe muszą być tylko zbiorem unikatowych nieujemnych liczb całkowitych oddzielonych spacjami.
• Powinieneś wypisać indeks leksykograficzny (zakres od 0 do n! -1 włącznie) permutacji.
• Nie można używać bibliotek permutacji ani wbudowanych permutacji.
• Nie możesz wygenerować zestawu permutacji ani żadnego podzbioru permutacji danych wejściowych, aby pomóc ci znaleźć indeks.
• Nie można również zwiększać ani zmniejszać danej permutacji do następnej / poprzedniej (leksykograficznie) permutacji.
• Punkty bonusowe (-10 bajtów), jeśli znajdziesz sposób, aby to zrobić bez użycia silni.
• Czas działania powinien być krótszy niż 1 minuta dla n = 100
• Wygrywa najkrótszy kod bajtowy
• Zwycięzca wybrany we wtorek (22 lipca 2014 r.)

Więcej informacji o permutacjach

• http://www.monkeyphysics.com/articles/read/26/numbering_permutations.html
• Operacja grupy permutacji
• http://lin-ear-th-inking.blogspot.com/2012/11/enumerating-permutations-using.html

Przykłady

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 znaków - 10 bonusów)

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

Punkty bonusowe za niestosowanie silni. Dane wejściowe należy podać na STDIN w formacie opisanym w pytaniu. Możesz wypróbować kod online .

CJam, 31, z silnią

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

Taki czytelny. Wiele wbudowanych. Łał.

Korzystamy z faktu, że indeks leksykograficzny permutacji jest sumą elementów permutacji liczby inwersji powyżej tego elementu (wartości po nim, ale poniżej niego) pomnożonej przez silnię liczby elementów po nim. Zamiast oceniać to wyrażenie wielomianowe termin po terminie, używamy czegoś podobnego do metody Hornera .

Zamiast zapętlać indeksy tablic, wielokrotnie usuwamy pierwszy element listy i przetwarzamy pozostałe elementy. Wyrażenie sorted(p).index(p.pop(0))zlicza liczbę inwersji za pierwszym indeksem, biorąc jego pozycję na posortowanej liście, jednocześnie wykonując usunięcie.

Niestety musiałem użyć Pythona 2 i wziąć 4 dodatkowe znaki dla raw_input(chociaż -1 dla print), ponieważ w Pythonie 3 map(int,...)tworzy obiekt mapy, który nie obsługuje operacji na listach,

Pyth (13 = 23-10)

JVPwdWJ=Z+*ZlJXovNJ;J)Z

Port mojej odpowiedzi w języku Python .

Tłumaczenie Pythona (z pominięciem niektórych nieistotnych elementów):

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)

Liczby wejściowe pozostają ciągami, ale są sortowane jako liczby całkowite za pomocą eval jako klucza. Lista jest odwrócona, dzięki czemu popzajmuje przód, a nie tył.

Kobra - 202

Oczywiście Cobra tak naprawdę nie konkuruje w tym przypadku.

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 bajtów (15–10)

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

Działa to w czasie O ( n ² ) i jest w stanie łatwo obsłużyć n = 100.

Stosowanie

   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

Wyjaśnienie

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