Lehmer codes can be used to encode each possible permutation of a sequence of n numbers. Often the main goal is just to map a range of numbers from 1 to x to the possible permutations of a sequence of numbers from 1 to n. An example to visualize this goal would be:
n := 3, x := 6 [1, 2, 3] = 1 [1, 3, 2] = 2 [2, 1, 3] = 3 [2, 3, 1] = 4 [3, 1, 2] = 5 [3, 2, 1] = 6
Instead of encoding each possible permutation of a sequence of n numbers, I want to encode each possible b-tree which can be created from a sequence of n numbers. When creating a b-tree from a sequence of n numbers, the possible solutions can be branched differently due to the order of (additional) insertions, deletions or reorganizations.
Example: Create a b-tree from the sequence of numbers from 1 to n := 5. The b-tree's (non-root) nodes must have at least 2 and at the maximum 4 children. With this conditions these b-trees would all be valid:
3 2 4 2|4 / \ / \ / \ / | \ 1|2 4|5 1 3|4|5 1|2|3 5 1 3 5
I could write an algorithm to generate every possible b-tree and then map them to a list of numbers. But that does not work very efficient for n getting bigger because obviously memory is a limitation here. So what I'm looking for is something like the above described Lehmer code for b-tree possibilities instead of permutations.
I would also appriciate a solution for this problem but with binary trees or other tree data structures instead of b-trees because I didn't find anything at all regarding to encoding trees like that and a first approach is always nice to work with.
If you think this question would be more appropriate on Mathematics Stack Exchange, let me know as well.