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.



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.