Riordino di una lista per massimizzare la differenza di elementi adiacenti

Question

Sono interessato a riordinare una lista in modo tale da massimizzare la somma dei quadrati delle differenze tra elementi adiacenti (ciclici). Ecco un pezzo di codice Python che bruta forze la soluzione in tempo fattoriale, in modo da poter capire cosa intendo:

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 

Questo produce i seguenti risultati per maximal_difference_reorder(range(4)):

[(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)] 

come si può vedi, tutti i risultati sono rotazioni cicliche e riflessioni l'una dell'altra. Se il punteggio è stato determinato con la somma delle differenze, non al quadrato, credo che tutte le permutazioni sarebbero equamente valutate, dato un input uniformemente distanziato.

La forzatura bruta funziona bene, ma O (n!) È terribile, quindi è possibile farlo in un tempo di calcolo asintotico più piccolo? Punti bonus se funziona per una mesh di input non uniforme o per altre funzioni di punteggio.

Per inciso, questo non è compito o una domanda di intervista, anche se forse sarebbe una buona soluzione. Piuttosto, sto provando a generare uno spettro di colori per una serie di dati parametrizzati, e sto cercando di evitare di avere colori simili l'uno accanto all'altro.

Answer 1

Il problema è un'istanza leggermente mascherata di Traveling Salesman Problem.

Chiamare l'elenco di input c (per "città"). Scegli uno M che è un limite superiore su (c[i]-c[j])**2 Questo è facilmente eseguibile in tempo lineare poiché il minimo e il massimo dell'elenco possono essere calcolati in un'unica passata, nel qual caso funziona M = (max - min)**2. Definire la distanza, d[i,j] da c[i] a c[j] da:

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

È facile vedere che per ogni permutazione ciclica il costo di tale permutazione (calcolato secondo d) è n*M - sum of squares of differences quindi è minimizzato se e solo la somma dei quadrati delle differenze è massimizzato.

Ci sono molti approcci per risolvere un TSP. Anche se è NP-duro, in pratica i metodi all'avanguardia sono fenomenalmente buoni nel risolvere i problemi che sorgono nella pratica. Inoltre, i buoni metodi euristici possono tipicamente arrivare a una frazione del percento ottimale.

Il tuo problema particolare è un caso speciale di un TSP. Come tale, è possibile che questo caso speciale sia più semplice e di fatto abbia una soluzione temporale polinomiale, ma ne dubito. Suppongo che sia anche NP-hard ma non ho una prova. Inoltre, anche se è NP-hard, potrebbe essere che ci sia una soluzione (forse una formulazione Integer Programming) che è più efficiente della riduzione a TSP come sopra.

On Edit: basato sui commenti di Dave Gavin e la risposta di @SergeBallesta Ora penso che sia possibile un algoritmo del tempo polinomiale. Lascerò questa risposta, se per nessun altro motivo se funziona un algoritmo del tempo polinomiale, questo problema sarebbe un buon esempio per mostrare che alcune sottoclassi del TSP hanno soluzioni più semplici.

Answer 2

Se stai cercando di massimizzare i quadrati delle differenze tra elementi consecutivi in ​​modo ciclico, direi che dovresti provare ad avere l'elemento più grande vicino al più piccolo perché concettualmente a²+b²>=2*((a+b)/2)². Questo è quello che hai trovato dalla forza bruta con range(4).

penso che si potesse dimostrare per induzione, ma che una parte dovrebbe essere migliore chiesto su Mathematics ma ci avrei scommesso una moneta che la soluzione è semplicemente quello di:

• sorta lista
• prendere più grande elemento messo nell'indice 0 della lista risultato
• prendere più piccolo e metterlo sull'indice 1
• prendere più piccolo di rimanere posero sul index -1
• prendere più di un residuo ND metterlo su indice 2

e iterare una volta a destra e una a sinistra alternando più grande e più piccolo dei rimanenti elementi

Si finisce in:

• O (n * log (n)) statistica per l'ordinamento Quicksort o unire-ordinamento, o o (n²/2) con un semplice bubblesort
• lineare per costruire la matrice risultato

Answer 3

Penso che possiamo avere una soluzione O (n)

La chiave per risolvere questo problema è generare il primo seme per il gruppo ciclico. Considerando che dovremmo associare gli elementi in cui la somma della differenza quadratica a coppie è massima che è possibile se accoppiamo un elemento con il suo vicino più lontano.

Il che significa che se h _i è l'i esimo numero più alto, poi i vicini di h _i sono (h _n-i-1, h _{n-i + 1}). Come la sequenza ciclica è così i numeri sarebbe avvolgono per indice negativo cioè h -1 = h Questo genererà il primo elenco seme come [0, 6, 2, 4, 3, 5, 1, 7]

Questa sequenza può essere facilmente generando scambiando ogni indice dispari pair ie [(a , un _n-1), (a , un _n-3), ...]

La sequenza successiva può essere generato generando un singolare sequenziale rotazione e il n riflettendo la sequenza ruotata

Ecco un esempio di implementazione

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) 

Esempio 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), 
    ] 

Nota Si presume che i dati sono ordinati.In caso contrario, è banale per risolvere la cosa in cui la complessità soluzione sarebbe O (n nlog)

Answer 4

Ecco l'algoritmo greedy ho suggerito nei commenti:

Come circa l'algoritmo greedy? Ad ogni passo, anteporre o aggiungere il numero per aumentare il punteggio più (questo farà un'onda a zigzag di ampiezza crescente e decrescente). Prova che a partire sia con il numero più basso o più alto numero

Sarebbe interessante studiare esempio in cui algoritmo greedy non è ottimale

# 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