Блог пользователя gXa

Permutations Of BST
Автор gXa, история, 8 лет назад, По-английски

Hi everyone, I am trying to find all permutations of the input elements which will result in the same Binary Search tree as the one formed with the input array.

Eg: I/P: 4, 3, 1, 2, 6, 5, 7

o/p:4 , 6, 3, 7, 5, 1, 2

4, 3, 2, 1, 6, 5, 7

and so on.

I have gone through links on internet but could not code it.

I am unable to print all the permutations correctly. So, I request community to help me with logic ( if recurive function can be provided too )?

Thank You

Теги bst
  • Проголосовать: нравится
  • +17
  • Проголосовать: не нравится

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Auto comment: topic has been updated by gXa (previous revision, new revision, compare).

→ Ответить
»
8 лет назад, # |
← Rev. 3   Проголосовать: нравится +3 Проголосовать: не нравится

Hi please someone could have a look and guide me the logic to print all the permutations. I can count number of permutations by a formula but cannot print all the permutations correctly.

→ Ответить
»
8 лет назад, # |
← Rev. 5   Проголосовать: нравится +11 Проголосовать: не нравится

Well heres a recursive function which I feel should solve the problem, but the time complexity is very high!
The root must always be the first element. The next element can be either its left child or right child. The element after that can be the child not taken in the previous round or the children of the current node.
poss contains the possible next elements to be added. Initially poss consists of only the root node.

void solve(vector<node> poss, vector<int> toprint)
{
    if(poss.size() == 0)
    {
        for(int i = 0; i < toprint.size(); i++)
            cout<<toprint[i]<<" ";
        cout<<endl;
        return;
    }
    
    for(int i = 0; i < poss.size(); i++)
    {
        vector<node> nxtposs;
        for(int j = 0; j < poss.size(); j++)
            if(j != i)
                nxtposs.push_back(poss[j]);
                
        if(poss[i]->left)
            nxtposs.push_back(poss[i]->left);
        if(poss[i]->right)
            nxtposs.push_back(poss[i]->right);
            
        vector<int> nxtprint = toprint;
        nxtprint.push_back(poss[i]->value);
        solve(nxtposs, nxtprint);
    }
}

How do i post code in comments lol?

→ Ответить