Rozważ permutację wartości całkowitych od 1do N. Np. Ten przykład dla N = 4:

[1, 3, 4, 2]

Będziemy rozważać tę listę być cykliczne, takie, że 1i 2są traktowane jako sąsiadujące. Jedną wielkością, którą możemy obliczyć dla takiej listy, jest całkowita kwadratowa różnica sąsiednich wartości:

(1-3)² + (3-4)² + (4-2)² + (2-1)² = 10

Twoim zadaniem jest znalezienie permutacji, która maksymalizuje tę ilość, biorąc pod uwagę dodatnią liczbę całkowitą N. W przypadku N = 4powyższego przykładu nie jest optymalny (w rzeczywistości jest minimalny). Możemy osiągnąć całkowitą kwadratową różnicę o 18następującej permutacji (jak również kilku innych):

[1, 4, 2, 3]

Twój algorytm musi działać w czasie wielomianowym (z N). W szczególności nie można po prostu obliczyć całkowitej kwadratowej różnicy wszystkich permutacji.

Możesz napisać program lub funkcję, pobierając dane wejściowe przez STDIN (lub najbliższą alternatywę), argument wiersza poleceń lub argument funkcji i wypisując wynik przez STDOUT (lub najbliższą alternatywę), wartość zwracaną funkcji lub parametr funkcji (wyjściowej).

Dane wyjściowe mogą być w dowolnym dogodnym, jednoznacznym, płaskim formacie lub w postaci łańcucha. Możesz zwrócić listę z wartościami od 0do N-1zamiast 1do N.

Obowiązują standardowe zasady gry w golfa .

Dane testowe

Istnieje ładne analityczne rozwiązanie tego problemu. Np. Wszystkie prawidłowe rozwiązania N = 10są równoważne z następującą listą (do cyklicznych przesunięć i cofnięć):

[7, 5, 6, 4, 8, 2, 10, 1, 9, 3]

Nie chcę ujawniać zbyt wiele poza tym (chociaż prawdopodobnie wystarczy, aby wymyślić wzór), więc zamiast podawać więcej przykładów, możesz sprawdzić, czy wyniki mają następujące całkowite kwadratowe różnice dla danej N:

N    Total squared difference

1                         0
2                         2
3                         6
4                        18
5                        36
6                        66
7                       106
8                       162
9                       232
10                      322
33                    11936
100                  333202
333                12308236
1000              333332002

To jest pozycja OEIS A064842 (która również zawiera odniesienie do artykułu zawierającego rozwiązanie tego wyzwania, jeśli utkniesz).

Galaretka, 24 21 15 14 10 9 bajtów

RUĖµ«/€ị"

Aby obliczyć całkowitą kwadratową różnicę, dołącz µ_ṙ1$²Sdo kodu. Wypróbuj online!

tło

Jednym ze sposobów na wygenerowanie permutacji o zmaksymalizowanej różnicy do kwadratu jest wzięcie liczb całkowitych 1 na n w porządku rosnącym i zamiana drugiego z lewej na drugi z prawej, czwarty z lewej z czwartym z prawej i tak dalej naprzód, aż spotkamy się w środku.

Na przykład dla n = 8, 9 mamy

1 2 3 4 5 6 7 8        1 2 3 4 5 6 7 8 9
  ^   ^ ^   ^            ^   ^   ^   ^

(znaki zaznaczają liczby całkowite do zamiany), co powoduje

1 7 3 5 4 6 2 8        1 8 3 6 5 4 7 2 9

po zamianie.

Jednym ze sposobów osiągnięcia tych zamian, niezależnie od parzystości n , jest:

Zacznij od wpisania liczb całkowitych w porządku rosnącym i malejącym, jeden pod drugim.

1 2 3 4 5 6 7 8        1 2 3 4 5 6 7 8 9
8 7 6 5 4 3 2 1        9 8 7 6 5 4 3 2 1

Dla każdej pary liczb całkowitych oblicz minimum pary. Daje to odległość do najbliższej krawędzi, tj. Indeks od lewej lub prawej (w zależności od tego, która wartość jest niższa).

1 2 3 4 5 6 7 8        1 2 3 4 5 6 7 8 9
8 7 6 5 4 3 2 1        9 8 7 6 5 4 3 2 1

1 2 3 4 4 3 2 1        1 2 3 4 5 4 3 2 1

Jeśli minimum jest nieparzyste, liczba całkowita powinna pozostać na swoim miejscu, więc wybieramy jedną z pierwszego rzędu; jeśli jest parzyste, liczby całkowite powinny zostać zamienione, więc wybieramy jedną z drugiego rzędu.

1   3     6   8        1   3   5   7   9
  7   5 4   2            8   6   4   2

To jest pożądany wynik.

Jak to działa

RUĖµ«/€ị"    Main link. Input: n

R            Range. Yields [1, ..., n].
 U           Upend. Yields [n, ..., 1].
  Ė          Enumerate. Yields p := [[1, n], [2, n-1], ... [n-1, 2], [n, 1]].

   µ         Begin a new, monadic chain. Argument: p
     /       Reduce...
      €        each pair of p...
    «          by minimum.
        "    For each minimum and the corresponding pair of p:
       ị       Select the element at that index.
            Indices are modular and 1-based in Jelly, so this selects the first
            element if the minimum is odd, and the second one if it is even.

JavaScript (ES6), 52 bajty

n=>[...Array(n)].map((_,i)=>(i<n/2|n%2)^i%2?i+1:n-i)

9 bajtów zapisanych dzięki @Neil!

Wyjaśnienie

To podejście określa liczbę, która powinna być w indeksie, io długości nzamiast konkatenacji wyników do tablicy. Jest to oparte na poniższej obserwacji ( n = 7na przykładzie):

• Zacznij od najniższej liczby po lewej i najwyższej po prawej: [ 1, 7 ]
• Zmień kolejność tak, aby najniższa była po prawej stronie, a najwyższa była po lewej, zwiększaj najniższą, zmniejszaj najwyższą i umieszczaj je na środku tablicy:[ 1, 6, 2, 7 ]
• Powtarzaj, aż najwyższa i najniższa zbieżność: [ 1, 6, 3, 4, 5, 2, 7 ]

Wyższe i niższe liczby można łatwo wyrazić jako n-ii i+1odpowiednio.

var solution =

n=>
  [...Array(n)] // create an array of length n
  .map((_,i)=>  // set each value of the array at index i
    (i<n/2      // if we're on the left side,
    |n%2)       // or we're on the right and n is odd, even i => lower, odd i => higher
    ^i%2?       // else even i => higher, odd i => lower
    i+1:n-i
  )

N = <input type="number" id="input" oninput="result.textContent=solution(+this.value)" />
<pre id="result"></pre>

Python2, 105 98 bajtów

7 bajtów zapisanych dzięki komentarzowi @Dennis

n=input()
r=([],[n/2+1])[n%2]
for i in range(n/2,0,-1):k=[n+1-i];r=([i]+r+k,k+r+[i])[i%2]
print r

Wersja edytowana 58 bajtów

lambda n:[(n-i-1,i)[(i+(n,1)[i<n/2])%2]for i in range(n)]

Wierzyłem już, że powinno być możliwe zrobienie tego w jednej linijce, ale logika była dla mnie zbyt złożona. Widząc odpowiedź JavaScript na @ @ user81655 i notację lambda w @Dennis Python-answer, podjąłem nową próbę.

Warunek jest równy

if i < n/2:
    i%2 != n%2
else:
    (i+1)%2

Niestety cały wysiłek związany z transformacją pozwala zaoszczędzić tylko jeden bajt w porównaniu z bezpośrednim tłumaczeniem (i<n/2or n%2)!=i%2logiki JavaScript.

Python, 51 49 bajtów

lambda n:[(i^min(i,~i%n)%-2)%n for i in range(n)]

Dzięki @xnor za grę w golfa z 2 bajtów!

Wypróbuj na Ideone .

Jak to działa

Jeśli i jest liczbą w [0, ..., n - 1] , to ~ i% n = - (i + 1)% n = - (i + 1) + n = (n - 1) - i , co oznacza, że ​​odwzorowuje 0 na n - 1 , 1 na n - 2 i, ogólnie rzecz biorąc, j- ^ty element od lewej do j- ^ty od prawej.

Jak wyjaśniono w mojej odpowiedzi na Jelly , możemy skonstruować wynik, zerkając na niższą wartość spośród i i ~ i% n , i wybierz i, jeśli jest parzyste, i ~ i% n, jeśli jest nieparzyste. Osiągamy to w następujący sposób.

• Jeśli minimalna jest równa, min(i,~i%n)%-2przyniesie 0 , więc w wyniku XORing i przyniesie I i obliczanie jej pozostałości modulo n powróci I .

• Jeśli minimum jest nieparzyste, min(i,~i%n)%-2da -1 , więc XOR wyniku za pomocą i da ~ i , więc całe wyrażenie ocenia się na ~ i% n zgodnie z potrzebą.

PHP, 77 76 51 50 49 bajtów

Wykorzystuje kodowanie ISO 8859-1.

Składanie pierwszej połowy tablicy w ten sposób:

• Liczby nieparzyste mają wartość indeksu (1, 3, 5 ..)
• Liczby parzyste mają wartość N+1-index(9, 7, 5)
• To skutkuje 1, 9, 3, 7, 5

Jeśli chodzi o drugą połowę tablicy, najbardziej zewnętrzne wartości sumują się N+1, co oznacza, że ​​można uzyskać odpowiednią prawą wartość, z N-[left value]której znana jest już lewa wartość.

for(;$k=$argv[1]-$j++;)echo" ",min($j,$k)%2?$j:$k;

Działaj w ten sposób (pokazuje to także całkowitą różnicę do kwadratu) ( -ddodano tylko dla estetyki):

php -d error_reporting=32757 -r 'for(;$k=$argv[1]-$j++;)echo~ß,$x[]=min($j,$k)%2?$j:$k;  for(;$c=$x[+$i++];)$b+=($c-($x[$i]?:$x[0]))**2;echo"\n$b\n";' 10

• Zapisano bajt, negując warunek lewy / prawy, aby można było zagnieżdżać drugą trójskładnik bez nawiasów
• Oszczędność 25 bajtów dzięki bezwstydnej implementacji algorytmu Dennisa
• Zaoszczędził bajt, pozbywając się potrzebnej przestrzeni echo
• Zapisano bajt, używając ~ßdo uzyskania spacji.

Python 2, 100

Wiem, że jest już odpowiedź na python, ale myślę, że mogłem to zrobić inaczej.

n=input();a=n%2;b=n/2;x=[b+1,b+a][a:]
for i in range(b+a-1):f=1-i%2*2;x=[x[-1]-f]+x+[x[0]+f]
print x

I jako dodatek do przetestowania całkowitego wyniku:

def t(x,n):return sum((x[i]-x[(i+1)%n])**2for i in range(n))

CJam, 17 15 14 bajtów

{,W%ee_::e<.=}

Jest to funkcja, która wyrzuca liczbę całkowitą n ze stosu i wypycha w zamian permutację [0… n-1] . Kod używa tego samego podejścia, co moja odpowiedź Jelly .

Wypróbuj online!

Jak to działa

,W%ee_::e<.=    Function body. Stack: N

,               Turn N into [0 ... N-1].
 W%             Reverse to push [N-1 ... 0].
   ee           Enumerate. This pushes [[0 N-1] [1 N-2] ... [N-2 1] [N-1 0]].
     _          Push a copy of the array of pairs.
      ::e<      Reduce each pair by minimum.
          .=    Vectorized selection.
                For the Ith minimum M, select the Mth element of the Ith pair.
                Indices are modular and 0-based in CJam, so this selects the first
                element if the minimum is even, and the second one if it is odd.

LISP, 86 bajtów

(defun g(n m)(if(= n m)(list n)(if(< m n)(cons m(reverse(cons n(g(- n 1)(+ m 1))))))))

Wejścia funkcji pozwalają wybrać wartości początkowe (m) i końcowe (n) sekwencji.

W celu przetestowania funkcji zgodnie z dostarczonymi próbkami, n jest ustalone na N, a m na 1.

Oto kod do testowania funkcji:

    (defun g(n m)(if(= n m)(list n)(if(< m n)(cons m(reverse(cons n(g(- n 1)(+ m 1))))))))

(defun sq (c)
    (apply #'+ (mapcar #'(lambda(x y) (* (- x y) (- x y))) c (append (cdr c) (list (car c))))))

(format t "N~20TSequence~50TSquared Difference~%")
(mapcar #'(lambda (x)(format t "~S~20T~S~50T~S~%" x (g x 1) (sq (g x 1)))) '(1 2 3 4 5 6 7 8 9 10 33 100 333 1000))

Wypróbuj na Ideone !

Julia, 39 bajtów

n->map(i->min(i-1,n-i)%2>0?n-~-i:i,1:n)

Wyświetla permutację 1: n . Permutacja 0: n-1 nie kosztuje ani nie oszczędza bajtów:

n->map(i->min(i,n+~i)%2>0?i:n+~i,0:n-1)

Ta ostatnia wersja jest bezpośrednim portem mojej odpowiedzi w języku Python .

ES6, 77 bajtów

n=>[...Array(n)].map(_=>r[++i&2?"push":"unshift"](i&1?n--:++j),i=j=0,r=[])&&r

Te i&1próbki cyfry od skrajności do środka. i&2Dodaje je do początku lub końca wynik w parach.

R, 117 86 bajtów

z=1:(n<-scan());a=pmin(z,n:1);for(i in seq(2,,2,n%/%2))z[b]=z[rev(b<-which(a==i,T))];z

edytuj zastąpioną długą wersję buggy z implementacją algorytmu Jelly @Dennis