I think I’ve figured out the basic math for pairs - but only if those pairs are of a different type. This works for the “abfdefa” example, but would not work, say, if the string was “abadeaa”. I’m still trying to work out how it work for n+ repeats. Hopefully seeing how it works for “abfdefa” will point in the right direction of writing algorithms for pairs of the same type, and triplets of a different type. Then it’s clever coding to figure out how to reduce the lines of code.
[FIRST PAIR]
Ok, so, first, I slice the input string into an array of singles and mutiples. So “abfdefa” > [“bde”,“aa”,ff"].
Let’s just assume for the moment that “ff” is “fe”. To find the amount of non-repeating permutations, there will be the total amount of permutations (with repeats) - the number of permutations that have repeats. The total amount of permutations will equal the factorial of the input string length. If length(“abfdefa”) is equal to 7, then 7!.
So far, we know then that the number of perms (without reps) will equal 7! - x, where x is the number of permutations containing combination “aa”. How do we find x?
We can find x, by considering the number of position we can insert “aa” into “bdeff”. We do this by drawing up “bdeff” as follows. _ B_D_E_F_F_ . We see that “aa” can be insert into any space between the letters, or either of the spaces on the outside. The number of possible positions is determined by length(“bdeff”) + 1. This gives us 6 possible places “aa” can be placed. Since “aa” can be switched around, there will be more than one permutation for each of the possible placements. Because length(“aa”) is 2, then we know that the amount of permutation is equal to 6 * 2! = 12. But for each of these 12 permutations, we can also switch “BDEFF” around 5! times. So the amount of permutations containing pairs, will equal: 5!* 6* 2! . This formula returns the value 1440.
So, the number of permutations that do no contain pair “aa” will equal
7! - (5!* 6* 2!) = 5040 - 1440 = 3600. This is enough math to solve the “abcdefa” example.
[SECOND PAIR]
For the second pair, which is “ff”, we can simply apply the same algorithm above to determine the amount of permutations which contain pairs of “f”. This will also be 1440. That simple? No! We have to consider that some of the pair-permutations of “aa” will contain some permutations which “ff” and vice versa. If we do a venn, we get a visual picture of the intersection:
{ “aa”:1440 [ “aa”&“ff”: ??? } “ff”:1440 ].
How do we get the number for “aa” & “ff”? Well, since we know that either “aa” or “ff” yields 1440 permutations, we can do further search within either. To get the number of pairs of “ff” within the set of all permutations containing “aa”, we repeat some of the logic from above, but set the problem up differently.
This time, rather than treating “aa” as seperate characters, where going to treat it as a block. So the position set up will look like this. _ AA_B_D_E_ . This gives us 5 possible position where “ff” could be placed, so 52! gives 10 permutations for one permutation of “aabde”. Now, to get the total number of permutations, rather than assuming that all characters can be switched around, we know that only “bde” can be switched around because “aa” must be kept together. So rather than multiplying (52!) by 5!, we will only multiply it by 4!. As well as this, because we have ANOTHER pair “aa” we need to multiply 4! by 2!. This yields a total function of 4!2! * (5*2!) which equals 480.
So then, to get the number of pairs (n =1) of two types, we use the following calculation.
7! - ((5!* 6* 2!) - [(5!* 6* 2!) - (4!2! * (5*2!)]
= 5040 - 1440 - (1440 - 480)
=5040 - 1440 -960
=2640
If I get a more concise algorithm, I’ll post it. I suspect number of repetitions will mean something like:
1 pair: (5!* (62!)
2 pair: (4!2! (52!)
3 pair: (3!2!2! (4*2!)… and so on