Crear una secuencia entera universal

22

Definición

Llamemos universal a una secuencia entera (infinita) si contiene cada secuencia entera finita como una subsecuencia contigua.

En otras palabras, la secuencia entera (a 1 , a 2 , ...) es universal si y solo si, para cada secuencia entera finita (b 1 , ..., b n ) , hay un desplazamiento k tal que (a k + 1 , ..., a k + n ) = (b 1 , ..., b n ) .

La secuencia de números primos positivos, por ejemplo, no es universal, entre otras, por las siguientes razones.

  • No contiene enteros negativos, 1 o números compuestos.

  • Aunque contiene 3 , no contiene la subsecuencia contigua (3, 3, 3) .

  • Aunque contiene 2 y 5 , no contiene la subsecuencia contigua (2, 5) .

  • Aunque contiene la subsecuencia contigua (7, 11, 13) , no contiene la subsecuencia contigua (13, 11, 7) .

Tarea

Elija cualquier secuencia entera universal (un 1 , un 2 , ...) e impleméntela en el lenguaje de programación que elija, respetando las siguientes reglas.

  • Puede enviar un programa completo o una función.

  • Tiene tres opciones para E / S:

    1. No ingrese datos e imprima o devuelva la secuencia completa.

    2. Tome un índice n como entrada e imprima o devuelva un n .

    3. Tome un índice n como entrada e imprima o devuelva (un 1 , ..., un n ) .

  • Para las opciones de E / S 2 y 3 , puede usar la indexación basada en 0 si lo prefiere.

  • Su envío debe ser determinista: si se ejecuta varias veces con la misma entrada, debe producir la misma salida.

Además, a menos que sea inmediatamente obvio, pruebe que la secuencia que eligió es universal. Su prueba puede no depender de conjeturas no comprobadas.

Aplican reglas estándar de . ¡Que gane el código más corto en bytes!

Dennis
fuente
Su prueba puede no depender de conjeturas no comprobadas. Pensé que eso estaba implícito: p
Erik the Outgolfer
y cómo guardarías una lista de números en un número?
RosLuP

Respuestas:

13

Casco , 5 bytes

Esto imprime una lista infinita

ΣṖ…ݱ

Pruébalo en línea! o encuentre el primer índice de su secuencia . (Toma mucha memoria para la mayoría de las secuencias)

Explicación:

   ݱ   Infinite list [1,-1,2,-2,3,-3,4,-4,5,-5...]
  …     Rangify       [1,0,-1,0,1,2,1,0,-1,-2,...]
 Ṗ      Powerset
Σ       Concatenate

En Husk se comporta muy bien para listas infinitas. Puedes ver su comportamiento aquí

H.PWiz
fuente
Es posible que desee detallar cómo Qfunciona. (Creo que lo tengo, pero no estoy seguro.)
Dennis
@Dennis resulta que quería , noQ
H.PWiz
9

Python 2 , 49 46 43 bytes

def f(n):d=len(`n`);return n/d**(n%d)%d-d/2

f(n)devuelve una n solamente. Utiliza el dígito más pequeño de nin base dpara extraer uno de los dígitos más altos.

Pruébalo en línea! Este guión (cortesía de Dennis) toma cualquier secuencia finita y le da un lugar ndonde comienza esa secuencia.

Explicación

n/d**(n%d)%d-d/2
     (n%d)         least significant digit of n
n/d**(   )%d       get n%d-th digit of n
            -d/2   offset to get negative values

Por ejemplo, for nen el rango 3141592650de 3141592659, d=10y el último dígito de nselecciona uno de los otros dígitos. Luego sumamos -d/2para obtener valores negativos.

n%d:       0  1  2  3  4  5  6  7  8  9
f(n)+d/2:  0  5  6  2  9  5  1  4  1  3
f(n):     -5  0  1 -3  4  0 -4 -1 -4 -2

Alternativa independiente, también 43 bytes:

n=input();d=len(`n`);print n/d**(n%d)%d-d/2
japh
fuente
Puedes usar en len(`n`)lugar de len(str(n)).
Dennis
Gracias @ Dennis. Puedo agregar más explicaciones si alguien lo necesita.
japh
Escribí una función que, dada una secuencia finita, encuentra un desplazamiento en su secuencia. Pruébalo en línea!
Dennis
Esto es muy genial.
histocrat
Agradable. Lo único es que se romperá hacia arriba n=2**63-1ya que la representación se Lagrega ( str(n)abordaría eso por tres bytes si es necesario).
Jonathan Allan
5

Brachylog 2, 11 bytes

≜~×-₂ᵐ~ȧᵐ≜∋

Pruébalo en línea!

También probé un algoritmo que usa particiones aditivas en una lista, pero no fue más corto. Este es un generador que produce un flujo infinito de enteros como salida; el enlace TIO tiene un encabezado para imprimir los primeros diez mil de ellos.

Explicación

El programa comienza probando todos los enteros posibles en secuencia ( prueba todas las posibilidades restantes, para enteros por defecto). Eso es 0, 1, -1, 2, -2, etc. (aunque los enteros negativos no llegan al final del programa). Este es el único paso "infinito" del programa; Todos los demás son finitos.

luego genera todas las factorizaciones posibles del número entero, trata diferentes órdenes como diferentes y usa solo valores de 2 en adelante (por lo que solo hay muchas); tenga en cuenta que los números compuestos están permitidos en la factorización, no solo primos. Esto significa que todas las secuencias posibles de enteros ≥ 2 serán generadas por este paso en algún momento de la ejecución de la función (como tal, una secuencia necesariamente tiene algún producto, y ese producto se generará en algún punto por la inicial ).

Luego necesitamos mapear el conjunto de esas secuencias en el conjunto de todas las secuencias de enteros, lo que se realiza en dos pasos: restar 2 ( -₂) de cada elemento ( ), dándonos el conjunto de todas las secuencias de enteros no negativos, luego tomando más o menos ( es decir, "un valor cuyo valor absoluto es") cada elemento () El último paso es obviamente no determinista, por lo que Brachylog lo trata como un generador, generando todas las listas posibles cuyos elementos son más o menos el elemento correspondiente de la lista de entrada. Esto significa que ahora tenemos un generador para todas las secuencias enteras posibles, y las genera en un orden que significa que todas se generan (específicamente, el orden que obtienes si tomas el valor absoluto de cada elemento, suma 2 a cada elemento, y luego ordenar por el producto de los elementos resultantes).

Desafortunadamente, la pregunta quiere una sola secuencia, no una secuencia de secuencias, por lo que necesitamos dos comandos más. Primero, solicita a Brachylog que genere explícitamente la secuencia de secuencias estrictamente (en lugar de producir una estructura de datos que describa el concepto de una secuencia generada mediante este método, y no generar las secuencias hasta que sea necesario); Esto sucede para que el programa sea más rápido en este caso y garantiza que la salida se produzca en el orden solicitado. Finalmente, hace que el generador genere los elementos de las secuencias individuales de uno en uno (pasando a la siguiente secuencia una vez que genera todos los elementos de la secuencia anterior).

El resultado final: cada posible secuencia entera se genera y genera, un elemento a la vez, y todos se concatenan en una sola secuencia universal.

usuario62131
fuente
ais523 ... ¿eres tú?
Fatalize
Si no son ellos, es una gran coincidencia, considerando que las publicaciones de su cuenta eliminada muestran el mismo número de cuenta.
totalmente humano
4

Python 2 , 100 99 bytes

  • Guardado un byte gracias a los ovs ; iterando sobre un itertoolsbucle incorporado a indefinidamente.
from itertools import*
for n in count():
 for P in permutations(range(-n,n)*n):
	for p in P:print p

Pruébalo en línea!

Imprime indefinidamente todas las permutaciones del nrango entero repetido veces [-n; n)para todos los enteros no negativos n.
Puede buscar el primer desplazamiento kpara cualquier subsecuencia utilizando esta versión modificada .

Jonathan Frech
fuente
while~0:. Je je ...
Chas Brown
99 bytes usandoitertools.count
ovs
@ovs Gracias; No sabía de eso incorporado.
Jonathan Frech
2

Perl 6 , 91 bytes

loop (my$i=1;;$i++){my@n=(-$i..$i);my@m=@n;loop (my$k=1;$k <$i;$k++){@m=@m X@n;};print @m;}

Pruébalo en línea!

Esto usa un método similar a algunas de las otras respuestas. Utiliza productos cartesianos para imprimir los elementos (-1,0,1), luego todos los pares ordenados de los elementos (-2,-1,0,1,2), luego todos los tripletes ordenados de los elementos (-3,-2,-1,0,1,2,3), etc.

Soy nuevo en Perl, por lo que podría haber más golf que se podría hacer.

Versión más legible:

loop (my $i = 1; ; $i++) {
  my @n = (-$i..$i);
  my @m = @n;
  loop (my $k=1; $k <$i; $k++) {
    @m = @m X @n;
  }
  print @m;
}
KSmarts
fuente