1

Expected tree for given array Given an array of n elements , create a tree such that all path labels from root to leaf represent all combinations of array elements of length 'n'. for ex if array = {1,2,3} then the tree should be such that there are 6 paths from root to leaf with each of them as follows {{123},{132},{213},{231},{312},{321}} 1<= n <= 10^9 and there can be duplicates too.

Sorrowfull Blinger
  • 191
  • 1
  • 7
  • The root value should be changed? Or create a dummy root and start parsing from level 1 onwards? – Erobrere Dec 29 '15 at 13:55
  • Yes create a dummy root , and then every edge label gets one of the values from array... Hope i am clear... – Sorrowfull Blinger Dec 29 '15 at 13:59
  • 1
    You do realize that the number of nodes in such trees will be O(n!) right? So it in pretty intractable even for small n let alone 10^9. – ElKamina Dec 29 '15 at 14:26
  • Do you need the tree or would it be sufficient to just traverse the possibilities recursively? – m13r Dec 29 '15 at 15:21
  • @ElKamina - Yes its n! ,i basically want to traverse such a tree in BFS fashion. Lets keep the value of 'n' to a lower value say 10. I wanted to know the best way to find what my child node's edge labels are for any given node at any given level. Now if i do want this for higher values of 'n' is there anything i can go about implementing? – Sorrowfull Blinger Dec 29 '15 at 15:45
  • @m13r .Like i said above i do not want to have a tree in memory , i juts want to traverse the tree in BFS fashion all through till the end. – Sorrowfull Blinger Dec 29 '15 at 15:46
  • Are you really just trying to enumerate all the permutations of n numbers in a breadth-first fashion? So traversing the virtual tree would give you `{ {1,2,3}, {2,3,1,3,1,2},{3,2,3,1,2,1}}`? – Jim Mischel Dec 29 '15 at 17:05
  • Have a look at the answer to this question: http://stackoverflow.com/questions/31216097/given-n-and-k-return-the-kth-permutation-sequence Understand the algorithm, and you will know how to do what you want – Matt Timmermans Dec 30 '15 at 00:19

1 Answers1

1

Since the list might contain duplicates you need to dedupe them and keep count. To keep it less confusing let us use letters instead of numbers.

Now, let us say {a, a, b, b, b} is your input.

Convert it into a data structure that looks like {a:2, b:3} (you can do this by using a map or using tuples)

Algorithm:

Initialization: Create a root node

Input: data = {a:2, b:3} and node

For node create k = size(data) children.

Assign each key in data to each new edge (in this case a and b).

For each child call this function recursively with the corresponding edge value removed. Example: for the function call corresponding to a, you will pass on data = {a:1, b:3} and for b, data = {a:2, b:3}

Whenever a value becomes 0, remove the corresponding key from data.

ElKamina
  • 7,747
  • 28
  • 43