Generuj sekwencje Skolem

Sekwencje Skolem

Sekwencja Skolem jest ciągiem 2nliczb, gdzie każda liczba ipomiędzy 1i nzachodzi dokładnie dwa razy, a odległość między dwoma wystąpieniami ijest dokładnie ikroki. Oto kilka przykładów sekwencji 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

Następujące sekwencje nie są sekwencjami 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)

Cel

Napisz program, funkcję lub wyrażenie, aby policzyć liczbę wszystkich sekwencji Skolem o danej długości. Mówiąc ściślej, dane wejściowe są liczbami całkowitymi n, a dane wyjściowe to liczba sekwencji Skolem o długości 2n. Ta sekwencja ma wpis OEIS . Dla n = 0, można zwrócić albo 0albo 1. Pierwsze kilka wartości, zaczynając od 0, to

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

Zasady i punktacja

To jest kod golfowy. Format wyjściowy jest luźny w granicach rozsądku.

GolfScript, 48 46 znaków

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

Wersja szybsza ( spróbuj online ) - działa dość szybko, np. n=8Zajmuje około dwóch sekund. Wybrane podejście zajmuje naprawdę niewiele postaci.

Ta wersja działa również z maskami bitowymi. Buduje możliwą tablicę wyników od 1 w górę, tj. Dla n=3:

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

Podczas gdy niektóre wyniki (jak 000011) mają dwie możliwe kontynuacje, inne (tj. 001100) nie mają żadnych i są usuwane z tablicy wyników.

Objaśnienie kodu:

: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

Wyrażenie J, 47 znaków

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

Przykład:

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

Trwa około 30 sekund y=:5na moim komputerze.

algorytm jest tak wolny, jak to tylko możliwe:

• ~.(i.!+:y)A.,~>:i.ygeneruje każdą permutację 1 2 .. y 1 2 .. yi usuwa zduplikowane wpisy
• ((=&{:+.2-#@])#;.2)\"1 oblicza:
  • (...)\"1 dla każdego prefiksu każdego wiersza:
    • #;.2 liczy elementy przed każdym wystąpieniem ostatniego elementu
    • #@] zlicza liczbę zliczeń (tj. liczbę wystąpień ostatniego elementu)
    • =&{: określa „równość” „” ostatniego elementu ”listy liczników i listy oryginalnej.
    • +.jest logicznym OR. =&{:+.2-#@]czyta „albo ostatnie elementy [listy zliczeń i oryginalnej listy] są równe, lub jest tylko jeden element [na liście zliczeń] zamiast dwóch”.
• */"1 mnoży (logiczne AND) przez wiersze tabeli warunków, określając, które permutacje są sekwencjami Skolema.
• +/ sumuje jedynki i zera razem.

GolfScript (46 znaków)

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

To wyrażenie pobiera dane wejściowe ze stosu. Aby przekształcić go w pełny program, który pobiera dane wejściowe na standardowe wejście, dodaj~

Jest to dość nieefektywne - większość oszczędności, które poczyniłem, grając w golfa z 56 znaków bez golfa, polegało na rozszerzeniu zakresu pętli w sposób, który nie wprowadza niepoprawnych wyników, ale oblicza straty.

Podejście polega na bitowym maskowaniu produktów kartezjańskich. Np. (Użycie binarne dla masek) dla n=4kodu bez golfa obliczałby xor każdego elementu w produkcie kartezjańskim [00000011 00000110 ... 11000000] x [00000101 00001010 ... 10100000] x ... x [00010001 ... 10001000]. Dowolny wynik z 8 bitami można osiągnąć tylko za pomocą nienakładających się masek.

Aby zoptymalizować rozmiar, a nie szybkość, kod gromadzi produkty cząstkowe ( S1 u S1xS2 u S1xS2xS3 ...) i sprawia, że ​​każdy produkt składa się z 2nelementów, a nie tylko z tych, 2n-1-iktóre mogą faktycznie przyczynić się do prawidłowej sekwencji.

Prędkość

Gra w golfa działa n=5na moim komputerze za 10 sekund i przez ponad 5 minut n=6. Oryginalna wersja bez golfa oblicza się n=5w niecałą sekundę i n=6około 1 minuty. Dzięki prostemu filtrowi wyników pośrednich można go obliczyć n=8w 30 sekund. Grałem w golfa do 66 znaków (jako program - 65 znaków jako wyrażenie), jednocześnie utrzymując pętle tak ograniczone, jak to możliwe i filtrując kolizje pośrednie:

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

GolfScript, 49 znaków

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

Oczekuje liczby nna STDIN. To jest golf golfowy - nie próbuj kodu z wartością nwiększą niż 5.

Sage, 70

To jest trochę krótsze niż mój oryginał.

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

Jak to działa:

Biorąc pod uwagę macierz 0/1, dokładnym problemem pokrycia dla tej macierzy jest znalezienie podzestawu wierszy, który sumuje (jako liczby całkowite) do wektora wszystkich. Na przykład,

11001
10100
01001
00011
00010

ma rozwiązanie

10100
01001
00010

Moje ulubione podejście do problemów polega na rzuceniu ich na dokładny problem z okładką. Sekwencje Skolem skutecznie to ułatwiają. Dokładnie opisuję problem, w którym rozwiązania są bijection z sekwencjami długości Skolema 2n. Na przykład wierszem problemu n=6jest

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

gdzie 1 w pozycji a < noznacza, że aużywany jest symbol . Pozostałe pozycje odpowiadają faktycznym lokalizacjom w sekwencji. Dokładna okładka odpowiada każdemu symbolowi używanemu dokładnie raz, a każda lokalizacja jest wypełniana dokładnie raz. Z konstrukcji każdy symbol kw lokalizacji jest koddalony od partnera.

W Sage DLXCPPjest implementacją „tańczących linków” - rozwiązuje dokładnie problem z okładką w wyjątkowo wdzięczny sposób. Jest to jeden z moich ulubionych algorytmów w historii, a bycie na powierzchni w Sage sprawia, że ​​kombinatoryczne wyliczanie jest radością.