1
$\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$
4
  • $\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$ Mar 23, 2016 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$ Mar 24, 2016 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$ Mar 24, 2016 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$ Mar 24, 2016 at 12:08

1 Answer 1

1
$\begingroup$

I believe this is a variant of a question first asked by Hansraj Gupta in 1981. Michael Engen and I surveyed many similar problems in a paper called Containing all permutations; this particular variant is discussed briefly in the second item of the conclusion.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .