Enumerate rhyme schemes A "rhyme scheme" is a string of letters a to z, such that the first occurrences of the characters are in ascending order (without gaps), starting from a. For example (with first occurrences marked):

abccdbebdcfa
^^^ ^ ^   ^


The number of rhyme schemes of length N is given by the Bell numbers B(N). (OEIS A000110)

The Challenge

Your task is to implement an enumeration of these rhyme schemes, i.e. a bijective mapping from integers to rhyme schemes. You're given a positive integer N &lt;= 26, as well as a non-negative integer 0 &lt;= i &lt; B(N). Alternatively, you can use the range 1 &lt;= i &lt;= B(N). You should output a rhyme scheme of length N, such that every i yields a different string.

You may write a program or function, taking input via STDIN (or closest alternative), command-line argument or function argument and outputting the result via STDOUT (or closest alternative), function return value or function (out) parameter.

You may use either lower or upper case letters (consistently).

Your code must be able to handle any valid input in reasonable amount of time (e.g. not more than a few hours for N = 26, worst case i). This should allow solutions that scale exponentially with N (for small bases), even in slow languages but prohibit solutions that scale linearly with i (i.e. B(N)). In particular, that means you cannot just iterate through all valid rhyme schemes of length N until you've discard i schemes.

Standard code-golf rules apply.

Examples

The exact assignment of the i to schemes (i.e. the order of the schemes for a given N) is up to you. But say you chose lexicographical ordering, your solution should correspond to the following table (with - denoting invalid input):

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


Here is a short CJam script which generates all valid rhyme schemes for any given length (but don't try more than 10 or you'll wait a while).

Related Challenges


Translate a Glypho program
Check if words are isomorphs
Python 2, 153

u=[1]*999;i=60;exec&quot;u[i]=i%30*u[i-30]+u[i-29];i+=1;&quot;*900
def x(l,n,a=0):m=u[30*l+a];c=n&gt;=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&lt;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'.