Arrangements of a word, and keeping letters together

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, then together 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

Example 1 · Input
BANANA
Expected output
arrangements 60
letter A
together 12
probability 1/5
Example 2 · Input
AAB
Expected output
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))

Lesson: Counting outcomes: permutations and combinations →