Permutendo una lista di numeri per ottenere una lista che soddisfi le condizioni date

Question

Permutendo una lista di numeri per ottenere una lista che soddisfi le condizioni date

#1 da (4 voti)

0

Ecco un problema algoritmico che sto cercando di risolvere:

Given a list [x_1,x_2,...,x_n] return a permutation of elements of the list [y_1,y_2,...,y_n] (where for each i we have y_i = x_j for only one j) which maximises the sum from k=1 to k=n-1 of |y_k-y_(k+1)|.

Quindi per semplificare - otteniamo un elenco di numeri interi e dobbiamo "mescolare" questi numeri in modo tale da ottenere un elenco in cui prendiamo la somma di tutti |y_m-y_n| tale che y_m e y_n sono uno accanto all'altro, otteniamo il numero massimo possibile di tutte le permutazioni degli elementi nell'elenco.

Penso che questo possa essere risolto in O(n*log n) , ho pensato di ordinare l'elenco e di restituire una lista in cui il primo elemento è l'elemento massimo, l'elemento successivo è minimo, il prossimo è il massimo di quelli a sinistra, ecc ... Ma questo porta verso il nulla, non posso provare che sia corretto, quindi probabilmente non lo è. Quindi, qualche consiglio su come affrontare questo problema?

algorithms

posta qiubit 13.12.2014 - 00:30

fonte

1 risposta

Leggi altre domande sui tag algorithms

Come rispettare la richiesta del codice sorgente LGPL 2.1? Decisione di progettazione del gioco di carte Java

score 4 · Accepted Answer

Che ci crediate o no, questo problema è risolvibile in tempo O(n) .

Per prima cosa, lascia che m sia la mediana dell'array. Per una coppia (x, y) vicina l'una all'altra, definisci il contributo di x da quella coppia come:

def contribution (x, y, m):
    if m < x:
        if x < y:
            return 0
        elif y < m:
            return x - m
        else:
            return x - y
    else:
        if y < x:
            return 0
        elif m < y:
            return m - x
        else:
            return y - x

Questa definizione è un po 'complessa, ma nota che contribution(x, y, m) + contribution(y, x, m) == |x - y| . E la somma che stai cercando è la somma di tutti i contributi di tutti gli elementi a entrambe le coppie.

Il modo per massimizzare il contributo di un elemento è di averlo con gli elementi sull'altro lato della mediana accanto ad esso su ciascun lato. Quali elementi non contano, solo dall'altra parte della mediana. E gli elementi sul bordo fanno solo la metà del loro contributo, quindi è chiaro che vuoi i due elementi più vicini alla mediana alle estremità. Quindi questo ci dice esattamente quale sia la permutazione che vogliamo. Vogliamo che i due elementi alle estremità siano il più vicino possibile alla mediana, mentre si alternano sopra / sotto.

Ora che lo comprendiamo, possiamo utilizzare il collegamento per trovare la mediana in O(n) di tempo. Il partizionamento dell'array e l'identificazione dei due elementi da mettere alla fine possono quindi essere eseguiti in O(n) time. E poi l'interlacciatura è anche O(n) per un algoritmo O(n) .