Introducción

Por supuesto, tenemos muchos desafíos de secuencia , así que aquí hay otro.

La secuencia de Kimberling ( A007063 ) es la siguiente:

1, 3, 5, 4, 10, 7, 15, 8, 20, 9, 18, 24, 31, 14, 28, 22, ...

Esto se produce barajando la iteración normal:

[1] 2  3  4  5  6  7  8

El primer término de la secuencia es 1. Después de eso, reorganizamos la secuencia hasta que se usen todos los términos de la izquierda. La mezcla tiene el patrón right - left - right - left - .... Como no hay términos a la izquierda del 1, no hay barajado. Obtenemos lo siguiente:

 2 [3] 4  5  6  7  8  9

En el i ^ª iteración, descartamos la i ^º elemento y ponerlo en nuestra secuencia. Esta es la segunda iteración, por lo que descartamos el segundo elemento. La secuencia se convierte en: 1, 3. Para nuestra próxima iteración, vamos a barajar la iteración actual con el patrón anterior. Tomamos el primer elemento que no utilice a la derecha de la i ^º artículo. Esto pasa a ser 4. Agregaremos esto a nuestra nueva iteración:

 4

Ahora vamos a dar el primer elemento que no utilice a la izquierda del i ^ésimo elemento. Esto es 2. Agregaremos esto a nuestra nueva iteración:

 4  2

Dado que no existen elementos que quedan en la parte izquierda de la i ^º artículo, voy a anexar el resto de la secuencia de la nueva iteración:

 4  2 [5] 6  7  8  9  10  11  ...

Esta es nuestra tercera iteración, por lo que descartaremos el tercer elemento, que es 5. Este es el tercer elemento de nuestra secuencia:

 1, 3, 5

Para obtener la siguiente iteración, simplemente repita el proceso. He hecho un gif si no está claro:

^{El gif me llevó más tiempo que escribir la publicación real}

Tarea

• Dado un número entero no negativo n , genera los primeros n términos de la secuencia
• Puede proporcionar una función o un programa
• Este es el código de golf , por lo que gana el envío con la menor cantidad de bytes.

Casos de prueba:

Input: 4
Output: 1, 3, 5, 4

Input: 8
Output: 1, 3, 5, 4, 10, 7, 15, 8

Input: 15
Output: 1, 3, 5, 4, 10, 7, 15, 8, 20, 9, 18, 24, 31, 14, 28

Nota: Las comas en la salida no son necesarias. Puede, por ejemplo, usar nuevas líneas o generar una lista, etc.

Pyth, 22 bytes

JS*3QVQ@JN=J.i>JhN_<JN

Pruébelo en línea: demostración

Simplemente realiza la técnica de barajado descrita en el OP.

Explicación:

JS*3QVQ@JN=J.i>JhN_<JN
JS*3Q                    assign the list [1, 2, ..., 3*input-1] to J
     VQ                  for N in range(Q):
       @JN                  print J[N]
            .i              interleave 
              >JhN             J[N+1:] with
                  _<JN         reverse J[:N]
          =J                assign the resulting list to J

Julia, 78 71 bytes

n->[(i=j=x;while j<2i-3 j=i-(j%2>0?1-j:j+2)÷2;i-=1end;i+j-1)for x=1:n]

Esta es una función sin nombre que acepta un entero y devuelve una matriz de enteros. Para llamarlo, asígnelo a una variable.

El enfoque aquí es el mismo que el descrito en OEIS.

Sin golf:

# This computes the element of the sequence
function K(x)
    i = j = x
    while j < 2i - 3
        j = i - (j % 2 > 0 ? 1 - j : j + 2)÷2
        i -= 1
    end
    return i + j - 1
end

# This gives the first n terms of the sequence
n -> [K(i) for i = 1:n]

¡Guardado 7 bytes gracias a Mauris!

Mathematica 130 bytes

(n=0;s={};Nest[(n++;AppendTo[s,z=#[[n]]];Flatten[TakeDrop[#,1+2(n-1)]/.{t___,z,r___}:> 
Riffle[{r},Reverse@{t}]])&,Range[3*#],#];s)&

Comenzamos con una lista que consiste en el rango de 1a 3x, donde xes el número deseado de términos de secuencia de Kimberling.

En cada paso, n, TakeDroprompe el la lista actual en una lista delante de 2n+1términos (donde se realiza el trabajo) y la lista trasero (que será más tarde se unió a la lista de reelaborado frontal). La lista frontal coincide con el siguiente patrón, {t___,z,r___}donde z es el término de Kimberling en el centro de la lista frontal. res Riffle'd con el reverso de ty luego se agrega la lista posterior. zse elimina y se agrega a ( AppendTo) la secuencia creciente de Kimberling.

nse incrementa en 1y la lista actual es procesada por la misma función a través deNest.

Ejemplo

(n=0;s={};Nest[(n++;AppendTo[s,z=#[[n]]];Flatten[TakeDrop[#,1+2(n-1)]/.{t___,z,r___}:> 
Riffle[{r},Reverse@{t}]])&,Range[3*#],#];s)&[100]

{1, 3, 5, 4, 10, 7, 15, 8, 20, 9, 18, 24, 31, 14, 28, 22, 42, 35, 33, 46, 53, 6, 36, 23, 2 , 55, 62, 59, 76, 65, 54, 11, 34, 48, 70, 79, 99, 95, 44, 97, 58, 84, 25, 13, 122, 83, 26, 115, 82, 91 , 52, 138, 67, 90, 71, 119, 64, 37, 81, 39, 169, 88, 108, 141, 38, 16, 146, 41, 21, 175, 158, 165, 86, 191, 45 , 198, 216, 166, 124, 128, 204, 160, 12, 232, 126, 208, 114, 161, 156, 151, 249, 236, 263, 243, 101, 121, 72, 120, 47, 229 }

Python 2, 76 bytes

for a in range(input()):
 b=a+1
 while-~b<2*a:b=a-(b^b%-2)/2;a-=1
 print a+b

Explicación

¡Esta es la fórmula OEIS después de muchas transformaciones de golf! Funcionó maravillosamente . El código original era

i=b=a+1
while b<2*i-3:b=i-(b+2,1-b)[b%2]/2;i-=1
print i+b-1

Primero lo eliminé i, reemplazándolo por a+1todas partes y expandiendo las expresiones:

b=a+1
while b<2*a-1:b=a+1-(b+2,1-b)[b%2]/2;a-=1
print a+b

Luego, volvió a escribir b<2*a-1como -~b<2*apara guardar un byte de espacio en blanco, y se trasladó al +1en la selección, la división por 2, y la negación:

while-~b<2*a:b=a-(b,-b-1)[b%2]/2;a-=1

Entonces, -b-1es justo ~b, para que podamos escribir (b,~b)[b%2]. Esto es equivalente a b^0 if b%2 else b^-1usar el operador XOR, o alternativamente b^b%-2.

while-~b<2*a:b=a-(b^b%-2)/2;a-=1

Pyth, 29 25 bytes

VQ+.W<hHyN-~tN/x%Z_2Z2hNN

Jakube guardó 4 bytes, pero ya no tengo idea de cómo leer el código.

Aquí está la vieja solución:

VQKhNW<hKyN=K-~tN/x%K_2K2)+KN

Traducción de mi respuesta de Python. No soy muy bueno en Pyth, así que tal vez todavía hay formas de acortar esto.

VQ                              for N in range(input()):
  KhN                             K = N+1
     W<hKyN                       while 1+K < 2*N:
           =K-~tN/x%K_2K2)         K = (N--) - (K%-2 xor K) / 2
                          +KN     print K + N

APL, 56 44 bytes

{⍵<⍺+⍺-3:(⍺-1)∇⍺-4÷⍨3+(1+2×⍵)ׯ1*⍵⋄⍺+⍵-1}⍨¨⍳

Este es un tren monádico sin nombre que acepta un número entero a la derecha y devuelve una matriz. Es aproximadamente el mismo enfoque que mi respuesta de Julia .

La función más interna es una función diádica recursiva que devuelve el n º plazo en la secuencia Kimberling, dada n como izquierda idénticos y argumentos adecuados.

{⍵<⍺+⍺-3:                                    ⍝ If ⍵ < 2⍺ - 3
         (⍺-1)∇⍺-4÷⍨3+(1+2×⍵)ׯ1*⍵           ⍝ Recurse, incrementing a and setting
                                             ⍝ ⍵ = ⍺ - (3 + (-1)^⍵ * (1 + 2⍵))/4
                                   ⋄⍺+⍵-1}   ⍝ Otherwise return ⍺ + ⍵ - 1

Con eso en la mano, podemos obtener términos individuales de la secuencia. Sin embargo, el problema se convierte en que esta es una función diádica , lo que significa que requiere argumentos en ambos lados. Ingrese el ⍨operador! Dada una función fy una entrada x, f⍨xes lo mismo que x f x. Entonces, en nuestro caso, refiriéndonos a la función mencionada anteriormente f, podemos construir el siguiente tren monádico:

f⍨¨⍳

Aplicamos fa cada número entero desde 1 hasta la entrada, produciendo una matriz.

¡Guardado 12 bytes gracias a Dennis!