Permutationen in der Verkleidung

17

Bestimmen Sie bei einem dimensionalen Vektor mit reellen Einträgen die nächstliegende Permutation von in Bezug auf den Abstand.nvp(1,2,...,n)l1

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.(0,1,...,n-1)
  • Der l1 Abstand zwischen zwei Vektoren ist definiert alsu,v
    d(u,v)=ich|uich-vich|.
  • 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.

fehlerhaft
quelle
Sind wir garantiert, dass alle Elemente von v, größer als sein werden 0? Oder zumindest nicht 0?
Shaggy
1
Nein, die Einträge von vkönnen beliebige ganze Zahlen sein. (Weitere Beispiele hinzugefügt.)
Fehler
Wenn es sich um reelle Zahlen handeln kann, [1.6 2]ist dies ein wichtiger Testfall (gieriger Algorithmus / lexikografische Sortierung gibt die falsche Antwort).
Histokrat
2
In Verkleidung duplizieren? Ich bin mir nicht sicher, ob es als solches geschlossen werden sollte, da es nicht offensichtlich ist, dass es sich um dieselbe Aufgabe handelt (wie jetzt von xnor bewiesen).
Arnauld
1
(In der Tat ist es nicht die gleiche Aufgabe, aber alle Lösungen der verknüpften Herausforderung sind Lösungen dieser.)
Arnauld

Antworten:

13

Python 2 , 60 Bytes

def f(l):z=zip(l,range(len(l)));print map(sorted(z).index,z)

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 .)

Claim: eine Permutation der Liste l , die zu seiner Entfernung minimiert (1,2,...,n) ist l sortiert.

Beweis: Betrachte eine andere Permutation l von l . Wir werden beweisen , es kann nicht besser sein als l sortiert.

Wählen Sie zwei Indizes ich,j , die l nicht in der richtigen Reihenfolge hat, d. H. ich<j aber lich>lj . Wir zeigen , dass sie Swapping nicht erhöhen kann den Abstand zu (1,2,...,n) . Wir stellen fest, dass Swap den Beitrag dieser beiden Elemente wie folgt ändert:

|lich-ich|+|lj-j||lich-j|+|lj-ich|.

Hier ist eine gute Möglichkeit zu zeigen, dass dies keine Steigerung sein kann. Stellen Sie sich zwei Personen vor, die auf einer Zahlenlinie gehen, eine von lich nach ich und die andere von lj nach j . Die Gesamtstrecke, die sie zurücklegen, ist der Ausdruck auf der linken Seite. Da ich<j aber lich>lj , wechseln sie, wer auf der Zahlenlinie höher ist, was bedeutet, dass sie irgendwann während ihrer Spaziergänge überqueren müssen, nennen es p . Aber wenn sie p erreichenpDann konnten sie ihre Ziele tauschen und die gleiche Gesamtstrecke zurücklegen. Und dann kann es nicht schlimmer sein, dass sie von Anfang an zu ihren vertauschten Zielen gelaufen sind, anstatt p als Wegpunkt zu verwenden, der die Gesamtentfernung auf der rechten Seite angibt.

So, Sortier- zwei out-of-order - Elemente in l macht ihre Entfernung zu (1,2,...,n) kleiner oder gleich ist . Wenn Sie diesen Vorgang wiederholen, wird l schließlich sortiert . So l sortiert ist mindestens so gut wie l für jede Wahl von l , das heißt , es als optimal oder für eine optimale gebunden.

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 haben lambda l:map(sorted(l).index,l).

xnor
quelle
brillante Einsicht
Jonah
Sie haben dies vereinfacht, um die Bestellung zu finden .
Meilen
@miles Das ist ziemlich lustig, ich habe diese Herausforderung komplett vergessen, obwohl ich eine Antwort geschrieben habe, und Dennis hat genau diese Python-Antwort, die ich beim Golfen unterstützt habe.
14.
Dieser "visuelle Beweis" ist ordentlich. Ich hatte die gleiche Idee, musste aber jeden Fall dieser Formel auslegen, um es zu beweisen. Als Nebenbemerkung werden in diesem Beitrag einige Alternativen zum Erhalten von Rängen in Python mithilfe von Bibliotheken von Drittanbietern gezeigt .
Joel
5

05AB1E , 7 Bytes

āœΣαO}н

Probieren Sie es online!


Erläuterung

ā              # get the numbers 1 to len(input) + 1
 œ             # Permutations of this
  Σ  }         # Sort by ...
   α           # Absolute difference
    O          # Sum these
      н        # And get the first one 
               # implicitly print
Abgelaufene Daten
quelle
1
Immer wenn ich erstaunt bin, was kann 05AB1E nicht ?
Der zufällige Kerl
5
@Therandomguy In 05AB1E können nicht viele Dinge erledigt werden, aber es ist ziemlich schlecht bei: Regex-basierten Herausforderungen; matrixbasierte Herausforderungen (obwohl dies nach einigen neuen Buildins verbessert wurde); Mangel an imaginären Zahlen; datums- / zeitbezogene Herausforderungen; usw. Obwohl es schwierig ist, kann es dennoch in der Regel durchgeführt werden. Um zwei Beispiele zu nennen: Der Countdown für den Arbeitstag (zum nächsten Tag gehen und den Wochentag manuell abrufen); Quine gibt sich binär aus (die UTF-8-Konvertierung erfolgt manuell).
Kevin Cruijssen
@Grimy sollte jetzt behoben sein :)
Abgelaufene Daten
3

Perl 6 , 44 Bytes

{permutations(+$_).min((*[]Z-$_)>>.abs.sum)}

Probieren Sie es online!

Anonymer Codeblock, der die erste minimale Permutation mit einer Indexierung von 0 zurückgibt.

Erläuterung:

{                                          }   # Anonymous code block
 permutations(+$_)                             # From the permutations with the same length
                  .min(                   )    # Find the minimum by
                                      .sum       # The sum of
                                >>.abs           # The absolute values of
                       (*[]Z-$_)                 # The zip subtraction with the input

Ich glaube, ich kann das auch loswerden .sumund 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.

Scherzen
quelle
1
Das hat mir auch das Hirn gebrochen (oder die meist äquivalente Frage: "Funktioniert dafür ein gieriger Algorithmus?"). Das einfachste Gegenbeispiel ist [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.
Histokrat
2

Gelee , 5 Bytes

Œ¿œ?J

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?

Œ¿œ?J - Link: list of numbers, X
Œ¿    - Index of X in a lexicographically sorted list of
         all permutations of X's items
    J - range of length of X
  œ?  - Permutation at the index given on the left of the
         items given on the right

NB L(Länge) würde anstelle der Arbeit , Jda œ?eine ganze Zahl angegeben, nauf der rechten Seite implizit den Bereich machen würde , [1..n]mit zu arbeiten, aber Jist eindeutig.

Jonathan Allan
quelle
2

Ruby , 63 60 Bytes

->v{[*1..v.size].permutation.max_by{|p|eval [p,0]*'*%p+'%v}}

Probieren 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) squaredist 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. Die 2Faktoren heraus, so können wir zu vereinfachen -x*y. Wenn wir dann von Minimieren zu Maximieren wechseln, können wir zu vereinfachen x*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 = 25während 3*4 + 4*3 = 24.

Bearbeiten: Speichert drei Bytes, indem eine Formatzeichenfolge generiert und ausgewertet wird, anstatt zip und sum zu verwenden.

Histokrat
quelle
2
y|x-y|(x-y)2
1

Gaia , 13 Bytes

e:l┅f⟪D†Σ⟫∫ₔ(

Probieren Sie es online!

e:		| eval and dup input
l┅f		| push permutations of [1..length(input)]
⟪   ⟫∫ₔ		| iterate over the permutations, sorting with minimum first
 D†Σ		| the sum of the absolute difference of the paired elements
       (	| and select the first (minimum)
Giuseppe
quelle
1

JavaScript (ES6), 61 Byte

Basierend auf den Erkenntnissen von xnor .

a=>[...a].map(g=n=>g[n]=a.sort((a,b)=>a-b).indexOf(n,g[n])+1)

Probieren Sie es online!

Kommentiert

a =>                    // a[] = input array
  [...a]                // create a copy of a[] (unsorted)
  .map(g = n =>         // let g be in a object; for each value n in the copy of a[]:
    g[n] =              //   update g[n]:
      a.sort(           //     sort a[] ...
        (a, b) => a - b //       ... in ascending order
      ).indexOf(        //     and find the position
        n,              //       of n in this sorted array,
        g[n]            //       starting at g[n] (interpreted as 0 if undefined)
      ) + 1             //     add 1
  )                     // end of map()

JavaScript (ES6),  130  128 Bytes

Es  muss  definitiv einen direkteren Weg geben ...

0-indiziert.

a=>(m=g=(k,p=[])=>1/a[k]?(h=i=>i>k||g(k+1,b=[...p],b.splice(i,0,k),h(-~i)))``:p.map((v,i)=>k+=(v-=a[i])*v)|k>m||(R=p,m=k))(0)&&R

Probieren Sie es online! (mit 1-indiziertem Ausgang)

Wie?

G(0,...,n-1)nein[]

p

k=n-1+ich=0n-1(pich-einich)2
n-1G

k

Arnauld
quelle
1

Python 2 , 149 126 112 Bytes

-23 Bytes dank Mr. Xcoder

-14 Bytes dank xnor

from itertools import*
f=lambda a:min(permutations(range(len(a))),key=lambda x:sum(abs(a-b)for a,b in zip(x,a)))

Probieren Sie es online!

Verwendet Permutationen von (0 ... n-1).

Hiatsu
quelle
Sie können zu Python 2 wechseln, so dass Sie nicht functoolsmehr brauchen .
Mr. Xcoder
reduceist normalerweise übertrieben, besonders hier, wo Sie Sachen hinzufügen. Ich denke, du kannst es einfach tun sum(abs(p-q)for p,q in zip(x,a)).
14.
0

Ohne Permutationspaket

Python 3 , 238 Bytes

def p(a,r,l):
 if r==[]:l+=[a];return
 for i in range(len(r)):
  p(a+[r[i]],r[:i]+r[i+1:],l)
def m(l):
 s=(float("inf"),0);q=[];p([],list(range(len(l))),q)
 for t in q:D=sum(abs(e-f)for e,f in zip(l,t));s=(D,t)if D<s[0]else s
 return s[1]

Probieren Sie es online!

David
quelle
0

Japt -g , 12 Bytes

Êõ á ñÈíaU x

Versuch es

Ersetzen Sie bei 0-indizierten die ersten 2 Bytes durch m,, um das Array stattdessen seinen Indizes zuzuordnen.

Êõ á ñÈíaU x     :Implicit input of array U
Ê                :Length
 õ               :Range [0,Ê]
   á             :Permutations
     ñÈ          :Sort by
       í U       :  Interleave with U
        a        :  Reduce each pair by absolute difference
           x     :  Reduce resulting array by addition
                 :Implicit output of first sub-array
Zottelig
quelle