Permutationsnummerierung

9

Die Herausforderung

Schreiben Sie für einen bestimmten Satz von n ganzen Zahlen ein Programm, das seinen lexikografischen Index ausgibt.

Die Regeln

  • Die Eingabe darf nur eine Reihe eindeutiger nicht negativer Ganzzahlen sein, die durch Leerzeichen getrennt sind.
  • Sie sollten den lexikografischen Index (Bereich 0 bis einschließlich n! -1) der Permutation ausgeben.
  • Es dürfen keine Permutationsbibliotheken oder Permutationsintegrationen verwendet werden.
  • Möglicherweise generieren Sie keine Permutationsmenge oder eine Teilmenge von Permutationen der Eingabe, um den Index zu finden.
  • Sie können die angegebene Permutation auch nicht auf die nächste / vorherige (lexikografisch) Permutation erhöhen oder verringern.
  • Bonuspunkte (-10 Bytes), wenn Sie einen Weg finden, dies ohne Verwendung von Fakultäten zu vervollständigen.
  • Die Laufzeit sollte für n = 100 weniger als 1 Minute betragen
  • Die kürzeste Anzahl von Code pro Byte gewinnt
  • Gewinner ausgewählt Dienstag (22. Juli 2014)

Weitere Informationen zu Permutationen

Beispiele

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
quelle
1
Können wir mehr Zeit haben, bis ein Gewinner ausgewählt wird? Drei Tage sind zu wenig Zeit.
xnor

Antworten:

4

GolfScript, 12 (22 Zeichen - 10 Bonus)

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

Bonuspunkte für die Nichtverwendung von Fakultäten. Die Eingabe muss auf STDIN in dem in der Frage beschriebenen Format erfolgen. Sie können den Code online ausprobieren .

Howard
quelle
Haha, nicht ganz das, wonach ich gesucht habe, als ich "ohne Fakultäten" sagte, aber ich nehme an, es zählt. Kudos
Kyle McCormick
4

CJam, 31, mit Fakultäten

q~]{__(f<0+:+\,,(;1+:**\(;}h]:+
jimmy23013
quelle
Warum bekomme ich immer noch positive Stimmen? Die GolfScript-Antwort kann in CJam mit nur 23 Zeichen umgeschrieben werden.
Jimmy23013
6
Weil die Leute deine Antwort mögen.
siehe
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

So lesbar. Viel eingebaut. Wow.

Wir verwenden die Tatsache, dass der lexikografische Index einer Permutation die Summe über den Elementen der Permutationen der Anzahl der Inversionen über diesem Element (Werte danach, aber darunter) multipliziert mit der Fakultät der Anzahl der Elemente danach ist. Anstatt diesen polynomartigen Ausdruck Begriff für Begriff zu bewerten, verwenden wir etwas, das der Horner-Methode ähnelt .

Anstatt die Array-Indizes zu durchlaufen, entfernen wir wiederholt das erste Element der Liste und verarbeiten die verbleibenden Elemente. Der Ausdruck sorted(p).index(p.pop(0))zählt die Anzahl der Inversionen nach dem ersten Index, indem er seine Position in der sortierten Liste einnimmt und gleichzeitig die Entfernung durchführt.

Leider musste ich Python 2 verwenden und 4 weitere Zeichen für raw_input(obwohl -1 für print) verwenden, da in Python 3 map(int,...)ein Kartenobjekt erzeugt wird, das keine Listenoperationen unterstützt.

xnor
quelle
1

Pyth (13 = 23-10)

JVPwdWJ=Z+*ZlJXovNJ;J)Z

Ein Port meiner Python-Antwort .

Eine Python-Übersetzung (mit einigen irrelevanten herausgefilterten Dingen):

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)

Die eingegebenen Nummern bleiben Zeichenfolgen, werden jedoch als Ints sortiert, indem eval als Schlüssel verwendet wird. Die Liste ist umgekehrt, so dass popeher die Vorderseite als die Rückseite verwendet wird.

xnor
quelle
1

Cobra - 202

Offensichtlich konkurriert Cobra in diesem Fall nicht wirklich.

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])
Οurous
quelle
0

J, 5 Bytes (15 - 10)

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

Dies läuft in O ( n 2 ) Zeit und ist in der Lage, n = 100 leicht zu handhaben .

Verwendungszweck

   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

Erläuterung

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