Number of arrangements with no consecutive letter the same

Question

This question is related to my question here. I am trying to get the following count programmatically to verify whether my mathematics is right.

How many arrangements of the letters in the word PQRDDDEEEEFFFFF have no consecutive letter the same?

How to determine this count using a php program?

My approach

1. generated all possible permutations using heap's algorithm and stored in an array (used heap's algorithm as it is found faster)
2. removed all duplicates using array_unique function
3. Iterated through the array, identified the strings where adjacent letters are same using regexp /(.)\1/ and copied the strings where no adjacent letters are same to a new array.
4. The new array has the list of elements which is required.

My approach is working fine. But, for large strings (strings above 10 characters), memory issues are coming due to the large number of permutations and so the program does not work.

Is there any alternative approach to determine this programmatically?

Note:

I am looking for the count only and not the list of strings

Answer 1

Here's some Python that's much more efficient than your method, though still exponential (sorry, don't know PHP):

from collections import Counter


def instancekey(letters):
    return tuple(sorted(Counter(letters).values()))


memo = {}


def permcount(letters):
    if not letters:
        return 1
    key = instancekey(letters)
    count = memo.get(key)
    if count is None:
        count = 0
        for letter, lettercount in Counter(letters).items():
            rest = letters
            for i in range(lettercount):
                j = rest.find(letter)
                rest = rest[:j] + rest[j + 1:]
                if i % 2 == 0:
                    count += permcount(rest)
                else:
                    count -= permcount(rest)
        memo[key] = count
    return count

There are two ideas here. The first is to perform the count recursively via inclusion-exclusion. For each letter in the input, we accumulate the number of possibilities that begin with that letter. Naively, it's enough to count the possibilities for the remaining letters, but this doesn't enforce the constraint that the first two letters are equal. Thus we apply a correction -- subtract the number of possibilities where two letters are deleted. This correction itself requires a correction, whereupon we arrive at the inclusion-exclusion formula.

The second idea is to use memoization to cut down significantly on the number of function evaluations. Given a word like PQRDDDEEEEFFFFF, we count

P: 1
Q: 1
R: 1
D: 3
E: 4
F: 5

and then drop the letters (because they don't matter) and sort the values:

1,1,1,3,4,5.