0
$\begingroup$

I would like to generate fixed size sequences contained a fixed number of repeated symbols. For example how to generate sequences of size N containing exactly p symbols of one type q symbols of another, etc... where p, q, etc. < N.

In my case I want to generate sequences of size 13 containing 3 symbols denoted x, 2 symbols denoted y and 2 symbols denoted z. Blank spaces are marked with '-'

So it would look like xxxyyzz------, x-xx--y-y-zz- ... etc.

There are C(13, 3)*C(10,2)*C(8,2) ways of generating such sequences but I have no idea how to generate them.

Technically how do you describe this problem? Combinations with repetitions? Where can I find a description of algorithms to solve this? Does Knuth book describe this algorithms? Most of the solutions I find deal with generating permutations or combinations but none deal with repeated elements.

Thanks.

$\endgroup$
4
  • 1
    $\begingroup$ I think this might be more for math.SE Consider multinomial coefficients: en.wikipedia.org/wiki/… $\endgroup$ Jul 13, 2011 at 17:15
  • $\begingroup$ Thanks for the pointer. It led to me to the correct technical description of this problem which is the enumeration of permutations of a multiset. Now I need to find an algorithm to generate this permutations. $\endgroup$
    – user16416
    Jul 13, 2011 at 21:22
  • $\begingroup$ There is quite a literature on this. A google search on "permutations of a multiset generation" will give many hits. $\endgroup$ Jul 14, 2011 at 0:29
  • $\begingroup$ E.g. see Knuth's The Art of Computer Programming Volume 4A, section 7.2.1.2 "Generating all permutations". (This section was earlier published in Vol 4 Fasc 2, and before that as pre-fascicle 2B.) The very first page of this section (page 319) has an "Algorithm L" that should work quite nicely. $\endgroup$
    – shreevatsa
    Oct 16, 2016 at 9:08

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.