A "rhyme scheme" is a string of letters
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)
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 <= 26, as well as a non-negative integer
0 <= i < B(N). Alternatively, you can use the range
1 <= i <= 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
B(N)). In particular, that means you cannot just iterate through all valid rhyme schemes of length
N until you've discard
Standard code-golf rules apply.
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).