Generar secuencias de Skolem

10

Secuencias de Skolem

Una secuencia de Skolem es una secuencia de 2nnúmeros donde cada número ientre 1y nocurre exactamente dos veces, y la distancia entre las dos ocurrencias ies exactamente ipasos. Aquí hay algunos ejemplos de secuencias de Skolem:

1 1
1 1 4 2 3 2 4 3
16 13 15 12 14 4 7 3 11 4 3 9 10 7 13 12 16 15 14 11 9 8 10 2 6 2 5 1 1 8 6 5

Las siguientes secuencias no son secuencias de Skolem:

1 2 1 2      (The distance between the 1's is 2, not 1)
3 1 1 3      (The number 2 is missing)
1 1 2 1 1 2  (There are four 1's)

Objetivo

Escriba un programa, función o expresión para contar el número de todas las secuencias de Skolem de una longitud determinada. Más explícitamente, su entrada es un número entero n, y su salida es el número de secuencias de longitud de Skolem 2n. Esta secuencia tiene una entrada OEIS . Para n = 0, puede regresar cualquiera 0o 1. Los primeros valores, a partir de 0, son

0, 1, 0, 0, 6, 10, 0, 0, 504, 2656, 0, 0, 455936, 3040560, 0, 0, 1400156768

Reglas y puntaje

Este es el código de golf. El formato de salida es laxo dentro de lo razonable.

boothby
fuente
Solo curiosidad, pero ¿cuál es el 0, 1, 0, 0, 6...en su pregunta? ¿Es ese el fragmento de código, si es así, qué idioma es ese?
PhiNotPi
2
¿Por qué está el primer elemento en su salida 0? Si vas a admitir 0como una entrada válida, entonces la salida debería ser 1.
Peter Taylor
1
Algunos (incluido mi código) creen que hay cero secuencias vacías. Si 1 te hace sentir mejor, devuélvelo.
stand
2
AFAIK en cada contexto , supone que hay una y solo una secuencia vacía / objeto nulo / conjunto vacío, etc.
Bakuriu
1
@ Boothby, ¿acabas de llamar tonto a Knuth?
Peter Taylor

Respuestas:

8

GolfScript, 48 46 caracteres

:b,1,{)2\?){{.2$&!{.2$|@@}*.+.4b?<}do;;}+%}@/,

La versión más rápida ( prueba en línea ): se ejecuta bastante rápido, por ejemplo, n=8demora aproximadamente dos segundos. Y el enfoque elegido toma muy pocos personajes.

Esta versión también funciona con máscaras de bits. Construye la posible matriz de resultados de 1 en adelante, es decir, para n=3:

1: 000011        000110 001100 011000 110000
2: 010111 101011 101110        011101 110101 111010

Mientras que algunos resultados (como 000011) tienen dos posibles continuaciones, otros (es decir, 001100) no tienen ninguno y se eliminan de la matriz de resultados.

Explicación del código:

:b           # save the input into variable b for later use
,            # make the list 0..b-1 (the outer loop)
1,           # puts the list [0] on top of the stack - initially the only possible
             # combination
{)           # {...}@/ does the outer loop counting from i=1 to b
  2\?)       # computes the smalles possible bit mask m=2^i+1 with two bits set 
             # and distance of those equal to i (i.e. i=1: 11, i=2: 101, ...)
  {          # the next loop starts with this bitmask (prepended to code via
             # concatination {...}+
             # the loop itself iterates the top of the stack, i.e. at this point 
             # the result array                 
             # stack here contains item of result array (e.g. 00000011)
             # and bitmask (e.g. 00000101)
    {        # the inner-most loop tries all masks with the current item in the result set
      .2$&!  # do item and result set share not single bit? then - {...}*
      {
        .2$| # then generate the new entry by or-ing those two
        @@   # push it down on the stack (i.e. put working items to top)
      }*
      .+     # shift the bit mask left by one
      .4b?<  # if still in the range loop further
    }do;;    # removes the remainders of the loop (i.e. item processed and mask)
  }+%        # stack now contains the new result array
}@/
,            # length of result array, i.e. the number of Skolem sequences
Howard
fuente
Aceptar el más rápido de las soluciones vinculadas.
stand
6

Expresión J, 47 caracteres

 +/*/"1((=&{:+.2-#@])#;.2)\"1~.(i.!+:y)A.,~>:i.y

Ejemplo:

    y=:5
    +/*/"1((=&{:+.2-#@])#;.2)\"1~.(i.!+:y)A.,~>:i.y
10

Toma alrededor de 30 segundos y=:5en mi máquina.

El algoritmo es tan lento como puede ser:

  • ~.(i.!+:y)A.,~>:i.ygenera cada permutación de 1 2 .. y 1 2 .. yy elimina entradas duplicadas
  • ((=&{:+.2-#@])#;.2)\"1 calcula:
    • (...)\"1 para cada prefijo de cada fila:
      • #;.2 cuenta los elementos antes de cada aparición del último elemento
      • #@] cuenta la cantidad de cuentas (es decir, la cantidad de ocurrencias del último elemento)
      • =&{: determina la "igualdad" "del" "último elemento" s de la lista de conteo y de la lista original.
      • +.es un OR lógico. =&{:+.2-#@]lee "o los últimos elementos [de la lista de conteo y la lista original] son ​​iguales, o solo hay un elemento [en la lista de conteo] en lugar de dos".
  • */"1 se multiplica (AND lógico) sobre las filas de la tabla de condiciones, determinando qué permutaciones son secuencias de Skolem.
  • +/ suma los unos y los ceros juntos.
John Dvorak
fuente
6

GolfScript (46 caracteres)

:&1,\,{0,2@)?)2&*{2${1$^}%@+\2*}*;+}/{4&?(=},,

Esta es una expresión que toma datos en la pila. Para convertirlo en un programa completo que reciba información sobre stdin, anteponer~

Es bastante ineficiente: la mayoría de los ahorros que obtuve al jugar golf de 56 caracteres sin golf fueron expandiendo el rango de bucles de formas que no introducen resultados incorrectos pero hacen un cálculo de desperdicio.

El enfoque es el enmascaramiento bit a bit de los productos cartesianos. Por ejemplo (el uso de binario para las máscaras) para n=4el código no protegido calcularía el xor de cada elemento en el producto cartesiano [00000011 00000110 ... 11000000] x [00000101 00001010 ... 10100000] x ... x [00010001 ... 10001000]. Cualquier resultado con 8 bits solo se puede lograr con máscaras no superpuestas.

Para optimizar el tamaño en lugar de la velocidad, el código acumula productos parciales ( S1 u S1xS2 u S1xS2xS3 ...) y hace que cada producto sea de 2nelementos en lugar de solo los 2n-1-ique realmente pueden contribuir a una secuencia válida.

Velocidad

La versión de golf funciona n=5en 10 segundos en mi computadora y más de 5 minutos n=6. La versión original sin golf se calcula n=5en menos de un segundo y n=6en aproximadamente 1 minuto. Con un filtro simple en resultados intermedios, puede calcular n=8en 30 segundos. Lo he jugado a 66 caracteres (como programa - 65 caracteres como expresión) manteniendo los bucles lo más restringidos posible y filtrando colisiones intermedias:

~:&1,\,{0,\).2\?)2&*@-{.{[\].~^.@~+<{;}*}+3$%@+\2*}*;\;}/{4&?(=},,
Peter Taylor
fuente
Maldición. Justo cuando pensaba que mi solución 48char J era lo suficientemente buena como para publicarla.
John Dvorak
Maldición. Nuestro empate de 47 personajes no duró mucho. +1
John Dvorak
5

GolfScript, 49 caracteres

~:/..+?:d(,{d+/base(;:w;/,{.w?)w>1$?=},,/=},,/1=+

Espera el número nen STDIN. Este es el código de golf: no intente el código con nmás de 5.

Howard
fuente
Ouch, no mayor que 5?
stand de
@boothby Fue el primer intento directo. A menudo tenemos que tomar la decisión velocidad versus tamaño, y el código de golf es aproximadamente de tamaño. Es por eso que también agregué la versión rápida, que originalmente era mucho más larga pero ahora es aún más corta.
Howard
0

Sabio, 70

Esto es un poco más corto que mi original.

sum(1for i in DLXCPP([(i-1,j,i+j)for i in[1..n]for j in[n..3*n-i-1]]))

Cómo funciona:

Dada una matriz 0/1, el problema de cobertura exacta para esa matriz es encontrar un subconjunto de las filas que sumen (como enteros) al vector de todos. Por ejemplo,

11001
10100
01001
00011
00010

tiene una solución

10100
01001
00010

Mi enfoque favorito para los problemas es lanzarlos a un problema de cobertura exacto. Las secuencias de Skolem facilitan esto de manera eficiente. Hago un problema de cobertura exacto donde las soluciones están en biyección con secuencias de longitud de Skolem 2n. Por ejemplo, una fila del problema para n=6es

  a   |  b  
001000|001001000000 # S[b] = S[b+a+1] = a

donde un 1 en posición a < nsignifica que ase usa ese símbolo . Las posiciones restantes corresponden a ubicaciones reales en la secuencia. Una cubierta exacta corresponde a cada símbolo que se usa exactamente una vez, y cada ubicación se llena exactamente una vez. Por construcción, cualquier símbolo ken una ubicación está a kespacios de distancia de su compañero.

En Sage, DLXCPPes una implementación de "enlaces de baile": resuelve el problema exacto de la cubierta de una manera excepcionalmente elegante. Es uno de mis algoritmos favoritos, y estar en la superficie en Sage hace que la enumeración combinatoria sea una alegría.

boothby
fuente
Wow, enlace de baile. El uso len(list(...))ahorrará 4 caracteres.
Ray
@Ray Mi computadora simplemente moriría si calculara len(list(...))para n = 16. Y mataría por completo el tiempo de ejecución.
stand
Así es, porque convertir un generador en una lista cuesta mucha memoria.
Ray