Neuordnen einer Liste zum Maximieren der Differenz benachbarter Elemente

Question

Ich möchte eine Liste so neu anordnen, dass die Summe der Quadrate der Differenzen zwischen benachbarten Elementen (zyklisch) maximiert wird. Hier ist ein Stück Python-Code, dass Brute-Kräfte der Lösung in faktorielles Zeit, so können Sie sehen, was ich meine:

def maximal_difference_reorder(input): 

    from itertools import permutations 

    best_sum = 0 
    best_orderings = [] 

    for x in permutations(input): 
     d = np.sum(np.diff(x)**2) + (x[0] - x[-1])**2 
     if d > best_sum: 
      best_orderings = [x] 
      best_sum = d 
     elif d == best_sum: 
      best_orderings.append(x) 

    return best_orderings 

Die folgenden Ergebnisse für maximal_difference_reorder(range(4)) ergibt:

[(0, 2, 1, 3), 
(0, 3, 1, 2), 
(1, 2, 0, 3), 
(1, 3, 0, 2), 
(2, 0, 3, 1), 
(2, 1, 3, 0), 
(3, 0, 2, 1), 
(3, 1, 2, 0)] 

Wie können Sie sehen Sie, alle Ergebnisse sind zyklische Rotationen und Reflexionen von einander. Wenn die Punktzahl mit der Summe der nicht quadrierten Differenzen bestimmt wurde, glaube ich, dass alle Permutationen bei einer gleichmäßig verteilten Eingabe gleichmäßig bewertet würden.

Brute Forcing funktioniert gut, aber O (n!) Ist schrecklich, also ist es möglich, dies in einer kleineren asymptotischen Rechenzeit zu tun? Bonuspunkte, wenn es für ein ungleichmäßiges Eingabegitter oder für andere Bewertungsfunktionen verwendet wird.

Übrigens ist das keine Hausaufgabe oder eine Interviewfrage, obwohl es vielleicht ein guter wäre. Ich versuche vielmehr, ein Farbspektrum für eine Reihe von parametrisierten Daten zu erzeugen, und versuche, ähnliche Farben nebeneinander zu vermeiden.

Answer 1

Ihr Problem ist eine leicht getarnte Instanz der Traveling Salesman Problem.

Rufen Sie die Eingabeliste c (für "Städte") auf. Wählen Sie eine beliebige M, die eine obere Grenze auf (c[i]-c[j])**2 ist Dies ist leicht in linearer Zeit getan, da die min und der max der Liste in einem einzigen Durchgang berechnet werden kann, in diesem Fall funktioniert M = (max - min)**2. Definieren den Abstand, d[i,j] von c[i] zu c[j] von:

d(i,j) = 0 if i == j else M - (c[i]-c[j])**2 

Es ist einfach, die Kosten dieser Permutation, daß für jede zyklische Vertauschung zu sehen (berechnet nach d) wird n*M - sum of squares of differences daher wird minimiert, wenn und nur die Summe der Quadrate der Unterschiede ist maximiert.

Es gibt eine Fülle von Ansätzen zur Lösung eines TSP. Obwohl es NP-schwer ist, sind die Methoden des Stands der Technik in der Praxis phänomenal gut darin, Probleme zu lösen, die in der Praxis auftreten. Außerdem können gute heuristische Methoden typischerweise einen Bruchteil eines Prozents des Optimalen erreichen.

Ihr spezielles Problem ist ein Spezialfall eines TSP. So ist es möglich, dass dieser spezielle Fall einfacher ist und tatsächlich eine polynomielle Zeitlösung hat, aber ich bezweifle es. Ich vermute, dass es auch NP-schwer ist, aber keinen Beweis hat. Auch - auch wenn es NP-schwer ist, könnte es sein, dass es eine Lösung gibt (vielleicht eine Integer Programming-Formulierung), die effizienter ist, als sie auf TSP wie oben zu reduzieren.

On Bearbeiten: basierend auf Kommentaren von Dave Gavin und die Antwort von @SergeBallesta Ich denke jetzt, dass ein Polynomialzeit-Algorithmus möglich ist. Ich lasse diese Antwort, wenn aus einem anderen Grund, als wenn ein Polynomialzeit-Algorithmus funktioniert, dann wäre dieses Problem ein schönes Beispiel dafür, zu zeigen, dass bestimmte Unterklassen des TSP einfachere Lösungen haben.

Answer 2

Wenn Sie versuchen, die Quadrate der Unterschiede zwischen aufeinanderfolgenden Elementen auf eine zyklische Weise zu maximieren, würde ich sagen, dass Sie versuchen sollten, das größte Element in der Nähe des kleinsten zu haben, weil konzeptionell a²+b²>=2*((a+b)/2)². Das haben Sie mit Brute Force mit range(4) gefunden.

Ich denke, dass es durch Induktion gezeigt werden kann, aber das Teil besser gebeten Mathematics werden soll, aber ich würde eine Münze wettet, dass die Lösung ist einfach:

• sortiert die Liste
• nehmen größte Element steckte es in Index 0 Ergebnisliste
• nehmen kleinste und legt sie auf Index 1
• nehmen kleinsten Rest und legt sie auf Index -1
• nehmen größte eine verbleibender nd legte sie auf Index 2

und iterieren einmal nach rechts und einmal nach links abwechselnd größten und kleinsten verbleibenden Elemente

Sie enden in:

• O (n * log (n)) statistik für die Sortierung mit quicksort oder merge-Sortieren, oder O (n²/2) mit einer bloßen Blasensortierung
• linear für den Aufbau der Ergebnismatrix

Answer 3

Ich denke, wir können eine O (n) -Lösung haben

Der Schlüssel zur Lösung dieses Problems ist, den ersten Keim für die zyklische Gruppe zu generieren. In Anbetracht dessen sollten wir die Elemente paaren, bei denen die paarweise quadratische Differenzsumme maximal ist, was möglich ist, wenn wir ein Element mit seinem entferntesten Nachbarn paaren.

die, wenn h i die i-te ist höchste Zahl, dann die Nachbarn von h i sind (h _n-i-1, _{h n-i + 1}). Wie die Sequenz zyklisch ist, so würden wickeln die Zahlen für negativen index dh h rund _-1 = h 0 Dies wird die erste Seed-Liste als [0, 6, 2, 4, 3, 5, 1, 7]

erzeugen kann Diese Sequenz leicht durch Vertauschen jeden ungeraden Index seines Erzeugungs Paar dh [(a 1, a n-1 ), (a 3 ein _n-3), ...]

Die nachfolgende Sequenz kann durch Erzeugung eines singulären sequenziellen erzeugt werden Rotation und die n Reflektieren der gedrehten Sequenz

Hier ist eine Beispielimplementierung

def maximal_difference_reorder1(x): 
    def maximal_difference_seeder(x): 
     for i in range(1, len(x)/2): 
      x[i:len(x) - i] = x[i:len(x) - i][::-1] 
     return x 
    def rotate_left(x): 
     start = x 
     while True: 
      x = x[1:] + x[0:1] 
      if x == start: break 
      yield x 

    x = maximal_difference_seeder(x) 
    rotated = [x] + (list(rotate_left(x)) if len(x) > 1 else []) 
    reflected = [e[::-1] for e in rotated] if len(x) > 2 else [] 
    return map(tuple, rotated + reflected) 

Beispiel Run

def display(lst, width = 80): 
    it_lst = iter(lst) 
    try: 
     print '[', 
     while True: 
      for _ in range(80/(len(lst[0])*3 + 2)): 
       print "{},".format(next(it_lst)), 
      print '\n ', 
    except StopIteration: 
     print ']' 

display(maximal_difference_reorder1(range(10))) 

[ (0, 8, 2, 6, 4, 5, 3, 7, 1, 9), (8, 2, 6, 4, 5, 3, 7, 1, 9, 0), 
    (2, 6, 4, 5, 3, 7, 1, 9, 0, 8), (6, 4, 5, 3, 7, 1, 9, 0, 8, 2), 
    (4, 5, 3, 7, 1, 9, 0, 8, 2, 6), (5, 3, 7, 1, 9, 0, 8, 2, 6, 4), 
    (3, 7, 1, 9, 0, 8, 2, 6, 4, 5), (7, 1, 9, 0, 8, 2, 6, 4, 5, 3), 
    (1, 9, 0, 8, 2, 6, 4, 5, 3, 7), (9, 0, 8, 2, 6, 4, 5, 3, 7, 1), 
    (9, 1, 7, 3, 5, 4, 6, 2, 8, 0), (0, 9, 1, 7, 3, 5, 4, 6, 2, 8), 
    (8, 0, 9, 1, 7, 3, 5, 4, 6, 2), (2, 8, 0, 9, 1, 7, 3, 5, 4, 6), 
    (6, 2, 8, 0, 9, 1, 7, 3, 5, 4), (4, 6, 2, 8, 0, 9, 1, 7, 3, 5), 
    (5, 4, 6, 2, 8, 0, 9, 1, 7, 3), (3, 5, 4, 6, 2, 8, 0, 9, 1, 7), 
    (7, 3, 5, 4, 6, 2, 8, 0, 9, 1), (1, 7, 3, 5, 4, 6, 2, 8, 0, 9), 
    ] 

Hinweis angenommen wird, dass die Daten sortiert ist.Wenn nicht, ist es trivial zu sortieren, wobei die Lösung der Komplexität O sein würde (n log n)

Answer 4

Hier ist der Greedy-Algorithmus ich in den Kommentaren vorgeschlagen:

Wie über den Greedy-Algorithmus? Bei jedem Schritt wird die Zahl vorangestellt oder angefügt, um die Punktzahl am stärksten zu erhöhen (dies wird eine Zickzackwelle mit zunehmender und dann abnehmender Amplitude erzeugen). Versuchen Sie das mal mit Start entweder der kleinsten Zahl oder größter Zahl

Es wäre interessant Beispiel zu studieren, wo Greedy-Algorithmus nicht optimal ist

# https://stackoverflow.com/questions/34154324/reordering-a-list-to-maximize-difference-of-adjacent-elements?s=2|0.0000 
import itertools 

def score(x): 
    return sum((a-b)**2 for a,b in zip(x, x[1:])) 

assert score([0, 2, 5]) == 4 + 9 

def maximise(x): 
    x = sorted(x) 
    candidates = [greedy(x[:1], x[1:]), greedy(x[-1:], x[:-1])] 
    return max(candidates, key=score) 

def greedy(current, remaining): 
    while remaining: 
     i, j = max(itertools.product((0, -1), repeat=2), key=lambda pair: score((current[pair[0]], remaining[pair[1]]))) 
     current.insert(i, remaining.pop(j)) 

    return current 

def cyclic_score(x): 
    return sum((a-b)**2 for a,b in zip(x, x[1:] + x[:1])) 

assert cyclic_score([0, 2, 5]) == 4 + 9 + 25