Hello lets say I have the string AAABBBB. I don't just want to calculate the numbers want to generate all the unique combinations of this string.
One way I thought of doing it was to simply move each A one position at a time to the end and then move each B one position at a time until the original string was regenerated and remove the duplicates
for example
AAABBBB AABABBB AABBABB
etc
but I don't know if this will give me everything or if there is a simpler way that can be generalized.
Can somebody show me a way/if my way is right and help me understand theoretically?
edit: Sorry the title inaccurately said 5 letter than I changed the title because my question is more general.
$\endgroup$ 42 Answers
$\begingroup$The first thing to do is to take out two letters. There are three possibilities: remove two $\sf B$s, or one $\sf A$ and one $\sf B$, or two $\sf A$s. In each one of those cases, we must generate all ways of ordering the remaining letters.
Here is a recursive algorithm. If there are any $\sf A$s at the end of the string, move all of them left till they form a bigger block with an $\sf A$ to their left, then shift that bigger block to the right once. Else, if there is no $\sf A$ at the end of the string, shift the rightmost $\sf A$ one positition right.
If we hadn't removed any letters, this would generate the following list:
$$ \begin{array}{l} \sf \color{LimeGreen}A\color{Orange}A\color{Magenta}ABBBB \\ \sf \color{LimeGreen}A\color{Orange}AB\color{Magenta}ABBB \\ \sf \color{LimeGreen}A\color{Orange}ABB\color{Magenta}ABB \\ \sf \color{LimeGreen}A\color{Orange}ABBB\color{Magenta}AB \\ \sf \color{LimeGreen}A\color{Orange}ABBBB\color{Magenta}A \\ \hline \sf \color{LimeGreen}AB\color{Orange}A\color{Magenta}ABBB \\ \sf \color{LimeGreen}AB\color{Orange}AB\color{Magenta}ABB \\ \sf \color{LimeGreen}AB\color{Orange}ABB\color{Magenta}AB \\ \sf \color{LimeGreen}AB\color{Orange}ABBB\color{Magenta}A \\ \hline \sf \color{LimeGreen}ABB\color{Orange}A\color{Magenta}ABB \\ \sf \color{LimeGreen}ABB\color{Orange}AB\color{Magenta}AB \\ \sf \color{LimeGreen}ABB\color{Orange}ABB\color{Magenta}A \\ \hline \sf \color{LimeGreen}ABBB\color{Orange}A\color{Magenta}AB \\ \sf \color{LimeGreen}ABBB\color{Orange}AB\color{Magenta}A \\ \hline \sf \color{LimeGreen}ABBBB\color{Orange}A\color{Magenta}A \\ \hline \\ \hline \sf B\color{LimeGreen}A\color{Orange}A\color{Magenta}ABBB \\ \sf B\color{LimeGreen}A\color{Orange}AB\color{Magenta}ABB \\ \sf B\color{LimeGreen}A\color{Orange}ABB\color{Magenta}AB \\ \sf B\color{LimeGreen}A\color{Orange}ABBB\color{Magenta}A \\ \hline \sf B\color{LimeGreen}AB\color{Orange}A\color{Magenta}ABB \\ \sf B\color{LimeGreen}AB\color{Orange}AB\color{Magenta}AB \\ \sf B\color{LimeGreen}AB\color{Orange}ABB\color{Magenta}A \\ \hline \sf B\color{LimeGreen}ABB\color{Orange}A\color{Magenta}AB \\ \sf B\color{LimeGreen}ABB\color{Orange}AB\color{Magenta}A \\ \hline \sf B\color{LimeGreen}ABBB\color{Orange}A\color{Magenta}A \\ \hline \\ \hline \sf BB\color{LimeGreen}A\color{Orange}A\color{Magenta}ABB \\ \sf BB\color{LimeGreen}A\color{Orange}AB\color{Magenta}AB \\ \sf BB\color{LimeGreen}A\color{Orange}ABB\color{Magenta}A \\ \hline \sf BB\color{LimeGreen}AB\color{Orange}A\color{Magenta}AB \\ \sf BB\color{LimeGreen}AB\color{Orange}AB\color{Magenta}A \\ \hline \sf BB\color{LimeGreen}ABB\color{Orange}A\color{Magenta}A \\ \hline \\ \hline \sf BBB\color{LimeGreen}A\color{Orange}A\color{Magenta}AB \\ \sf BBB\color{LimeGreen}A\color{Orange}AB\color{Magenta}A \\ \hline \sf BBB\color{LimeGreen}AB\color{Orange}A\color{Magenta}A \\ \hline \\ \hline \sf BBBB\color{LimeGreen}A\color{Orange}A\color{Magenta}A \\ \end{array}$$
So it looks like this algorithm must be applied to the following seeds:
$$ \begin{array}{l} \sf AAABB \\ \sf AABBB \\ \sf ABBBB \end{array} $$
$\endgroup$ 1 $\begingroup$Pseudo code (counting from 1):
For i in 1 to 5: Put an A in position i For j in i+1 to 6: Put an A in position j For k in j+1 to 7: Put an A in position k Put Bs in all the other positions Output the stringThat shouold give you $35$ results looking like
i j k output
1 1 2 3 AAABBBB
2 1 2 4 AABABBB
3 1 2 5 AABBABB
4 1 2 6 AABBBAB
5 1 2 7 AABBBBA
6 1 3 4 ABAABBB
7 1 3 5 ABABABB
8 1 3 6 ABABBAB
9 1 3 7 ABABBBA
10 1 4 5 ABBAABB
11 1 4 6 ABBABAB
12 1 4 7 ABBABBA
13 1 5 6 ABBBAAB
14 1 5 7 ABBBABA
15 1 6 7 ABBBBAA
16 2 3 4 BAAABBB
17 2 3 5 BAABABB
18 2 3 6 BAABBAB
19 2 3 7 BAABBBA
20 2 4 5 BABAABB
21 2 4 6 BABABAB
22 2 4 7 BABABBA
23 2 5 6 BABBAAB
24 2 5 7 BABBABA
25 2 6 7 BABBBAA
26 3 4 5 BBAAABB
27 3 4 6 BBAABAB
28 3 4 7 BBAABBA
29 3 5 6 BBABAAB
30 3 5 7 BBABABA
31 3 6 7 BBABBAA
32 4 5 6 BBBAAAB
33 4 5 7 BBBAABA
34 4 6 7 BBBABAA
35 5 6 7 BBBBAAA
