0
$\begingroup$

What is the minimum number of gems required to make a garland (circular) which contains all permutations, with unique colored gems considered as a valid permutation, of size n, when we have infinite number of gems of N colors.

The garland is circular, so we don't need to consider reverse direction of same permutation (eg. if 123 is present, 321 is also present) Also, we don't need to consider concatinating extra gems at the end, if the are present in the beginning (eg, 123 also contain 231) Example : for 4 colors, we need our garland to have (123, 124, 132, 134, 142, 143 etc...)

It is different from de bruijn sequence, as de bruijn sequence will contain 111, 121 etc as well, so it will be LONGER, and these permutations are not counted.

My approach : suppose n = 3, and N = 5. then, we will have numOfCombs = (N! / ((N-n)! * n!) ) combinations of them. for any combinations, "123", we can make a string "12312", which will have all permutations. So, as there are numOfCombs combinations, and for each combination we can have a string of length 5 which contains all permutations. so (numOfCombs * 5), in this case, gives 50. However, this can be optimized. as, 12312, and 12412, can be grouped together, as 12312412, we can decrease this length. We will not have common length 3, we can have only 2 and 1 as common length, so after optimizing this, we can have string of length 40.

However, this was for length 3, for which i calculated this manually. for 4, 5... i am not able to get any relation...

$\endgroup$
  • $\begingroup$ It's a good description of the problem! Now, what are your thoughts? Have you worked out specific cases or simple families of cases? $\endgroup$ – Greg Martin Mar 23 '16 at 19:27
  • $\begingroup$ @GregMartin Actually the question was for n = 3 & N = 5, i tried generalising it. i tried it for basic cases. i failed to see any pattern. $\endgroup$ – nishantbhardwaj2002 Mar 24 '16 at 3:33
  • $\begingroup$ the only way i could find to solve this was using graph algorithms (like bfs or dijkstra) but it wont be very efficient for larger numbers. there might be some better way to do it $\endgroup$ – nishantbhardwaj2002 Mar 24 '16 at 5:51
  • $\begingroup$ also, i have updated the question with a approach, which i am not sure, will not work for n > 3. or not $\endgroup$ – nishantbhardwaj2002 Mar 24 '16 at 12:08

Your Answer

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

Browse other questions tagged or ask your own question.