Count the distinct arrangements of a word's letters, and how many of them keep every copy of its most common letter side by side.
What to build
A program that counts arrangements with repeated letters.
Requirements
- Print
arrangements A: the number of different orders of the word's letters. - Find the most common letter (if several tie, the one first in the alphabet) and print
letter L, thentogether T: the arrangements in which all copies of L are next to each other. - Print
probability P: the chance that a random arrangement keeps them together, as a reduced fraction.
Input
One line: a word of capital letters.
Output
Four lines.
Constraints
1 ≤ length ≤ 12.
Example
Input:
BANANA
Output:
arrangements 60
letter A
together 12
probability 1/5
Why it works
Identical letters can be swapped without changing the word, so each repeat divides the count; gluing a letter's copies into one block turns "together" into an ordinary arrangement of fewer items.
Examples
BANANA
arrangements 60 letter A together 12 probability 1/5
AAB
arrangements 3 letter A together 2 probability 2/3
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
Arrangements: n! divided by the factorial of every letter's count.
Hint 2
To keep all copies of a letter together, glue them into one block: n − c + 1 items, and divide by the other letters' repeats.
Solution
Show one correct solution (try it yourself first)
from collections import Counter
from fractions import Fraction
from math import factorial
def arrangements(counts):
result = factorial(sum(counts))
for c in counts:
result //= factorial(c)
return result
word = input().strip()
counts = Counter(word)
total = arrangements(counts.values())
best = max(counts.values())
letter = min(ch for ch in counts if counts[ch] == best)
others = [c for ch, c in counts.items() if ch != letter]
together = arrangements(others + [1])
print("arrangements", total)
print("letter", letter)
print("together", together)
print("probability", Fraction(together, total))