Interview Question
Country: India
Interview Type: In-Person
This can be implemented using trees.
1. take the 1st element as root and add all the elements as a child.
for eg: take A as root, and add 3 child nodes: A, B, C
if the size = 3, again add child nodes to each sub node
in our example, with set = A,B,C and n = 3 , the tree would be:
A
/ | \
A B C
/|\ /|\ /|\
A B C ABC A B C
thus the height = k-1
Now traverse the tree from root to each leaf, which gives us the permutation
AAA, AAB and so on.
When you have traversed this tree, replace the node with next element from set, B in our case. repeat the process of traversal.
a little correction in last line:
When you have traversed this tree, replace the ROOT with next element from set, B in our case. repeat the process of traversal.
Brilliant idea, one small development to this idea.Since the tree is going to be a complete n-array Tree(in our case ternary tree), it can be built using only arrays, just like in heap.
1. First allocate nCr array of bytes. and fill the first three places by A,B and C.
2. formula for calculating children is as follows.
3. for any element at an index i, its n children need to be placed at n*i+(n), n*i+(n+2),... n*i+(n+n-1).
4. fill each of its children's indices by the symbol array as long as these indices are within bounds of the array.
5. All that is left to do is Depth first traversal iteratively.
Repeat steps 1 to 5 starting with next elemennt form the Symbol array and so on.
The permutations are just K-length "numbers" of radix-N (size-of-symbols), in the example 2-length numbers of radix 3, where the "digits" are 'A', 'B' and 'C' (0->A, 1->B, 2->C)
- Selmeczy, Péter December 15, 2011So if we create all K-lengths numbers of radix N we have solved the problem (just substiture digit-x with the xth symbol)
The number can be represented by an array of K integers, all 0 initially, this is number "00" that maps into "AA"
Now increment this number, the sequence generated will be (initial 00) then 01, 02, 10, 11, 12, 20, 21, 22 (all the 2-digit number using radix 3).
To increment the number represented using this array is a simple loop (adding one to the last digit, check for overflow, move the carry on, etc), same way as you have learnt in school. We know that we reached the highest representable number (in this case 22) when incrementing function will have a carry to the end.
This works properly if all the symbols are different and the number of symbols is smaller than the number that can be represented in an integer.