Como informáticos, probablemente estén familiarizados con las operaciones básicas de listas de pop y push . Estas son operaciones simples que modifican una lista de elementos. Sin embargo, ¿alguna vez has oído hablar del fracaso de la operación ? (como en flip- flop )? Es muy simple Dado un número n , invierta los primeros n elementos de la lista. Aquí hay un ejemplo:

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

Lo bueno de la operación de flop es que puedes usarla para hacer algunas cosas interesantes en una lista, como ordenarla . Vamos a hacer algo similar con los flops:

Dada una lista de enteros, "Vecino". En otras palabras, ordénelo para que cada elemento duplicado aparezca consecutivamente.

¡Esto se puede hacer con flops! Por ejemplo, tome la siguiente lista:

>>> 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]

Esto nos lleva a la definición del desafío de hoy:

Dada una lista de enteros, genere cualquier conjunto de flops que resulte en la lista de vecinos.

Usando la última lista como ejemplo, debe generar:

4
3
6

porque si la lista se despliega en 4, luego en 3 y luego en 6, se obtendrá una lista de vecinos. Tenga en cuenta que no necesita imprimir la lista de flops más corta posible que esté junto a una lista. Si hubiera impreso:

4
4
4
3
1
1
6
2
2

en cambio, esto todavía sería una salida válida. Sin embargo, es posible que no siempre el número de una salida mayor que la longitud de la lista. Esto se debe a que para una lista a = [1, 2, 3], llamar no a.flop(4)tiene sentido.

Aquí hay unos ejemplos:

#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]

Tenga en cuenta que en cada uno de estos ejemplos, la salida dada es solo una salida válida potencial. Como dije antes, cualquier conjunto de flops que sea vecino de la lista dada es una salida válida . Puede usar esta secuencia de comandos de Python para verificar si una lista dada de flops se encuentra correctamente junto a una lista.

Puede tomar entrada y salida en cualquier formato razonable. Por ejemplo, los argumentos de función / valor de retorno, STDIN / STDOUT, leer / escribir un archivo, etc. son todos válidos. Como de costumbre, este es el código de golf , ¡así que haz el programa más corto que puedas y diviértete! :)

Haskell , 98 71 bytes

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

Pruébalo en línea!

Explicación

Para una lista de longitud neste método produce2*n flops. Funciona mirando el último elemento de la lista, buscando el mismo elemento en la lista anterior y volteándolo a la penúltima posición. Luego, la lista con el último elemento eliminado es recursivamente "vecina".

Para la lista, [1,2,3,1,2]el algoritmo funciona así:

[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
 ...

En conjunto, esto produce los fracasos [2,4,0,3,1,2,0,1,0,0]y la lista vecina [3,1,1,2,2].

Wolfram Language (Mathematica) , 71 bytes

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

Pruébalo en línea!

Cómo funciona

Dada una matriz de longitud n, genera una secuencia de 4nflops que ordena la matriz en orden creciente: en particular, colocando elementos duplicados uno al lado del otro.

La idea es que para ordenar una matriz, movemos su elemento más grande hasta el final, y luego ordenamos los primeros n-1elementos de la matriz. Para evitar implementar la operación de flop, movemos el elemento más grande hasta el final de manera que no moleste a los otros elementos:

{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 general, si el elemento más grande está en posición i, la secuencia de flops que lo mueve hasta el final lo es i, n, n-1, i-1.

Python 2 , 69 bytes

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

Pruébalo en línea!

Jalea , 19 17 bytes

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

Ordena la lista.

Pruébalo en línea!

Limpio , 88 bytes

Creo que hay uno posiblemente más corto con guardias, pero aún no lo he encontrado.

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

$o r

Pruébalo en línea!

Como una función literal. Funciona de la misma manera que la respuesta de Hasikell de Laikoni , pero el golf es un poco diferente y, por supuesto, también en un idioma diferente.

JavaScript, 150 bytes

(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++)],[])

Pruébalo en línea!

JavaScript, 151 bytes

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}

Pruébalo en línea!

Básicamente, ambos ordenan la matriz volteando el número máximo al principio y luego volteándolo hacia atrás, repitiendo esto con la matriz restante. El primero usa reduce, el segundo usa un bucle for.

Sin 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 (o superior), 66 bytes

Incluye +3para -n The use 5.10.0para llevar el idioma al nivel perl 5.10 se considera gratuito

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

Ejecute con la entrada como una línea en STDIN:

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

Ordena la lista encontrando repetidamente cualquier inversión, volviéndola al frente y luego volteando la inversión y volviendo a dejar todo en su posición anterior.

Fue sorprendentemente difícil entrar en el mismo estadio que Python en este :-)

C (gcc) , 165 bytes

• Gracias a ceilingcat por guardar cinco bytes.

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;}

• Pruébalo en línea!
• Verificación