Permutations of items with no adjacent duplicates

[alandberg]

Hello

I have recently come across a problem in my programming exercises that I haven't been able to solve, even after several days of hard thinking and tinkering.

I have found that this problem may be solved by means of permutations using factorials, but there is a specific permutation that I cannot calculate.

The problem statement is that a string of n characters contains 3 types of different characters, e.g. A, B and C, where each character can have duplicates within the string. Calculate the number of different ways the characters in the string can be arranged. No two adjacent characters can be the same, where the first and last character are also adjacent.
For example: ABBA can be arranged in two ways: ABAB and BABA.

So far, I have tried to find a permutation for the string AAABBC. My method is as follows:

Calculate all permutations under consideration of duplicates as 6! / 3! x 2!
Then, subtract all permutations that contain an occurrence of AAA, AA, BB
The issue with this is that each of these three permutations will also include a subset of the other two, which means I will need to add back permutations that contain both AAA and AA, AAA and BB, and AA and BB. Finally I will need to subtract the intersection of all three sets.

This method may not even be correct, I am getting lost in trying to calculate permutations that contain duplicates. Can someone point me to a post / exercises where I can study this? Can someone please give me a hint on how to approach this problem.

Thanks and regards

Andy

 

[Stephen Tashi]

I have recently come across a problem in my programming exercises

I haven't solved the problem. These are just my random thoughts.

Is the solution to this problem to be given in the form of a computer program? If so it might expect an algorithm as an answer rather than solving this by finding a mathematical formula and simply writing the expression for that formula.

If the answer is to be a program, you should look up the subject of "algorithmic combinatorics". There is an online book about it that is probably overkill for your problem, but you might find it handy in your future work: http://www.1stworks.com/ref/RuskeyCombGen.pdf

If the answer is to be a single mathematical formula, I hope some other forum member will give you a hint. I've never enjoyed thinking about such problems. Algorithmic combinatorics is more interesting.

Algorithms that enumerate all possible arrangements of things can often be written in a recursive style. Computer science textbooks seem to like recursion. For practical programming, I prefer to implement recursion using stacks that I can monitor for overflows.

That might suggest a slick approach using just mathematics. Induction resembles recursion. If you knew the answer to the problem for a string of length n, could you find the answer for a string of length n+1?

A list of the arrangements for a string of length n would contain only "legal" initial substrings for the arrangements of length n+1. It would be also be missing some legal initial substrings. You could consider how the legal substrings that are present could be used to form other legal substrings and how the missing initial substrings could be added back.

I think the algorithmic solution to the above idea taxes my brain less than a mathematical solution. If someone gave you all the legal strings of length n, could your write an algorithm to form all the legal strings of length n+1? If you can write such a function then it can be used recursively to solve the problem.

If S is legal string of length n then we can append any any character to it except its first and last character. That seems straightforward to program. How do we account for the missing strings? A string of length 4 like ABCA will be missing from the list because its first and last characters match, but it could be used as a legal initial substring in a string of length 5.

Perhaps the best way to program this is to write one function G that computes a list Lg(n) of all strings of length n plus the ones that are illegal only because the first and last characters match. Then write another function F that computes a list Lf(n) of legal strings by pruning the list Lg(n) of all the strings whose first and last characters match. To find the legal strings of length n+1, apply G to the Lg(n) to produce Lg(n+1). Then apply F to Lg(n+1) to produce Lf(n+1).