I have a tree T, I need to generate all possible variants of T by permuting all its child nodes(please refer the following figure). how can I generate all variants, T, using recursion? enter image description here

any help is appreciated.

  • $\begingroup$ This is a very straightforward application of recursion. I suggest making sure that you understand recursion. Once you do, you would be able to solve it on your own. $\endgroup$ – Yuval Filmus Apr 2 '20 at 14:21

The outline is: You start the function-call at the root vertex. For every child-vertex, you find all permutations of its sub-tree. Then you you find all combinations of these permuations of the children's sub-trees, and for each of them do all permutations of the child-vertices themselves.
The recursion happens where you need the permutations of the sub-trees of the children.
The exit-condition is the call on a leaf.

Set<Tree> perm(vertex x):
    if x is leaf:
        return x
    Let C be the set of all children of x.
    Set<Tree> result <- emptySet
    For all different combinations of perm(c) from the vertices c of C, now called comb:
        For all permutations p of C:
            add to result the graph you get with comb and p.
    return result


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.