1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.