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
- http://www.monkeyphysics.com/articles/read/26/numbering_permutations.html
- Permutationsgruppenoperation
- http://lin-ear-th-inking.blogspot.com/2012/11/enumerating-permutations-using.html
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
code-golf
math
combinatorics
set-theory
permutations
Kyle McCormick
quelle
quelle
Antworten:
GolfScript, 12 (22 Zeichen - 10 Bonus)
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 .
quelle
CJam, 31, mit Fakultäten
quelle
Python 2 (77 = 87-10)
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ürprint
) verwenden, da in Python 3map(int,...)
ein Kartenobjekt erzeugt wird, das keine Listenoperationen unterstützt.quelle
Pyth (13 = 23-10)
Ein Port meiner Python-Antwort .
Eine Python-Übersetzung (mit einigen irrelevanten herausgefilterten Dingen):
Die eingegebenen Nummern bleiben Zeichenfolgen, werden jedoch als Ints sortiert, indem eval als Schlüssel verwendet wird. Die Liste ist umgekehrt, so dass
pop
eher die Vorderseite als die Rückseite verwendet wird.quelle
Cobra - 202
Offensichtlich konkurriert Cobra in diesem Fall nicht wirklich.
quelle
J, 5 Bytes (15 - 10)
Dies läuft in O ( n 2 ) Zeit und ist in der Lage, n = 100 leicht zu handhaben .
Verwendungszweck
Erläuterung
quelle