Enumerate rhyme schemes

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)

It uses alphabetical order and 0-based indexing.

Let l denote the length of a suffix of the letters and a denote the number of distinct letters that were used in the preceding part. Then a function p(l,a) that calculates the number of ways to select the remaining letters could be 40 bytes:

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

However, this is too slow for the challenge, so instead the necessary values are precalculated and stored in the u array. At each stage of the calculation, if the next letter is the one of the a already used, the n = k * p(l - 1, a) + n' where k is the 0-indexed letter of the alphabet and n' is the value of n for the next function call, which contains the information about the remaining letters. If a new letter is used, then n = a * p(l - 1, a) + n'.

Haskell (GHC 7.10), 150 bytes

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

The operator n # i computes the ith (zero-indexed) rhyme scheme of length n. It runs in O(n²) (big-integer) operations, taking advantage of Haskell’s lazy infinite lists for automatic memoization. Sample runs:

*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"]

(If the maximum N were 25 instead of 26, the .fromEnum could be removed, because B(25) fits in a 64-bit Int.)

Perl 257 + 1 (-p flag) = 258

Perl 182 + 10 (-pMbignum flags) = 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}

Thanks to dev-nul for saving many bytes! I've now rewritten it based on what I learnt from doing the CJam version.

Calculates the rhyme in ascending alphabetical order, 0 indexed.

Two parts: Part 1 is 128 90 bytes and calculates a matrix for Part 2. Part 2 is 129 92 bytes and does some simple maths to calculate each letter. If I could get rid of the matrix and replace it with two simple numbers, I could calculate a single path through the matrix for each number and save a lot of bytes! Apparently, that idea doesn't work!

Unfortunately, it doesn't output the right rhymes for values of i higher than 9007199254740992, but it works beautifully for low values! I've added the Bignum library at a cost of 11 bytes. It's run from the command line with perl -pMbignum bell-rhyme.pl. -pMbignum  = 10 bytes. It's also very fast for any input value.