How many arrangements of the letters AAABBBCCCDDDEEE are there such that there are no triple letters in the sequence?
The total number of ways, including triplets, is 15!/(3!)^5 = 168,168,000
The Python itertools.permutations does not account for duplicate elements, but a different library does have that function: more-itertools.distinct_permutations.
A test run counted the expected number.
But when all triplets are excluded, the count is 145,895,280
The first 10 and the last 10 permutations are shown:
['AABABBCCDCDEDEE',
'AABABBCCDCDEEDE',
'AABABBCCDCEDDEE',
'AABABBCCDCEDEDE',
'AABABBCCDCEDEED',
'AABABBCCDCEEDDE',
'AABABBCCDCEEDED',
'AABABBCCDDCEDEE',
'AABABBCCDDCEEDE',
'AABABBCCDDECDEE',
... ... ... ... ,
... ... ... ... ,
... ... ... ... ,
'EEDEDDCCBBACBAA',
'EEDEDDCCBBCAABA',
'EEDEDDCCBBCABAA',
'EEDEDDCCBCAABAB',
'EEDEDDCCBCAABBA',
'EEDEDDCCBCABAAB',
'EEDEDDCCBCABABA',
'EEDEDDCCBCABBAA',
'EEDEDDCCBCBAABA',
'EEDEDDCCBCBABAA']]
------------------------
count = 0
results = []
from more_itertools import distinct_permutations
for p in (distinct_permutations('AAABBBCCCDDDEEE')):
skip = False
inarow = 0
for i,v in enumerate(p):
if i == 0:
last = v
inarow = 1
continue
if v == last:
inarow += 1
if inarow >= 3:
skip = True
break
elif v != last:
inarow = 1
last = v
if not skip:
results.append(''.join(p))
count += 1
print(count)
|
Posted by Larry
on 2023-11-14 15:05:56 |