list manipulation - 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.
Answer
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}}, . . . }
Comments
Post a Comment