Bestimmen Sie bei einem dimensionalen Vektor mit reellen Einträgen die nächstliegende Permutation von in Bezug auf den Abstand.
Einzelheiten
- Wenn es bequemer ist, können Sie stattdessen Permutationen von verwenden. Wenn es mehrere nächstliegende Permutationen gibt, können Sie eine oder alternativ alle davon ausgeben.
- Der Abstand zwischen zwei Vektoren ist definiert als
- Wenn Sie möchten, können Sie davon ausgehen, dass die Eingabe ausschließlich aus Ganzzahlen besteht.
Beispiele
[0.5 1] -> [1 2], [2 1]
c*[1 1 ... 1] -> any permutation
[1 4 2 6 2] -> [1 4 3 5 2], [1 4 2 5 3]
[1 3 5 4 1] -> [2 3 5 4 1], [1 3 5 4 2]
[7 7 3 2 5 6 4 2] -> [8 7 3 2 5 6 4 1], [8 7 3 1 5 6 4 2], [7 8 3 2 5 6 4 1], [7 8 3 1 5 6 4 2]
[-2 4 5 7 -1 9 3] -> [1 4 5 6 2 7 3], [2 4 5 6 1 7 3], [1 4 5 7 2 6 3], [2 4 5 7 1 6 3]
[0 4 2 10 -1 10 5] -> [1 4 2 6 3 7 5], [1 4 3 6 2 7 5], [2 4 3 6 1 7 5], [3 4 2 6 1 7 5], [1 4 2 7 3 6 5], [1 4 3 7 2 6 5], [2 4 3 7 1 6 5], [3 4 2 7 1 6 5]
Octave-Skript zur Generierung weiterer Beispiele.
code-golf
math
combinatorics
permutations
optimization
fehlerhaft
quelle
quelle
v
, größer als sein werden0
? Oder zumindest nicht0
?v
können beliebige ganze Zahlen sein. (Weitere Beispiele hinzugefügt.)[1.6 2]
ist dies ein wichtiger Testfall (gieriger Algorithmus / lexikografische Sortierung gibt die falsche Antwort).Antworten:
Python 2 , 60 Bytes
Probieren Sie es online!
Verwendet die Null-Indizierung.
Ein schneller Algorithmus mit einer einfachen Idee. Wenn wir stattdessen die Eingabeliste permutieren müssen sie so nah machen zu(1,2,...,n) wie möglich, sollten wir einfach irgendwie es, wie weiter unten unter Beweis gestellt. Da wir stattdessen sind Permutation (1,2,...,n) , wählen wir die Permutation , dass die auf die gleiche Weise wie die Eingangsliste geordnet, wie in meiner Herausforderung eine Ordnung Imitate ( mit Ausnahme der Eingabe kann wiederholt). (Bearbeiten: Meilen wies auf diese identische Herausforderung hin , wo Dennis die gleiche Antwort hat .)
Beachten Sie, dass die einzige Eigenschaft von( 1 , 2 , . . . , N ) , dass ich verwendet wird , ist , dass es sortiert, damit der gleiche Algorithmus jede gegebene Liste permutieren funktionieren würde, seinen Abstand zu jeder festen Liste zu minimieren.
Im Code besteht der einzige Zweck
z=zip(l,range(len(l)))
darin, die Eingabeelemente zu unterscheiden, dh Bindungen zu vermeiden, während die gleichen Vergleiche zwischen ungleichen Elementen beibehalten werden. Wenn die Eingabe garantiert keine Wiederholungen hat, könnten wir diese entfernen und nur habenlambda l:map(sorted(l).index,l)
.quelle
05AB1E , 7 Bytes
Probieren Sie es online!
Erläuterung
quelle
Perl 6 , 44 Bytes
Probieren Sie es online!
Anonymer Codeblock, der die erste minimale Permutation mit einer Indexierung von 0 zurückgibt.
Erläuterung:
Ich glaube, ich kann das auch loswerden
.sum
und nur nach der Liste der absoluten Werte sortieren, aber ich bin mir nicht sicher, ob dies tatsächlich richtig ist, obwohl es meine aktuellen Testfälle besteht.quelle
[0.6 1]
(vorausgesetzt, wir sind mit 0 indiziert), wo Sie, wenn Sie für den ersten Wert optimieren,[1,0]
eine Punktzahl von 1,4 erhalten. Wenn Sie jedoch für den gesamten Vektor optimieren, ist die 1 an der zweiten Position für eine Punktzahl wertvoller von 0,6.Gelee , 8 Bytes
Probieren Sie es online!
quelle
Gelee , 5 Bytes
Ein monadischer Link, der eine Liste von Zahlen akzeptiert, die eine Liste von ganzen Zahlen ergibt.
Probieren Sie es online! Oder sehen Sie sich die Testsuite an .
Wie?
NB
L
(Länge) würde anstelle der Arbeit ,J
daœ?
eine ganze Zahl angegeben,n
auf der rechten Seite implizit den Bereich machen würde ,[1..n]
mit zu arbeiten, aberJ
ist eindeutig.quelle
Ruby ,
6360 BytesProbieren Sie es online!
Hier gibt es einen mathematischen Trick, der auch bei anderen Antworten hilfreich sein kann. Anstatt die Summe der absoluten Werte der Differenzen zu minimieren, maximieren wir die Summe der Produkte. Warum funktioniert das?
Das Minimieren der Summe von
(x-y) squared
ist nicht gleichbedeutend mit dem Minimieren der Summe von|x-y|
, aber es gibt immer eine gültige Antwort, es priorisiert nur das Reduzieren großer Unterschiede gegenüber kleinen, während die eigentliche Herausforderung zwischen den beiden gleichgültig ist.Aber
(x-y)*(x-y)
=x*x+y*y-2*x*y
. Da die quadratischen Terme für jede Permutation immer irgendwo in der Summe angezeigt werden, haben sie keinen Einfluss auf das Ergebnis, sodass wir dies vereinfachen können-2*x*y
. Die2
Faktoren heraus, so können wir zu vereinfachen-x*y
. Wenn wir dann von Minimieren zu Maximieren wechseln, können wir zu vereinfachenx*y
.Dies ist intuitiv vergleichbar mit der Beobachtung, dass Sie, wenn Sie versuchen, die Quadratmeterzahl mithilfe einer Reihe horizontaler und vertikaler Wände zu maximieren, am besten Wände miteinander kombinieren, die eng beieinander liegen, um Räume zu erstellen, die so groß wie möglich sind so nah wie möglich am Platz.
3*3 + 4*4 = 25
während3*4 + 4*3 = 24
.Bearbeiten: Speichert drei Bytes, indem eine Formatzeichenfolge generiert und ausgewertet wird, anstatt zip und sum zu verwenden.
quelle
Gaia , 13 Bytes
Probieren Sie es online!
quelle
JavaScript (ES6), 61 Byte
Basierend auf den Erkenntnissen von xnor .
Probieren Sie es online!
Kommentiert
JavaScript (ES6),
130128 BytesEs
mussdefinitiv einen direkteren Weg geben ...0-indiziert.
Probieren Sie es online! (mit 1-indiziertem Ausgang)
Wie?
quelle
Wolfram Language (Mathematica) , 14 Byte
Probieren Sie es online!
Basierend auf den Erkenntnissen von xnor .
quelle
Python 2 ,
149126112 Bytes-23 Bytes dank Mr. Xcoder
-14 Bytes dank xnor
Probieren Sie es online!
Verwendet Permutationen von (0 ... n-1).
quelle
functools
mehr brauchen .reduce
ist normalerweise übertrieben, besonders hier, wo Sie Sachen hinzufügen. Ich denke, du kannst es einfach tunsum(abs(p-q)for p,q in zip(x,a))
.Ohne Permutationspaket
Python 3 , 238 Bytes
Probieren Sie es online!
quelle
Wolfram Language (Mathematica) , 57 Byte
Probieren Sie es online!
quelle
Japt
-g
, 12 BytesVersuch es
Ersetzen Sie bei 0-indizierten die ersten 2 Bytes durch
m,
, um das Array stattdessen seinen Indizes zuzuordnen.quelle
J ,
258 BytesProbieren Sie es online!
Viel kürzere Antwort basiert auf der brillanten Idee von xnor.
ursprüngliche Antwort
J , 25 Bytes
Probieren Sie es online!
quelle