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.

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ I think this might be more for math.SE Consider multinomial coefficients: en.wikipedia.org/wiki/… $\endgroup$
    – Daniel Moskovich
    Commented 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
    Commented 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$
    – Richard Stanley
    Commented 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
    Commented Oct 16, 2016 at 9:08

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .