Найти количество перестановок заданной последовательности целых чисел, которые дают одно и то же двоичное дерево поиска

Question

Дан массив целых чисел arr = [5, 6, 1]. Когда мы создаем BST с этим входом в том же порядке, у нас будет «5» в качестве корня, «6» в качестве правого дочернего элемента и «1» в качестве левого дочернего элемента.

Теперь, если наш вход будет изменен на [5,1,6], наша структура BST останется идентичной.

Итак, учитывая массив целых чисел, как найти число различных перестановок входного массива, которые приводят к тому же BST, что и BST, сформированный в исходном порядке массива?

Answer 1

Ваш вопрос эквивалентен вопросу подсчета количества топологических упорядочений для данного BST.

Например, для BST

  10
 /  \
5   20
 \7 | \
    15 30

набор топологических упорядочений можно посчитать вручную следующим образом: 10 начинается при каждом упорядочении. Число топологических упорядочений для поддерева, начинающегося с 20, равно двум: (20, 15, 30) и (20, 30, 15). Поддерево, начинающееся с 5, имеет только один порядок: (5, 7). Эти две последовательности могут чередоваться произвольным образом, что приводит к 2 × 10 чередованиям, в результате чего получается двадцать входов, которые вырабатывают один и тот же BST. Первые 10 перечислены ниже для случая (20, 15, 30):

 10 5 7 20 15 30
 10 5 20 7 15 30
 10 5 20 15 7 30
 10 5 20 15 30 7
 10 20 5 7 15 30
 10 20 5 15 7 30
 10 20 5 15 30 7
 10 20 15 5 7 30
 10 20 15 5 30 7
 10 20 15 30 5 7

Случай (20, 30, 15) аналогичен - вы можете проверить, что любой из следующих входов выдает одинаковый BST.

Этот пример также предоставляет рекурсивное правило для расчета количества заказов. Для листа число равно 1. Для неконечного узла с одним потомком число равно количеству топологических упорядочений для потомка. Для неконечного узла с двумя дочерними элементами с размерами поддерева | L | и | R |, оба имеют порядки l и r, соответственно, число равно

  l x r x INT(|L|, |R|)

Где INT - число возможных перемежений | L | и | R | элементы. Это можно легко вычислить как (| L | + | R |)! / (| L |! X | R |!). Для приведенного выше примера мы получаем следующие рекурсивные вычисления:

  Ord(15) = 1
  Ord(30) = 1
  Ord(20) = 1 x 1 x INT(1, 1) = 2  ; INT(1, 1) = 2! / 1 = 2
  Ord(7) = 1
  Ord(5) = 1
  Ord(10) = 1 x 2 x INT(2, 3) = 2 x 5! / (2! x 3!) = 2 x 120 / 12 = 2 x 10 = 20

Это решает проблему.

Примечание: это решение предполагает, что все узлы в BST имеют разные ключи.

Answer 2

Спасибо за объяснение antti.huima! Это помогло мне понять. Вот немного C ++:

#include <vector>
#include <iostream>

using namespace std;

int factorial(int x) {
  return (x <= 1) ? 1 : x * factorial(x - 1);
}

int f(int a, int b) {
  return factorial(a + b) / (factorial(a) * factorial(b));
}

template <typename T>
int n(vector<T>& P) {
  if (P.size() <= 1) return 1;
  vector<T> L, R;
  for (int i = 1; i < P.size(); i++) {
    if (P[i] < P[0])
      L.push_back(P[i]);
    else
      R.push_back(P[i]);
  }
  return n(L) * n(R) * f(L.size(), R.size());
}

int main(int argc, char *argv[]) {
  vector<int> a = { 10, 5, 7, 20, 15, 30 };
  cout << n(a) << endl;
  return 0;
}

Answer 3

Этот вопрос может быть легко решен, если у вас мало знаний о рекурсии, перестановке и комбинациях, а также о бинарном дереве поиска (очевидно).

Сначала вы строите двоичное дерево поиска с заданной последовательностью. Вы также можете выполнить ту же операцию в массиве, но древовидная визуализация создаст хорошую картину.

Для заданной последовательности arr [1..n] 1-й элемент останется на том же месте, как и в данном массиве, и в arr [2..n] необходимо ввести только расположение.

Предположим:

bag1 = количество элементов в arr [2..n], которые меньше, чем arr [0].

и,

bag2 = количество элементов в arr [2..n], которые больше, чем arr [0].

Поскольку перестановка элементов в bag1 в последовательности не будет конфликтовать с числами, присутствующими в bag2 при формировании бинарного дерева поиска, можно начать вычисление ответа, выбирая элементы bag1 из ( n-1) элементы для перестановки и , затем остальные ((n-1) - bag1) = bag2 элементы могут быть размещены 1 способом только сейчас . Порядок элементов в bag1 должен быть таким же, как и для элементов bag2 в последовательности.

Поскольку каждое поддерево дерева двоичного поиска должно быть BST. Аналогичный процесс будет выполняться на каждом узле и умножать локальный ответ для узла на окончательный ответ.

int ans = 1;
int size[1000000] = {0};

// calculate the size of tree and its subtrees before running function "fun" given below.
int calSize(struct node* root){
     if(root == NULL)
          return 0;

     int l = calSize(root->left);
     int r = calSize(root -> right);
     size[root->val] = l+r+1;
     return size[root->val]; 
}

void fun(struct node* root){
     if(root == NULL)
         return;

     int n = size[root->val];
     if(root->left){
         ans *= nCr(n-1, size[root->left]);
         ans *= 1; // (Just to understand that there is now only 1 way 
                   //to distribute the rest (n-1)-size of root->left)
     }

     fun(root->left);
     fun(root->right); 
}

int main(){
     struct node* root;

     //construct tree
     //and send the root to function "fun"

     fun(root);

     cout<<ans<<endl;
     return 0;
}

Answer 4

Вы можете сделать это задом наперед: учитывая BST, перечислите все массивы целых чисел, которые могут привести к этому BST ...

Не могли бы вы (используя недетерминизм ...)

1. Извлеките root и добавьте его в отправляемый набор.
2. недетерминистически выбирает элемент из дерева, которого нет в наборе но чей родитель, и добавьте его в излучаемый набор и испустите его.
3. повторите 2, пока все не испустится.

Недетерминизм даст вам все такие массивы. Тогда вы можете сосчитать их.