# Finding all length-n words on an alphabet that have a specified number of each letter

For example, I might want to generate all length n=6 words on the alphabet {A, B, C} that have one A, three B's and two C's. An example of such a word is: 'ABBBCC'. I'd like to generate all such words.

I've already tried generating all permutations of a particular string (like 'ABBBCC') and deleting all duplicates. This is too slow for my purposes.

Permutations is already duplicate-aware:

Permutations[{"A", "A", "B"}]

{{"A", "A", "B"}, {"A", "B", "A"}, {"B", "A", "A"}}


Perhaps you are looking for combinations of a particular length (which can then be permuted). One way to get those is this:

f[k_, {}, c__] := If[+c == k, {{c}}, {}]

f[k_, {x_, r___}, c___] := Join @@ (f[k, {r}, c, #] & /@ 0~Range~Min[x, k - +c])


Use:

f[4, {1, 3, 2}]

{{0, 2, 2}, {0, 3, 1}, {1, 1, 2}, {1, 2, 1}, {1, 3, 0}}


These represent the words of length 4 for a list with unique items repeated, 1, 3, and 2 times at most.

You can then construct the actual words from these lists, e.g.:

char = {"A", "B", "C"};

StringJoin@MapThread[ConstantArray, {char, #}] & /@ f[4, {1, 3, 2}]

{"BBCC", "BBBC", "ABCC", "ABBC", "ABBB"}


Or:

Inner[#2 ~Table~ {#} &, f[4, {1, 3, 2}], char, StringJoin]

{"BBCC", "BBBC", "ABCC", "ABBC", "ABBB"}


And with permutations:

Inner[#2 ~Table~ {#} &, f[4, {1, 3, 2}], char, Join]

Permutations /@ %

{{B,B,C,C},{B,B,B,C},{A,B,C,C},{A,B,B,C},{A,B,B,B}}

{{{B,B,C,C},{B,C,B,C},{B,C,C,B},{C,B,B,C},{C,B,C,B},{C,C,B,B}}, . . . }

• Sigh. I didn't bother to look at the documentation for permutations because I assumed it wasn't. Thank you! May 3, 2012 at 0:42
• Could you please avoid (or stop) the use of quote block for output? I find the thin grey bar on yellow BG highly distracting and really, serves no purpose. I think enclosing it in (* *) is cleaner and since it's shown in subtle grey, it's not too distracting either...
– rm -rf
May 3, 2012 at 0:44
• Your first answer was sufficient. Thank you :D May 3, 2012 at 0:44
• @R.M I don't really know what to say; I much prefer this format. I seem to recall this was on Meta; I'll look for the popular opinion. May 3, 2012 at 0:48
• @R.M besides not very copyable I don't have much problems with this style. I find it visually more clear and attractive than the one I proposed myself in the Meta. It mimics one of mma's own styles. May 3, 2012 at 6:54