Considérons une permutation des valeurs entières de 1à N. Par exemple, cet exemple pour N = 4:

[1, 3, 4, 2]

Nous considérerons cette liste comme cyclique, de sorte que 1et 2seront traités comme adjacents. Une quantité que nous pouvons calculer pour une telle liste est la différence quadratique totale des valeurs adjacentes:

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

Votre tâche consiste à trouver une permutation qui maximise cette quantité, étant donné un entier positif N. Dans le cas de N = 4l'exemple ci-dessus, ce n'est pas optimal (en fait, c'est minime). Nous pouvons obtenir une différence quadratique totale de 18avec la permutation suivante (ainsi que plusieurs autres):

[1, 4, 2, 3]

Votre algorithme doit s'exécuter en temps polynomial (of N). En particulier, vous ne pouvez pas simplement calculer la différence quadratique totale de toutes les permutations.

Vous pouvez écrire un programme ou une fonction, en prenant une entrée via STDIN (ou l'alternative la plus proche), un argument de ligne de commande ou un argument de fonction et en sortant le résultat via STDOUT (ou l'alternative la plus proche), la valeur de retour de la fonction ou le paramètre de la fonction (out).

La sortie peut être dans n'importe quel format de liste plate ou de chaîne pratique et sans ambiguïté. Vous pouvez choisir de renvoyer une liste avec des valeurs de 0à N-1au lieu de 1à N.

Les règles de code-golf standard s'appliquent.

Données de test

Il existe une bonne solution analytique pour ce problème. Par exemple, toutes les solutions valides pour N = 10sont équivalentes à la liste suivante (jusqu'aux décalages cycliques et inversions):

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

Je ne veux pas en révéler trop au-delà (bien que cela soit probablement suffisant pour comprendre le modèle), donc au lieu de donner plus d'exemples, vous pouvez vérifier que vos résultats ont les différences quadratiques totales suivantes pour une donnée 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

Il s'agit de l'entrée OEIS A064842 (qui contient également une référence à un document avec une solution à ce défi si vous êtes bloqué).

Gelée, 24 21 15 14 10 9 octets

RUĖµ«/€ị"

Pour calculer la différence quadratique totale, ajoutez µ_ṙ1$²Sau code. Essayez-le en ligne!

Contexte

Une façon de générer une permutation avec une différence quadratique maximisée consiste à prendre les entiers 1 à n dans l'ordre croissant, et à échanger le deuxième de gauche avec le second de droite, le quatrième de gauche avec le quatrième de droite, etc. jusqu'à ce que nous nous rencontrions au milieu.

Par exemple, pour n = 8, 9, nous avons

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

(les carets marquent les entiers à échanger), ce qui entraîne

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

après l'échange.

Une façon de réaliser ces swaps, indépendamment de la parité de n , est la suivante.

Commencez par écrire les nombres entiers dans l'ordre croissant et décroissant, l'un en dessous de l'autre.

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

Pour chaque paire d'entiers, calculez le minimum de la paire. Cela donne la distance au bord le plus proche, c'est-à-dire l'indice à partir de la gauche ou de la droite (le plus bas des deux).

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

Si le minimum est impair, l'entier doit rester à sa place, nous sélectionnons donc celui de la première ligne; s'il est pair, les entiers doivent être échangés, nous sélectionnons donc celui de la deuxième ligne.

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

Il s'agit de la sortie souhaitée.

Comment ça fonctionne

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 octets

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

9 octets économisés grâce à @Neil!

Explication

Cette approche détermine le nombre qui doit être à l'index iavec une longueur nplutôt que de concaténer les résultats dans un tableau. Ceci est basé sur l'observation suivante (en utilisant n = 7comme exemple):

• Commencez par le nombre le plus bas à gauche et le plus élevé à droite: [ 1, 7 ]
• Changez l'ordre pour que le plus bas soit à droite et le plus haut à gauche, incrémentez le plus bas, décrémentez le plus haut et placez-les au milieu du tableau:[ 1, 6, 2, 7 ]
• Répétez jusqu'à ce que le plus haut et le plus bas convergent: [ 1, 6, 3, 4, 5, 2, 7 ]

Les nombres supérieurs et inférieurs peuvent facilement être exprimés comme n-iet i+1respectivement.

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 octets

7 octets économisés grâce au commentaire de @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

Version modifiée 58 octets

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

Je pensais déjà qu'il devrait être possible de le faire en monoplace, mais la logique était trop complexe pour moi. En voyant la réponse JavaScript de @ user81655 et la notation lambda dans @Dennis Python-answer, j'ai fait un nouvel essai.

La condition est égale à

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

Malheureusement, tous les efforts de transformation ne permettent d'économiser qu'un seul octet par rapport à la traduction directe (i<n/2or n%2)!=i%2de la logique JavaScript.

Python, 51 49 octets

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

Merci à @xnor d'avoir joué au golf sur 2 octets!

Essayez-le sur Ideone .

Comment ça fonctionne

Si i est un nombre dans [0, ..., n - 1] , alors ~ i% n = - (i + 1)% n = - (i + 1) + n = (n - 1) - i , ce qui signifie qu'il mappe 0 à n - 1 , 1 à n - 2 et, en général, le j ^ème élément de gauche à j ^ème de droite.

Comme expliqué dans ma réponse Jelly , nous pouvons construire la sortie en jetant un coup d'œil à la valeur inférieure parmi i et ~ i% n , et choisir i s'il est pair et ~ i% n s'il est impair. Nous y parvenons comme suit.

• Si le minimum est pair, min(i,~i%n)%-2donnera 0 , donc XOR le résultat avec i donnera i , et le calcul de son résidu modulo n retournera i .

• Si le minimum est impair, min(i,~i%n)%-2donnera -1 , donc XOR le résultat avec i donnera ~ i , donc l'expression entière sera évaluée à ~ i% n comme souhaité.

PHP, 77 76 51 50 49 octets

Utilise le codage ISO 8859-1.

Assemblage de la première moitié du tableau comme ceci:

• Les nombres impairs ont leur valeur d'index (1, 3, 5 ..)
• Les nombres pairs ont la valeur N+1-index(9, 7, 5)
• Il en résulte 1, 9, 3, 7, 5

En ce qui concerne la seconde moitié du tableau, les valeurs les plus externes s'additionnent N+1, ce qui signifie que vous pouvez obtenir la valeur droite correspondante d' N-[left value]où la valeur gauche est déjà connue.

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

Exécutez comme ceci (cela montre également la différence totale au carré) ( -dajouté pour l'esthétique uniquement):

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

• Enregistrement d'un octet en annulant la condition gauche / droite afin que le deuxième ternaire puisse être imbriqué sans parenthèses
• 25 octets enregistrés en implémentant sans vergogne l'algorithme de Dennis
• Sauvegardé un octet en se débarrassant de l'espace nécessaire après echo
• Enregistré un octet en utilisant ~ßpour générer un espace.

Python 2, 100

Je sais qu'il y a déjà une réponse en python, mais je pense que je l'ai peut-être fait différemment.

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

Et en plus pour tester le score total:

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

CJam, 17 15 14 octets

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

Il s'agit d'une fonction qui extrait un entier n de la pile et envoie en retour une permutation de [0… n-1] . Le code utilise la même approche que ma réponse Jelly .

Essayez-le en ligne!

Comment ça fonctionne

,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 octets

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

Les entrées de la fonction permettent de choisir les valeurs de début (m) et de fin (n) de la séquence.

Pour tester la fonction selon les échantillons fournis, n est fixé à N et m à 1.

Voici le code pour tester la fonction:

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

Essayez-le sur Ideone !

Julia, 39 octets

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

Cela imprime une permutation de 1: n . Une permutation de 0: n-1 ne coûte ni ne sauvegarde les octets:

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

Cette dernière version est un port direct de ma réponse Python .

ES6, 77 octets

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

Les i&1échantillons les chiffres des extrêmes au milieu. Le les i&2ajoute au début ou à la fin du résultat par paires.

R, 117 86 octets

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

modifier la version longue du buggy remplacé avec une implémentation de l'algorithme Jelly de @Dennis