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

Question

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.

Answer 1

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}}, . . . }