[Algorytmy] Permutacja dająca największą sumę

[matinf]

Witam,
Mamy listę \(\displaystyle{ [a_1, a_2, a_3, a_4, ...., a_n]}\)
Naszym zadaniem jest teraz znaleźć taką permutację tej listy, aby suma:
\(\displaystyle{ \sum_{i=1}^{n-1} | x_{p_{i+1}} - x_p_i |}\) była możliwie największa.

[Afish]

Sortujesz liczby a następnie sprawdzasz dwa ustawienia:

Kod: Zaznacz cały

największa ; najmniejsza ; druga największa ; druga najmniejsza ...

oraz:

Kod: Zaznacz cały

najmniejsza ; największa ; druga najmniejsza ; druga największa ...

Powinno zadziałać, aczkolwiek nie dowodziłem tego.

[Zordon]

Nie działa: \(\displaystyle{ [1,1,1,1,1000000]}\)

[matinf]

Tak, to oczywiście nie działa.
Jakiś inny pomysł ?

[Afish]

Nie działa: \(\displaystyle{ [1,1,1,1,1000000]}\)

A jaka odpowiedź jest tutaj poprawna?

[matinf]

Generalnie to w sumie bym nie odrzucał tak szybko tego Twojego pomysłu jednak, biorąc pod uwagę, że obydwa przypadki rozważasz.
Faktycznie miałem taki pomysł, ale rozważałem jeden przypadek i pochopnie napisałem, że to nie zadziała.
Należy spróbować zastanowić się nad uzasadnieniem tego.

[Zordon]

Przepraszam, faktycznie podałem zły przykład...
Poprawka: \(\displaystyle{ [0,1,1,1,1,1,1,2]}\)

[matinf]

Czy uważasz, że ten przykład uwala algorytm ?
Pokaże te dwa przypadki:
\(\displaystyle{ [0;1;1;2;1;1;1;1]
[2;0;1;1;1;1;1;1]}\)

Jak moglibyśmy niby lepiej uzyskać ?

[Zordon]

Algorytm zwróci inny wynik niż pokazujesz. Tak czy inaczej, żadne z Twoich ustawień nie jest optymalne. Jest takim zaś \(\displaystyle{ [1,2,1,1,1,1,0,1]}\).


edit: tutaj jest opisane zachłanne podejście, które działa ... 37&t=14074 ale niekoniecznie łatwo jest to udowodnić

[Afish]

Okej, dla tego kontrprzykładu wystarczy budować tablice od środka, czyli:

Kod: Zaznacz cały

największy
najmniejszy ; największy ; drugi najmniejszy
drugi największy ; najmniejszy ; największy ; drugi najmniejszy ; trzeci największy

Aczkolwiek to wydaje mi się grubymi nićmi szyte Trzeba na spokojnie usiąść i pokminić teoretycznie.

[Zordon]

Budowanie od środka działa, ale ciężko to udowodnić

[Afish]

Budowanie od środka działa

Tak obstawiasz, czy masz jakieś mocniejsze przesłanki (na przykład przeszło na jakimś konkursie)?

[Zordon]

Tak, to jest klasyczne zadanie Nawet chyba gdzieś widziałem dowód. Przy odrobinie zawziętości można to samemu wymyślić, ale zapewne nie jest to przyjemne.

[norwimaj]

Kod: Zaznacz cały

najmniejszy ; największy ; drugi najmniejszy

Albo

Kod: Zaznacz cały

drugi największy; najmniejszy ; największy 

Dla \(\displaystyle{ n}\) nieparzystego są dwa przypadki, w zależności od tego, która ze środkowych różnic jest większa. Dla ciągu \(\displaystyle{ 1,3,4}\) będzie inaczej niż dla \(\displaystyle{ 1,2,4}\). Dla \(\displaystyle{ n}\) parzystego jest tylko jedna możliwość.

Dowód nie wydaje się trudny. Jeśli \(\displaystyle{ x_1\le x_2\le\ldots\le x_{2n}}\), to tą metodą uzyskamy wynik

\(\displaystyle{ 2(x_2-x_1)+4(x_3-x_2)+6(x_4-x_3)+\ldots+2(n-1)(x_n-x_{n-1}) +\\
+ (2n-1)(x_{n+1}-x_n) +\\
+2(n-1)(x_{n+2}-x_{n+1})+\ldots+2(x_{2n}-x_{2n-1}).}\)

Większego wyniku uzyskać nie możemy. Dla \(\displaystyle{ k<n}\) składnik \(\displaystyle{ x_{k+1}-x_k}\) może być policzony co najwyżej z krotnością \(\displaystyle{ 2k}\), bo skoro każdy z wierzchołków \(\displaystyle{ x_1,\ldots,x_k}\) odwiedzamy tylko raz, to wychodzi z nich co najwyżej \(\displaystyle{ 2k}\) krawędzi, zatem jest co najwyżej \(\displaystyle{ 2k}\) krawędzi z tych wierzchołków do wierzchołków \(\displaystyle{ x_{k+1},\ldots,x_{2n}}\). Tak samo dla składników z trzeciej linijki. Składnik środkowy może być z krotnością co najwyżej \(\displaystyle{ 2n-1}\), bo tyle jest wszystkich krawędzi.

Dla nieparzystej liczby wyrazów jest trochę trudniej, ale też da się udowodnić.