CODEWITHSUNDEEP
algorithmdata-structures
Luiz
Luiz

Reputation: 2539

Build a k-ary tree with no repeated values

Suppose I have two values: x1 and x2.

Given a single root, how to build all the combinations of x1 and x2 using an k-ary tree?

Example:

#0    root
      /   \
#1  x1     x2
     |
#2  x2

At level #1 I have the initial elements, x1 and x2.

At level #2 I have x2, making the combination x1x2, but don't have x1 because it would be a repeated combination (x2x1, we don't care about the elements order here).

If I had more than two elements, the tree would keep going on, until the level is equal to the number of elements minus 1.

I have already built the initial #1 level. but how do I keep generating the tree without repeating combinations? In other words, how to verify if I should or not put a given element on the tree, in the most performatic way. There is some well-known algorithm for this?

Additional info: PHP

Upvotes: 1

Views: 48

Answers (1)

Alireza
Alireza

Reputation: 1038

Edit: some modifications on building the tree

My idea is having a n-ary tree for n elements (x1, x2,... ,xn). let root be x0, then for any node xi (0 <= i <= n), you should have all children xj where (i < j <= n). In this way you can have all non-repeating combinations. E.g. for n=3 the 3-ary tree would be something like this:

root ---> x1 ---> x2 ---> x3
          |  ---> x3
root ---> x2 ---> x3
root ---> x3

Upvotes: 1

Related Questions