permutation-tree

Permutation Tree

The Permutation Tree is a data structure that creates all the numeric substrings of a number. If we define the term "numeric substring" to be all those numbers that are permutations of adjacent digits of a given number, then the resulting set S of numeric substrings of the number 123 is given by S = {{1}, {2}, {3}, {12}, {23}, {123}}. This is the same notion as the mathematical construct known as a subset, except for two elements that are not included: {13}, and {}, the empty set. These two elements are excluded from the Permutation Tree because they are not permutations of adjacent digits in the number.

This data structure takes a number as input, and makes the resulting set S. The data are stored in a binary search tree. For example, if the number 123456789 is given as input, the resulting structure looks like:

                9
               / \
              8   89
             /   /  \
            7   78   789
           /   /    /   \
          6   67   678   6789
         /   /    /     /    \
        5   56   567   5678   56789
       /   /    /     /      /     \
      4   45   456   4567   45678   456789
     /   /    /     /      /       /      \
    3   34   345   3456   34567   345678   3456789
   /   /    /     /      /       /        /       \
  2   23   234   2345   23456   234567   2345678   23456789
 /   /    /     /      /       /        /         /        \
1   12   123   1234   12345   123456   1234567   12345678   123456789

Notice that the first digit in the number is the root, and the number itself is the element in the bottom-right of the tree. If the digits of the number are strictly increasing from left to right, then this will be the shape of the resulting tree. Otherwise, the tree will not be as full, and could potentially be quite degenerate, as this data structure is not self-balancing. For example, the Permutation Tree for 192837 is:

      7
     / \
    3   8
   /     \
  2       9
 /         \
1           37
           /  \
          28   83
         /      \
        19       92
                  \
                   837
                  /   \
                 283   928
                /       \
               192       2837
                        /    \
                       1928   9283
                               \
                                192837

The resulting tree is quite sparse, and you can begin to see how the order of the digits affects the outcome. The worst case scenario is a number whose digits are strictly decreasing from left to right. For example, input such as 54321 will effectively form an array of numbers, increasing from smallest to largest:

1
 \
  2
   \
    3
     \
      4
       \
        5
         \
          21
           \
            32
             \
              43
               \
                54
                 \
                  321
                   \
                    432
                     \
                      543
                       \
                        4321
                         \
                          5432
                           \
                            54321

This is because of the way the data structure breaks the number apart and finds the permutations of sequences. Thus, in the best case, search time for the structure is Ω(log₂(n)), and in the worst case it is O(n).