En tant qu'informaticiens, vous connaissez probablement tous les opérations de liste de base de pop and push . Ce sont des opérations simples qui modifient une liste d'éléments. Cependant, avez-vous déjà entendu parler de l'opération flop ? (comme dans bistable flop , )? C'est assez simple. Étant donné un nombre n , inversez les n premiers éléments de la liste. Voici un exemple:

>>> a = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
>>> a.flop(4)
[4, 3, 2, 1, 5, 6, 7, 8, 9, 10]

La chose intéressante à propos de l'opération de flop, c'est que vous pouvez l'utiliser pour faire des choses intéressantes sur une liste, comme le trier . Nous allons faire quelque chose de similaire avec les flops:

Étant donné une liste d'entiers, "Neighbour it". En d'autres termes, triez-le de sorte que chaque élément en double apparaisse consécutivement.

Cela peut être fait avec des flops! Par exemple, prenez la liste suivante:

>>> a = [3, 2, 1, 4, 3, 3, 2]
>>> a.flop(4)
[4, 1, 2, 3, 3, 3, 2]
>>> a.flop(3)
[2, 1, 4, 3, 3, 3, 2]
>>> a.flop(6)
[3, 3, 3, 4, 1, 2, 2]

Cela nous amène à la définition du défi d'aujourd'hui:

Étant donné une liste d'entiers, affichez tout ensemble de flops qui entraînera le voisinage de la liste.

En utilisant la dernière liste comme exemple, vous devez sortir:

4
3
6

car flasher la liste par 4, puis par 3, puis par 6 se traduira par une liste voisine. Gardez à l'esprit que vous n'avez pas besoin d'imprimer la liste de flops la plus courte possible qui voisine une liste. Si vous aviez imprimé:

4
4
4
3
1
1
6
2
2

au lieu de cela, ce serait toujours une sortie valide. Cependant, vous ne pouvez jamais afficher un nombre supérieur à la longueur de la liste. En effet, pour une liste a = [1, 2, 3], appeler a.flop(4)n'a pas de sens.

Voici quelques exemples:

#Input:
[2, 6, 0, 3, 1, 5, 5, 0, 5, 1]

#Output
[3, 7, 8, 6, 9]


#Input
[1, 2]

#Output
<any list of integers under 3, including an empty list>


#Input
[2, 6, 0, 2, 1, 4, 5, 1, 3, 2, 1, 5, 6, 4, 4, 1, 4, 6, 6, 0]

#Output
[3, 19, 17, 7, 2, 4, 11, 15, 2, 7, 13, 4, 14, 2]


#Input
[1, 1, 1, 1, 2, 2, 2, -1, 4]

#Output
[]


#Input
[4, 4, 8, 8, 15, 16, 16, 23, 23, 42, 42, 15]

#Output
[12, 7]

Gardez à l'esprit que dans chacun de ces exemples, la sortie donnée n'est qu'une sortie potentiellement valide. Comme je l'ai déjà dit, tout ensemble de flops qui voisine la liste donnée est une sortie valide . Vous pouvez utiliser ce script python pour vérifier si une liste donnée de flops voisine correctement une liste.

Vous pouvez prendre des entrées et des sorties dans n'importe quel format raisonnable. Par exemple, les arguments de fonction / valeur de retour, STDIN / STDOUT, la lecture / écriture d'un fichier, etc. sont tous valides. Comme d'habitude, c'est du golf de code , alors faites le programme le plus court possible et amusez-vous! :)

Haskell , 98 71 octets

h.r
h(x:s)|(a,b)<-span(/=x)s=l b:l s:h(b++r a)
h e=e
r=reverse
l=length

Essayez-le en ligne!

Explication

Pour une liste de longueur, ncette méthode produit des 2*nflops. Il fonctionne en regardant le dernier élément de la liste, en recherchant le même élément dans la liste avant et en le retournant de l'avant-dernière position. Ensuite, la liste avec le dernier élément supprimé est récursivement "voisine".

Pour la liste, [1,2,3,1,2]l'algorithme fonctionne comme ceci:

[1,2,3,1,2]  flip longest prefix that ends in 2: flop 2
[2,1,3,1,2]  bring first element to second to last position: flop n-1 = flop 4
[1,3,1,2,2]  recursively work on n-1 list
[1,3,1,2]    there is no other 2: flop 0
[1,3,1,2]    flop n-1 = flop 3
[1,3,1,2]    recurse
[1,3,1]      flop 1
[1,3,1]      flop 2
[3,1,1]      recurse
[3,1]        flop 0
[3,1]        flop 1
 ...

Tous ensemble, cela donne les flops [2,4,0,3,1,2,0,1,0,0]et la liste des voisins [3,1,1,2,2].

Wolfram Language (Mathematica) , 71 octets

If[(n=Tr[1^#])<1,{},{i=Last@Ordering@#,n,n-1,i-1}~Join~#0[#~Drop~{i}]]&

Essayez-le en ligne!

Comment ça marche

Étant donné un tableau de longueur n, génère une séquence de 4nflops qui trient le tableau dans un ordre croissant: en particulier, en plaçant les éléments en double les uns à côté des autres.

L'idée est que pour trier un tableau, nous déplaçons son plus grand élément à la fin, puis trions les premiers n-1éléments du tableau. Pour éviter de mettre en œuvre l'opération de flop, nous déplaçons le plus gros élément à la fin d'une manière qui ne perturbe pas les autres éléments:

{3, 2, 1, 5, 3, 3, 2}    starting array, with largest element in position 4
{5, 1, 2, 3, 3, 3, 2}    flop 4 to put the largest element at the beginning
{2, 3, 3, 3, 2, 1, 5}    flop 7 to put the largest element at the end
{1, 2, 3, 3, 3, 2, 5}    flop 6 (7-1) to reverse the effect of flop 7 on other elements
{3, 2, 1, 3, 3, 2, 5}    flop 3 (4-1) to reverse the effect of flop 4 on other elements

En général, si le plus grand élément est en position i, la séquence de flops qui le déplace jusqu'à la fin l'est i, n, n-1, i-1.

Python 2 , 69 octets

l=input()
while l:k=l.index(max(l));print-~k,len(l),;l=l[:k:-1]+l[:k]

Essayez-le en ligne!

Gelée , 19 17 octets

ỤỤạ‘Ḣ
ỤÇÐƤĖµUż’ṚF

Trie la liste.

Essayez-le en ligne!

Nettoyer , 88 octets

Je pense qu'il y en a peut-être un plus court avec des gardes, mais je ne l'ai pas encore trouvé.

import StdEnv
$[h:t]#(a,b)=span((<>)h)t
=map length[b,t]++ $(b++r a)
$e=e
r=reverse

$o r

Essayez-le en ligne!

En tant que fonction littérale. Fonctionne de la même manière que la réponse Haskell de Laikoni , mais a joué un peu différemment, et bien sûr aussi dans une langue différente.

JavaScript, 150 octets

(a,f=n=>(a=[...a.slice(0, n).reverse(),...a.slice(n)],n),l=a.length,i=0)=>a.reduce(c=>[...c,f(a.indexOf(Math.max(...a.slice(0, l-i)))+1),f(l-i++)],[])

Essayez-le en ligne!

JavaScript, 151 octets

a=>{f=n=>(a=[...a.slice(0,n).reverse(),...a.slice(n)],n),r=[];for(i=a.length+1;--i>0;)r.push(f(a.indexOf(Math.max(...a.slice(0, i)))+1),f(i));return r}

Essayez-le en ligne!

Les deux trient essentiellement le tableau en retournant le nombre maximum au début, puis en le retournant à l'arrière, en répétant cela avec le tableau restant. Le premier utilise réduire, le second utilise une boucle for.

Non golfé:

array => {
  let flop = n => {
    array = [...array.slice(0, n).reverse(), ...array.slice(n)]; 
    return n;
  }
  let flops = [];
  for (let i = array.length + 1; --i > 0;) 
  {
    let maxIndex = array.indexOf(Math.max(...array.slice(0, i)));
    flops.push(flop(maxIndex + 1), flop(i));
  }
  return flops;
}

Perl 5.10 (ou supérieur), 66 octets

Comprend +3pour -n l' use 5.10.0apporter la langue au niveau perl 5.10 est considéré comme gratuit

#!/usr/bin/perl -n
use 5.10.0;
$'>=$&or$.=s/(\S+) \G(\S+)/$2 $1/*say"$. 2 $."while$.++,/\S+ /g

Exécutez avec l'entrée en une seule ligne sur STDIN:

flop.pl <<< "1 8 3 -5 6"

Trie la liste en trouvant à plusieurs reprises toute inversion, en la renversant vers l'avant, puis en renversant l'inversion et en replaçant le tout dans son ancienne position.

C'était étonnamment difficile de se retrouver dans le même stade que le python sur celui-ci :-)

C (gcc) , 165160 octets

• Merci à plafondcat pour avoir économisé cinq octets.

m,j,t;f(A,l)int*A;{for(j=0;j+j<l;A[j]=A[l+~j],A[l+~j++]=t)t=A[j];}F(A,l)int*A;{for(;l;f(A,++m),printf("%d,%d,",m,l),f(A,l--))for(j=m=0;j<l;j++)m=A[j]>A[m]?j:m;}

• Essayez-le en ligne!
• Vérification