Gerar sequências Skolem

Sequências de Skolem

Uma sequência de Skolem é uma sequência de 2nnúmeros em que todo número ientre 1e nocorre exatamente duas vezes, e a distância entre as duas ocorrências ié exatamente de ietapas. Aqui estão alguns exemplos de sequências 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

As seguintes sequências não são sequências 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

Escreva um programa, função ou expressão para contar o número de todas as seqüências de Skolem de um determinado comprimento. Mais explicitamente, sua entrada é um número inteiro ne sua saída é o número de sequências de comprimento de Skolem 2n. Esta sequência tem uma entrada OEIS . Para n = 0, você pode retornar 0ou 1. Os primeiros valores, começando por 0, são

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

Regras e pontuação

Isso é código de golfe. O formato de saída é relaxado dentro do razoável.

GolfScript, 48 46 caracteres

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

A versão mais rápida ( experimente online ) - corre razoavelmente rápido, por exemplo, n=8leva cerca de dois segundos. E a abordagem escolhida tem realmente poucos caracteres.

Esta versão também funciona com máscaras de bits. Ele constrói a matriz de resultados possíveis de 1 para cima, ou seja, para n=3:

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

Enquanto alguns resultados (como 000011) têm duas continuações possíveis, outros (por exemplo, 001100) não têm nenhum e são removidos da matriz de resultados.

Explicação do 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

Expressão J, 47 caracteres

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

Exemplo:

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

Demora cerca de 30 segundos y=:5na minha máquina.

o algoritmo é o mais lento possível:

• ~.(i.!+:y)A.,~>:i.ygera toda permutação 1 2 .. y 1 2 .. ye remove entradas duplicadas
• ((=&{:+.2-#@])#;.2)\"1 calcula:
  • (...)\"1 para cada prefixo de cada linha:
    • #;.2 conta os elementos antes de cada ocorrência do último elemento
    • #@] conta o número de contagens (ou seja, o número de ocorrências do último elemento)
    • =&{: determina a "igualdade" "de" "último elemento" s da lista de contagem e da lista original.
    • +.é um OR lógico. =&{:+.2-#@]lê "os últimos elementos [da lista de contagens e da lista original] são iguais ou existe apenas um elemento [na lista de contagens] em vez de dois".
• */"1 multiplica (AND lógico) nas linhas da tabela de condições, determinando quais permutações são sequências de Skolem.
• +/ soma esses e zeros juntos.

GolfScript (46 caracteres)

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

Esta é uma expressão que recebe entrada na pilha. Para transformá-lo em um programa completo, com entrada no stdin, acrescente~

É bastante ineficiente - a maior parte das economias que fiz ao reduzir para 56 caracteres sem golfe foi expandindo o leque de loops de maneiras que não introduzem resultados incorretos, mas fazem o cálculo de resíduos.

A abordagem é o mascaramento bit a bit de produtos cartesianos. Por exemplo, (usando binário para as máscaras) para n=4o código não armazenado, calcularia o xor de cada elemento no produto cartesiano [00000011 00000110 ... 11000000] x [00000101 00001010 ... 10100000] x ... x [00010001 ... 10001000]. Qualquer resultado com 8 bits só poderia ser alcançado por máscaras sem sobreposição.

Para otimizar o tamanho em vez da velocidade, o código acumula produtos parciais ( S1 u S1xS2 u S1xS2xS3 ...) e faz com que cada produto seja constituído por 2nelementos, e não apenas pelo 2n-1-ique pode realmente contribuir para uma sequência válida.

Rapidez

A versão para golfe dura n=510 segundos no meu computador e mais de 5 minutos para n=6. A versão original não gasta calcula n=5em menos de um segundo e n=6em cerca de 1 minuto. Com um filtro simples em resultados intermediários, ele pode calcular n=8em 30 segundos. Joguei o jogo em 66 caracteres (como um programa - 65 caracteres em uma expressão), mantendo os loops o mais restrito possível e filtrando as colisões intermediárias:

~:&1,\,{0,\).2\?)2&*@-{.{[\].~^.@~+<{;}*}+3$%@+\2*}*;\;}/{4&?(=},,

GolfScript, 49 caracteres

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

Espera o número nem STDIN. Isso é código-golfe - não tente o código com nmais de 5.

Sálvia, 70

Isso é um pouco menor que o meu original.

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

Como funciona:

Dada uma matriz 0/1, o problema exato de cobertura dessa matriz é encontrar um subconjunto das linhas que somam (como números inteiros) ao vetor all-ones. Por exemplo,

11001
10100
01001
00011
00010

tem uma solução

10100
01001
00010

Minha abordagem favorita para os problemas é convertê-los em um problema exato de capa. As sequências de Skolem facilitam isso com eficiência. Faço um problema exato de cobertura em que as soluções estão em desuso com as sequências de comprimento Skolem 2n. Por exemplo, uma linha do problema para n=6é

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

onde um 1 na posição a < nsignifica que o símbolo aé usado. As posições restantes correspondem aos locais reais na sequência. Uma capa exata corresponde a cada símbolo sendo usado exatamente uma vez e a cada local sendo preenchido exatamente uma vez. Por construção, qualquer símbolo kem um local está a kespaços de distância de seu parceiro.

No Sage, DLXCPPé uma implementação de "links de dança" - resolve o problema exato da capa de uma maneira excepcionalmente elegante. É um dos meus algoritmos favoritos de todos os tempos, e estar na superfície do Sage torna uma enumeração combinatória uma alegria.