18

Desafío

Dado un entero n ≥ 4 , genera una permutación de los enteros [0, n-1] con la propiedad de que no hay dos enteros consecutivos (enteros con diferencia absoluta 1) uno al lado del otro.

Ejemplos

4 → [1, 3, 0, 2]
5 → [0, 2, 4, 1, 3]
6 → [0, 2, 4, 1, 3, 5]
7 → [0, 2, 4, 1, 5, 3, 6]

En su lugar, puede usar la indexación 1 (usando enteros [1, n] en lugar de [0, n-1] ).

Su código debe ejecutarse en tiempo polinómico en n , por lo que no puede probar todas las permutaciones y probar cada una.

code-golf restricted-complexity Anush
fuente

Cuando dices "generar una permutación", ¿te refieres a una lista? ¿O podemos producir una función que implemente el mapeo de permutación en sí?

xnor

@xnor Debería salir en alguna forma legible por humanos. No me importa exactamente cómo.

Anush

¿ [[1,3],[0,2]]Sería un formato de salida aceptable?

Shaggy

@ Shaggy No es genial. ¿Significa 1,3,0,2?

Anush

Relacionado

Peter Taylor

31

Jalea , 3 2 bytes

ḂÞ

Ordena los enteros en [1, ..., n] por su LSB.

Pruébalo en línea!

Dennis
fuente

¡Guauu! Esto es increíble.

Anush

2

"Ordenar por LSB" significa que todos los demás se mueven al principio, pero ¿la definición de Jelly requiere que los números en cada mitad permanezcan en su orden original? De lo contrario, 100 (4) podría estar al lado de 101 (5) y aún estar "ordenado por LSB". No está fallando su código, pero ¿tal vez el comentario descriptivo no está completo?

WGroleau

1

@WGroleau Sí, Þordenación estable, porque se implementa utilizando la sortedfunción Python , que se garantiza que sea estable .

user202729

3

El algoritmo es más impresionante para mí que el tamaño pequeño, en su inteligencia. También podría, supongo, revertir el orden de bits, ordenar y revertirlo.

WGroleau

44

Solo puede haber 65536 programas Jelly de dos bytes diferentes. Es sorprendente que muchos de esos resulten ser respuestas a los desafíos de ppcg.

Anush

16

Python 2 , 32 bytes

lambda n:(range(n|1)*2)[1:n*2:2]

Pruébalo en línea!

ovs
fuente

8

Python 3 , 40 , 38 bytes

lambda n:[*range(1,n,2),*range(0,n,2)]

Pruébalo en línea!

Esto corre a O(n)tiempo.

¡Gracias a Dennis por guardar 2 bytes!

DJMcMayhem
fuente

¡Ganador del premio más rápido! :)

Anush

¿La carrera más rápida o la primera publicación?

WGroleau

2

@WGroleau Primero publicado.

user202729

6

Python 2 , 34 bytes

lambda n:range(1,n,2)+range(0,n,2)

Pruébalo en línea!

Python 2 , 40 bytes

lambda n:[(k-~k)%(n|1)for k in range(n)]

Pruébalo en línea!

xnor
fuente

6

Haskell, 22 bytes

f es una función de n que devuelve una lista ordenada adecuadamente. Estoy usando la opción de 1 indexación.

f n=[2,4..n]++[1,3..n]

Penguino
fuente

6

Octava , 17 bytes

@(x)[2:2:x,1:2:x]

Pruébalo en línea!

Esto utiliza el mismo enfoque que muchos otros. Concatene dos vectores, uno con todos los números pares en el rango inclusivo 2 ... x , y todos los números impares en el rango inclusivo 1 ... x . La sintaxis debería ser bastante obvia, por lo que no explicaré eso.

Stewie Griffin
fuente

1

¿No están 3y 2uno al lado del otro f(4)?

pajonk

Vaya ... arreglado. El mismo recuento de bytes. :-)

Stewie Griffin

5

JavaScript (ES6), 40 bytes

f=
n=>[...Array(i=n)].map(_=>(i+--i)%(n|1))

<input type=number min=4 oninput=o.textContent=f(+this.value).join`\n`><pre id=o>

Expandir fragmento

Editar: guardado 1 byte gracias a @Arnauld.

Neil
fuente

5

Gaia , 2 bytes

r∫

Pruébalo en línea!

Esto simplemente (estable) ∫ Ørts los números enteros en el intervalo [1, de entrada] por su pa r dad.

Sr. Xcoder
fuente

El mismo comentario que en Jelly: ¿el algoritmo o la definición del lenguaje garantizan que las dos mitades permanezcan en su orden original?

WGroleau

@WGroleau Sí, en Gaia, el metaoperador de clasificación es estable.

Sr. Xcoder

5

R , 39 36 35 bytes

function(x)c(seq(2,x,2),seq(1,x,2))

Pruébalo en línea!

ngm
fuente

Hay un NA final para números impares.

JayCe

tio.run/#%23K/qfZvs/…

JayCe

La culpa de la esposa. Tuvimos que ir en bicicleta antes de que pudiera arreglar eso. Pero también recortó algunos bytes.

ngm

Sí, me sentí mal pidiéndole que agregue bytes, así que tuve que encontrar la manera de eliminar algunos ... funcionó bien.

JayCe

1

inspirado en la respuesta de octava

Giuseppe

4

05AB1E , 3 bytes

Puerto de la respuesta de DJMcMayhem Python y Dennis's Jelly

ÝΣÉ

Pruébalo en línea!

¿Cómo?

ÝΣÉ - implicitly take input onto stack  e.g. 7
Ý   - pop a and push range(a)               [0,1,2,3,4,5,6]
 Σ  - sort by (stable):
  É -   is even? (x%2==0 ?)                 [1,3,5,0,2,4,6]
    - implicit print of top of stack

Jonathan Allan
fuente

4

Japt, 4 bytes

También podrías reemplazar uconv para obtener un orden diferente.

õ ñu

Intentalo

O, si podemos superar una matriz de 2 matrices:

õ ó

Intentalo

Lanudo
fuente

Técnicamente, el segundo genera una lista de números separados por comas ;-) 4Desafortunadamente, ambos fallan ; se puede fijar el primero cambiando ua vo oa õ.

ETHproductions

3

Mathematica, 50 -> 47 -> 42 bytes

p = Join[Range[2, #, 2], Range[1, #, 2]] &

Pruébalo en línea!

Gracias a user202729 por señalar el doble potencial de optimización Únase [] en lugar de Flatten [] y utilice funciones puras.

Me gustaría agregar dos comentarios.

1) Es bastante sencillo construir una permutación específica sin sucesión descendente o ascendente para n> = 4 como se solicita en el OP.

Consiste en dos listas consecutivas.

Para incluso n estos son:
list1 = (2,4, ..., n / 2)
list2 = (1,3, ..., n / 2-1)

Para n impar tenemos:
list1 = (2,4, ..., Floor [n / 2])
list2 = (1,3, ..., Floor [n / 2])

Para este "algoritmo" solo se debe tomar una decisión (n par o impar), el resto es simplemente escribir n números.

Se proporciona una posible solución de Mathematica en la parte superior.

2) Una pregunta relacionada es cuántas permutaciones existen en función de n.

Mathematica, 124 Bytes

a[0] = a[1] = 1; a[2] = a[3] = 0;
a[n_] := a[n] = (n + 1)*a[n - 1] - (n - 2)*a[n - 2] - (n - 5)*a[n - 3] + (n - 3)*a[n - 4]

Pruébalo en línea!

Ejemplo:

a[#] & /@ Range[4, 12]

{2, 14, 90, 646, 5242, 47622, 479306, 5296790, 63779034}

Contar el número de tales permutaciones es un problema estándar.

Para n = 4 hay 2: {{2,4,1,3}, {3,1,4,2}}

Para n = 5 hay 14: {{1,3,5,2,4}, {1,4,2,5,3}, {2,4,1,3,5}, {2,4, 1,5,3}, {2,5,3,1,4}, {3,1,4,2,5}, {3,1,5,2,4}, {3,5,1, 4,2}, {3,5,2,4,1}, {4,1,3,5,2}, {4,2,5,1,3}, {4,2,5,3, 1}, {5,2,4,1,3}, {5,3,1,4,2}}

El número a (n) de estas permutaciones aumenta rápidamente: 2, 14, 90, 646, 5242, 47622, 479306, 5296790, 63779034, ...

Para n grande, la relación a (n) / n! parece acercarse al límite 1 / e ^ 2 = 0.135335 ... No tengo pruebas estrictas, pero es solo una conjetura de la evidencia numérica. Puede probar esto intentando ejecutar el programa en línea.

El programa anterior (basado en la referencia dada a continuación) calcula estos números.

Puede encontrar más información en la secuencia relevante en OEIS: A002464 . El problema de Hertzsprung: formas de organizar n reyes que no atacan en un tablero n X n, con 1 en cada fila y columna. También número de permutaciones de longitud n sin sucesiones ascendentes o descendentes.

Dr. Wolfgang Hintze
fuente

@ Stewie Griffin Como soy nuevo aquí, explique con más detalle lo que quiere decir. En mi primer comentario, proporcioné un algoritmo y un código que resuelve el problema en tiempo polinómico. Por lo tanto, debe considerarse una solución al desafío. La segunda parte extiende el interesante problema. Por lo tanto, debe considerarse como un comentario.

Dr. Wolfgang Hintze

Me tomé la libertad de modificar ligeramente su envío para que su código de Mathematica esté en la parte superior. Con los desafíos de código de golf, es obligatorio proporcionar el código real (lo más corto posible). La forma en que lo formateé se convierte en una respuesta de Mathematica como probablemente pretendías que fuera, y todavía tiene tu explicación original debajo. Si siente que falta algo o edité incorrectamente su respuesta inicial, siéntase libre de editarlo usted mismo nuevamente. Bienvenido a PPCG! :)

Kevin Cruijssen

@ Kevin Cruijssen Muchas gracias por la cálida bienvenida y la edición de mi ingenua presentación. Ahora he agregado un programa de Mathematica para el segundo comentario. Lo que probablemente no sea lege artis. Sobre todo, no sé cómo crear el bonito enlace "pruébelo en línea".

Dr. Wolfgang Hintze

Cualquier enlace se puede crear usando [some text](the_link). En cuanto al enlace "Pruébelo en línea" en particular, el sitio web https://tio.run/ que está alojado por nuestro propio @Dennis contiene enlaces a todo tipo de lenguajes de programación. Wolfram Language (Mathematica) es uno de ellos. En la parte superior, puede hacer clic en el botón de reproducción para ejecutar el código, o en el botón de hipervínculo para copiar "Pruébelo en línea". (marcado-) enlaces. Y puede dividir su código en "Código" real (su envío), con un encabezado / pie de página opcional para (bastante) imprimir una o varias cajas de prueba.

Kevin Cruijssen

Disculpas por mi comentario algo contundente, y la falta de respuesta a partir de entonces! La respuesta apareció en la cola de revisión, y no noté el código debido al formato. No es raro que los nuevos usuarios publiquen "observaciones interesantes" a los desafíos, sin proporcionar una respuesta real. Si bien se hace de buena fe, no se trata del sitio. Pensé que esta era una respuesta. Debería haber respondido a su comentario, pero tenía prisa y no podía escribir un nuevo comentario, así que en lugar de eso, eliminé el anterior. Disculpas! ¡Y bienvenido al sitio! ¡Espero que te quedes! :)

Stewie Griffin

2

JavaScript (Node.js) , 42 bytes

n=>(f=i=>i<n?[i,...f(i+2)]:i&1?[]:f(1))(0)

Pruébalo en línea!

JavaScript (Node.js) , 47 bytes

n=>(f=i=>i--?[n--*2%(N|1)+N%2,...f(i)]:[])(N=n)

Pruébalo en línea!

l4m2
fuente

2

Rubí , 27 bytes

->n{[*2.step(n,2)]|[*1..n]}

Pruébalo en línea!

Usando la indexación 1

GB
fuente

2

Espacio en blanco , 161 bytes

Aquí está la presentación oficial, sin comentarios: ¡ Pruébelo en línea!

push_0   
read_n	
		push_0   
retreive_n			push_1  		
subtract	   dup_and_out[ 
 	
 	]label_s'
   
'push_2  		 
subtract	   dup[ 
 ]jump_next_if_neg:
		  
:dup_and_out[ 
 	
 	]else_jump_back:
 
 
:label_ss'
    
'push_0   
retreive_n			push_2  		 
subtract	   dup_and_out[ 
 	
 	]dup[ 
 ]jump_next:
 
    
:label_ssss'
      
'push_2  		 
subtract	   dup[ 
 ]jump_end_if_neg:
		   
:dup_and_out[ 
 	
 	]else_jump_back:
 
    
:label_sss'
     
'end

Pruébalo en línea!

Sacrifiqué unos pocos bytes para que el programa se ejecute sin errores, creo que podría perder alrededor de 7-8 bytes, y aún se generaría correctamente, pero también generaría mensajes de error, y nadie quiere eso.

Explicación completa de bytes:

[Space][Space][Space][N]                   Push a 0 on the stack
[Tab][Tab][N][Tab][Tab][Tab][Tab]          Read input value and store in heap
[Space][Space][Space][N]                   Push a 0 on the stack again
[Tab][Tab][Tab]                            Retrieve the value from the heap
[Space][Space][Tab][Tab][N]                Push a -1 on the stack
[Tab][Space][Space][Space]                 Add -1 to value
[Space][N][Space]                          Duplicate 
[Tab][N][Space][Tab]                       Output
[N][Space][Space][Space][N]                Set First Label
[Space][Space][Tab][Tab][Space][N]         Push a -2 on the stack
[Tab][Space][Space][Space]                 Subtract 2 from value
[Space][N][Space]                          Duplicate
[N][Tab][Tab][Space][Space][N]             If negative, jump to second label
[Space][N][Space]                          Duplicate
[Tab][N][Space][Tab]                       Output
[N][Space][N][Space][N]                    Jump back to first label
[N][Space][Space][Space][Space][N]         Set Second Label
[Space][Space][Space][N]                   Push a 0 on the stack
[Tab][Tab][Tab]                            Retrieve input value from heap again
[Space][Space][Tab][Tab][Space][N]         Push a -2 on the stack
[Tab][Space][Space][Space]                 This time, Add a -2 to the value
[Space][N][Space]                          Duplicate
[Tab][N][Space][Tab]                       Output
[Space][N][Space]                          Duplicate
[N][Space][N][Space][Tab][N]               Jump to third label
[N][Space][Space][Space][Tab][N]           Set third label
[Space][Space][Tab][Tab][Space][N]         Push a -2 on the stack
[Tab][Space][Space][Space]                 Subtract 2 from value
[Space][N][Space]                          Duplicate
[N][Tab][Tab][Space][Space][Space][N]      Jump to end if negative
[Space][N][Space]                          Duplicate
[Tab][N][Space][Tab]                       Output
[N][Space][N][Space][Tab][N]               Jump back to third label
[N][Space][Space][Space][Space][Space][N]  Set fourth label/end
[N][N][N]                                  Terminate

X1M4L
fuente

Algunas cosas para el golf: push_0, read_STDIN_as_int, push_0, retrievepuede ser push_0, duplicate_0, read_STDIN_as_int, retrieveguardar un byte. Y la primera etiqueta puede ser vacía con en NSSNlugar de NSSSN(y luego la segunda etiqueta puede ser NSSSN; tercera NSSTNy cuarta NSSSSN). Esto también debería ahorrar 8 bytes. Además, puede eliminar el primero Jump_to_third_labelporque ya tiene el Set_third_labelderecho debajo. En total: 140 bytes ; (o con comentarios: Pruébelo en línea ). -3 bytes si elimina la NNNsalida.

Kevin Cruijssen

1

F # (Mono) , 27 bytes

let f n=[2..2..n]@[1..2..n]

Pruébalo en línea!

Henrik Hansen
fuente

1

Gol> <> , 14 bytes

FL:2%Z}:3=?$|B

Pruébalo en línea!

Programa completo de ejemplo y cómo funciona

1AGIE;GDlR~
FL:2%Z}:3=?$|B

1AG          Register row 1 as function G
   IE;       Take number input; halt on EOF
      GD     Call G and print the stack
        lR~  Empty the stack
             Repeat indefinitely

F           |   Repeat n times...
 L              Push loop counter (0..n-1)
  :2%Z}         If even, move to bottom of the stack
       :3=?$    If top == 3, swap top two
                  This is activated only once to make [2 0 3 1]
             B  Return

Bubbler
fuente

1

J , 10 bytes

i./:2|1+i.

Pruébalo en línea!

Explicación:

  /:          sort
i.            the numbers in the range 0..n-1 
    2|        according the remainder mod 2 of 
      1+i.    the numbers in the range 1..n

Galen Ivanov
fuente

1

Java 8, 56 bytes

n->{for(int i=n;i>0;)System.out.println((i+--i)%(n|1));}

Puerto de la respuesta JavaScript de @Neil (ES6) .

Pruébalo en línea.

Antigua respuesta de 66 bytes:

n->{String[]r={"",""};for(;n-->0;)r[n%2]+=n+" ";return r[0]+r[1];}

Pruébalo en línea.

Explicación:

n->{                  // Method with integer parameter and String return-type
  String[]r={"",""};  //  Result-Strings, both starting empty
  for(;n-->0;)        //  Loop in the range (n, 0]
    r[i%2]+=i+" ";    //   Append `i` and a space to one of the two result-Strings,
                      //   depending on if it is even (first) or odd (second)
  return r[0]+r[1];}  //  Return the two result-Strings appended to each other

Kevin Cruijssen
fuente

1

Rubí, 27 bytes

->n{(1..n).sort_by{|i|i&1}}

Como en esta respuesta , los nprimeros enteros se ordenan por su bit menos significativo.

Pruébalo en línea!

Eric Duminil
fuente

Dar una permutación sin dos enteros consecutivos uno al lado del otro

Respuestas:

Jalea , 3 2 bytes

Python 2 , 32 bytes

Python 3 , 40 , 38 bytes

Python 2 , 34 bytes

Haskell, 22 bytes

Octava , 17 bytes

JavaScript (ES6), 40 bytes

Gaia , 2 bytes

R , 39 36 35 bytes

05AB1E , 3 bytes

¿Cómo?

Japt, 4 bytes

Mathematica, 50 -> 47 -> 42 bytes

Mathematica, 124 Bytes

JavaScript (Node.js) , 42 bytes

JavaScript (Node.js) , 47 bytes

Rubí , 27 bytes

Espacio en blanco , 161 bytes

Explicación completa de bytes:

F # (Mono) , 27 bytes

Gol> <> , 14 bytes

Programa completo de ejemplo y cómo funciona

J , 10 bytes

Explicación:

Java 8, 56 bytes

Rubí, 27 bytes