„Schemat rymów” to ciąg liter ado z, dzięki czemu pierwsze wystąpienia znaków są w porządku rosnącym (bez przerw), zaczynając od a. Na przykład (z zaznaczonymi pierwszymi wystąpieniami):

abccdbebdcfa
^^^ ^ ^   ^

Liczba schematów rymów długości Njest podana przez liczby Bell B(N) . ( OEIS A000110 )

Wyzwanie

Twoim zadaniem jest zaimplementowanie wyliczenia tych schematów rymów, tj. Bijective mapping od liczb całkowitych do schematów rymów. Otrzymujesz dodatnią liczbę całkowitą N <= 26, a także nieujemną liczbę całkowitą 0 <= i < B(N). Alternatywnie możesz użyć zakresu 1 <= i <= B(N). Powinieneś wypisać schemat rymów długości N, tak że każdy idaje inny ciąg znaków.

Możesz napisać program lub funkcję, pobierając dane wejściowe przez STDIN (lub najbliższą alternatywę), argument wiersza poleceń lub argument funkcji i wypisując wynik przez STDOUT (lub najbliższą alternatywę), wartość zwracaną funkcji lub parametr funkcji (wyjściowej).

Możesz używać zarówno małych jak i wielkich liter (konsekwentnie).

Twój kod musi być w stanie obsłużyć każdy ważny wkład w rozsądnym czasie (np nie więcej niż kilka godzin za N = 26, najgorszym przypadku i). Powinno to pozwolić na rozwiązania skalowane wykładniczo za pomocą N(dla małych zasad), nawet w wolnych językach, ale zabraniać rozwiązań skalowanych liniowo za pomocą i(tj B(N).). W szczególności oznacza to, że nie możesz po prostu powtarzać wszystkich prawidłowych schematów rymów, Ndopóki nie odrzucisz ischematów.

Obowiązują standardowe zasady gry w golfa .

Przykłady

Dokładne przypisanie ido schematów (tj. Kolejność schematów dla danego N) zależy od Ciebie. Ale powiedzmy, że wybrałeś porządek leksykograficzny, twoje rozwiązanie powinno odpowiadać poniższej tabeli (z -oznaczeniem nieprawidłowych danych wejściowych):

N\i 1    2    3    4    5    6    7    8    9    10   11   12   13   14   15
1   a    -    -    -    -    -    -    -    -    -    -    -    -    -    -
2   aa   ab   -    -    -    -    -    -    -    -    -    -    -    -    -
3   aaa  aab  aba  abb  abc  -    -    -    -    -    -    -    -    -    -
4   aaaa aaab aaba aabb aabc abaa abab abac abba abbb abbc abca abcb abcc abcd

Oto krótki skrypt CJam, który generuje wszystkie prawidłowe schematy wierszy dla dowolnej długości (ale nie próbuj więcej niż 10, bo poczekaj chwilę).

Powiązane wyzwania

• Przetłumacz program Glypho
• Sprawdź, czy słowa są izomorfami

CJam, 68 66 bajtów

r~:W)1a*{__(;\);_,,.*.+}W(*r~{X@\=_2$\/:CX<!{X:C):X;}&C*-C'a+o}W*;

Wypróbuj online.

To mój pierwszy program CJam. Zaczęło życie jako port mojego rozwiązania Perla i początkowo miało ponad 130 bajtów. Dalsze sugestie dotyczące gry w golfa są mile widziane.

Podobnie jak w moim programie Perl, składa się on z dwóch części.

Part 1:
r~:W                                         | Read the first input (n) and store it in W
    )1a*                                     | Create an array of n+1 1s
        {              }W(*                  | Repeat n-1 times:
         __                                  | Duplicate array twice
           (;\);                             | Remove first element of 1st array. Swap
                                             | arrays. Remove last element of 2nd array
                _,,                          | Duplicate array. Count items. Create range
                   .*.+                      | Multiply arrays. Add 1st array to result

Part 2:
r~                                           | Read the second input (i)
   {                                  }W*    | Repeat n times:
    X@                                       | Push y (initially 1). Bring item 2 (last array) to top
     \=                                      | Swap top two items. Pop array[y] (v)
       _2$                                   | Duplicate v. Copy item 2 (i) to top
          \/:CX                              | Swap i & v. i/v. Store in C (c). Push y
               <!{       }&                  | If !(i/v < c):
                  X:C):X;                    | c = y. ++y (store in X)
                           C*-C'a+o          | i -= c * v. Push y. Push "a". Add c. Print
                                         ;   | Discard top item (integer 0)

Debugować tablic stworzonych przez Part 1 Dodaj ]_`o~pomiędzy Parts 1 & 2. Jeżeli n jest 5, macierze będzie wyglądać następująco: [[1 1 1 1 1 1] [1 2 3 4 5] [2 5 10 17] [5 15 37] [15 52]]. Wskaźniki 0 w każdej tablicy nie są używane, po prostu ułatwiają to, że nie trzeba obliczać przesunięć. Tablice są obliczane w następujący sposób:

[2 5 10 17] [2 5 10 17] [2 5 10 17]        | Duplicate twice
[2 5 10 17] [2 5 10 17] [5 10 17]          | Discard first item of array
[2 5 10 17] [5 10 17] [2 5 10 17]          | Swap last two arrays
[2 5 10 17] [5 10 17] [2 5 10]             | Discard last item of array
[2 5 10 17] [5 10 17] [2 5 10] [2 5 10]    | Duplicate array
[2 5 10 17] [5 10 17] [2 5 10] 3           | Count items in array
[2 5 10 17] [5 10 17] [2 5 10] [0 1 2]     | Integer to range 0 - n-1
[2 5 10 17] [5 10 17] [0 5 20]             | Multiply arrays [2*0 5*1 10*2]
[2 5 10 17] [5 15 37]                      | Add arrays [5+0 10+5 17+20]

Przechowuje kopię starej tablicy podczas obliczania następnej. Tablice są odczytywane i odrzucane w odwrotnej kolejności przez część 2.

Python 2, 153

u=[1]*999;i=60;exec"u[i]=i%30*u[i-30]+u[i-29];i+=1;"*900
def x(l,n,a=0):m=u[30*l+a];c=n>=a*m;return'.'*l and chr(65+min(n/m,a))+x(l-1,[n%m,n-m*a][c],a+c)

Wykorzystuje porządek alfabetyczny i indeksowanie oparte na 0.

Niech loznacza długość sufiksu liter i aliczbę różnych liter użytych w poprzedniej części. Następnie funkcja, p(l,a)która oblicza liczbę sposobów wyboru pozostałych liter, może mieć 40 bajtów:

p=lambda l,a:l<1or a*p(l-1,a)+p(l-1,a+1)

Jest to jednak zbyt wolne dla wyzwania, więc zamiast tego niezbędne wartości są wstępnie obliczane i zapisywane w utablicy. Na każdym etapie obliczeń, jeśli następną literą jest ajuż używana litera , n = k * p (l - 1, a) + n ', gdzie k jest literą alfabetu o indeksie 0, a n' wynosi wartość nnastępnego wywołania funkcji, która zawiera informacje o pozostałych literach. Jeśli używana jest nowa litera, to n = a * p (l - 1, a) + n ' .

Haskell (GHC 7.10), 150 bajtów

s=(1,\_->[]):s
k!((y,b):l@((x,a):_))|let h i|i<x=k:a i|(p,q)<-divMod(i-x)y=p:b q=(x+k*y,h):(k+1)!l
n#i=(['a'..]!!).fromEnum<$>snd(iterate(0!)s!!n!!0)i

Operator n # ioblicza ischemat długości rymu th (indeksowany od zera) n. Działa w operacjach O (n²) (big-integer), wykorzystując leniwe, nieskończone listy Haskella do automatycznego zapamiętywania. Przykładowe przebiegi:

*Main> 26 # 0
"abcdefghijklmnopqrstuvwxyz"
*Main> 26 # 1
"abcdefghijklmnopqrstuvwxya"
*Main> 26 # 2
"abcdefghijklmnopqrstuvwxyb"
*Main> 26 # 49631246523618756271
"aaaaaaaaaaaaaaaaaaaaaaaabb"
*Main> 26 # 49631246523618756272
"aaaaaaaaaaaaaaaaaaaaaaaaab"
*Main> 26 # 49631246523618756273
"aaaaaaaaaaaaaaaaaaaaaaaaaa"
*Main> [1 # i | i <- [0..0]]
["a"]
*Main> [2 # i | i <- [0..1]]
["ab","aa"]
*Main> [3 # i | i <- [0..4]]
["abc","aba","abb","aab","aaa"]
*Main> [4 # i | i <- [0..14]]
["abcd","abca","abcb","abcc","abac","abaa","abab","abbc","abba","abbb","aabc","aaba","aabb","aaab","aaaa"]

(Jeśli maksymalna N to 25 zamiast 26, .fromEnummożna je usunąć, ponieważ B (25) mieści się w wersji 64-bitowej Int).

Perl 257 + 1 (flaga -p) = 258

Perl 182 + 10 (flagi -pMbignum) = 192

($n,$i)=split;@m=[@a=(1)x($n+1)];while($a[2]){push@m,[@a=map{$a[$_]*$_+$a[$_+1]}0..$#a-1]}$_='';$y=1;while($w=pop@m){$c=int($i/($v=$$w[$y]));$c=$y++if($c>=$y);$i-=$c*$v;$_.=chr$c+65}

Dzięki dev-nul za uratowanie wielu bajtów! Teraz przepisałem go na podstawie tego, czego nauczyłem się podczas tworzenia wersji CJam.

Oblicza rym w kolejności alfabetycznej, 0 indeksowane.

Dwie części: część 1 ma 128 90 bajtów i oblicza macierz dla części 2. Część 2 ma 129 92 bajtów i wykonuje kilka prostych obliczeń matematycznych w celu obliczenia każdej litery. Gdybym mógł pozbyć się macierzy i zastąpić ją dwoma prostymi liczbami, mógłbym obliczyć jedną ścieżkę przez macierz dla każdej liczby i zaoszczędzić dużo bajtów! Najwyraźniej ten pomysł nie działa!

Niestety nie wyświetla odpowiednich rymów dla wartości iwyższych niż 9007199254740992, ale działa pięknie dla niskich wartości! Dodałem bibliotekę Bignum kosztem 11 bajtów. Jest uruchamiany z wiersza poleceń za pomocą perl -pMbignum bell-rhyme.pl. -pMbignum = 10 bajtów. Jest również bardzo szybki dla każdej wartości wejściowej.

Oracle SQL 11.2, 412 284 283 bajtów

WITH a AS(SELECT CHR(96+LEVEL)d,LEVEL b FROM DUAL CONNECT BY LEVEL<=:i),v(s,c,n)AS(SELECT d,1,1 FROM a WHERE b=1 UNION ALL SELECT s||d,b,LENGTH(REGEXP_REPLACE(s||d,'([a-z])\1+','\1'))FROM v,a WHERE(b<=n OR b=c+1)AND LENGTH(s)<:n)SELECT s FROM v WHERE:n=LENGTH(s)AND:i<=:n ORDER BY 1;

Niestety osiąga długość do 8. Każda większa wartość powoduje: ORA-01489: wynik konkatenacji łańcucha jest zbyt długi

Nie grał w golfa

WITH a AS(SELECT CHR(96+LEVEL)d,LEVEL b FROM DUAL CONNECT BY LEVEL<=:i),
v(s,c,n) AS
(
  SELECT d,1,1 FROM a WHERE b=1
  UNION ALL
  SELECT s||d,b,LENGTH(REGEXP_REPLACE(s||d,'([a-z])\1+','\1')) 
  FROM v,a 
  WHERE (b<=n OR b=c+1) AND LENGTH(s)<:n
)
SELECT s FROM v WHERE LENGTH(s)=:n AND :i<=:n ORDER BY 1;

Widok generuje: i litery w kolumnie a i ich wartość w b.

Widok rekurencyjny v przyjmuje ciąg budowany jako parametr v, wartość ostatniej litery użytej w c oraz wartość największej litery użytej w n. Parametr n jest równy długości łańcucha bez zduplikowanej litery, to jest to, dla czego służy wyrażenie regularne.

Litera jest ważna, jeśli jej wartość wynosi <= wartość największej już użytej litery lub jest to kolejna litera, która zostanie użyta.

Jakoś kwerenda potrzebuje części LENGTH (s) <: n do uruchomienia, brakuje mi czegoś w sposobie działania kwerendy.

Główny WYBÓR zajmuje się odfiltrowaniem nieprawidłowych danych wejściowych i krótszych ciągów znaków zbudowanych przed osiągnięciem docelowej długości.

Wersja 412 bajtów

WITH a AS(SELECT * FROM(SELECT d,b,ROW_NUMBER()OVER(PARTITION BY b ORDER BY d)l FROM(SELECT CHR(64+DECODE(MOD(LEVEL,:i),0,:i,MOD(LEVEL,:i)))d,CEIL(LEVEL/:i)b FROM DUAL CONNECT BY LEVEL<=:i*:n))WHERE l<=b),v(s,c,p)AS(SELECT d,1,l FROM a WHERE b=1 UNION ALL SELECT s||d,c+1,l FROM v,a WHERE c+1=b AND(l<=LENGTH(REGEXP_REPLACE(s,'([A-Z])\1+','\1'))OR l=p+1))SELECT s FROM v WHERE LENGTH(s)=:n AND :i<=:n ORDER BY 1;

Nie próbuj kwerendy 412 bajtów z 26. To przełącza bazę danych w tryb zastrzeżony, przynajmniej w mojej wersji xe działającej w kontenerze dokera na Macbooku. Mógłbym przymierzyć exadata w pracy, ale niestety nadal muszę zarabiać na życie.

Mathematica, 136 bajtów

(For[j=2^#-1;t=#2,c=1;m=0;x=t;r=If[#>0,++m,c*=m;d=x~Mod~m+1;x=⌊x/m⌋;d]&/@j~IntegerDigits~2;;c<=t,t-=c;--j];FromCharacterCode[r+64])&

Dla kompletności, oto moja referencyjna implementacja gry w golfa. W przeciwieństwie do istniejących odpowiedzi, nie działa to w czasie wielomianowym (jest wykładniczy w Nprzypadku podstawy 2), ale spełnia ograniczenie czasowe (najgorszy przypadek trwałby jeszcze za pół godziny).

Chodzi o to:

• Dla każdego schematu rymów możemy zidentyfikować pozycje, w których zwiększa się jak dotąd maksymalny znak:

  ABCDEFGHDIJDEKBBIJEIKHDFII
  ^^^^^^^^ ^^  ^
  

  Możemy traktować te oznaczenia jako liczbę binarną, co ułatwia iterację wszystkich takich struktur. Musimy iterować od 2 ^n-1 do 2 ⁿ (lub na odwrót), skąd pochodzi wykładnicza złożoność czasu.

• Dla każdej takiej struktury łatwo jest określić, ile jest takich ciągów: można dowolnie wybierać tylko odstępy między oznaczeniami, a maksymalna liczba przed odstępem mówi nam, ile różnych znaków jest poprawnych w każdej pozycji. To jest prosty produkt. Jeśli liczba ta jest mniejsza niż i, odejmujemy ją i. W przeciwnym razie znaleźliśmy strukturę żądanego schematu wierszyków.
• Aby wyliczyć schematy w danej strukturze, po prostu reprezentujemy i(lub to, co z niej pozostanie) jako liczbę o mieszanej podstawie, gdzie wagi cyfr są określone przez liczbę dozwolonych znaków na pozostałych pozycjach.

Zastanawiam się, czy pozwoliłoby to na krótsze rozwiązanie w niektórych innych przesłanych językach, ponieważ nie wymaga to żadnej zapamiętywania ani wstępnego obliczenia.