Introduction

Generating anagrams is essentially a permutation problem with an extra wrinkle: duplicate letters can create duplicate outputs if you are careless. The right algorithm depends on whether you want every unique rearrangement of the letters or only rearrangements that are valid dictionary words.

Start with the real problem definition

If the input is east, then eats, seat, and teas are anagrams. If the input contains duplicate letters, such as aab, naive permutation generation will repeat the same output several times unless you deduplicate.

That is why a good anagram generator should usually work from letter counts rather than from raw index swaps. A frequency-based approach avoids duplicate work naturally.

Backtracking with letter counts

A practical algorithm is:

1. count how many times each character appears
2. build the result one character at a time
3. choose only characters whose remaining count is positive
4. decrement the count, recurse, then restore it

This generates only unique permutations.

1from collections import Counter
2
3
4def generate_anagrams(text):
5    counts = Counter(text)
6    result = []
7    current = []
8    length = len(text)
9
10    def backtrack():
11        if len(current) == length:
12            result.append("".join(current))
13            return
14
15        for ch in sorted(counts):
16            if counts[ch] == 0:
17                continue
18            counts[ch] -= 1
19            current.append(ch)
20            backtrack()
21            current.pop()
22            counts[ch] += 1
23
24    backtrack()
25    return result
26
27
28print(generate_anagrams("aab"))

This approach avoids repeated anagrams such as generating aab twice just because the two a positions were swapped internally.

Why naive permutation is wasteful

A brute-force algorithm that permutes characters by position is fine for short strings with all distinct letters, but it becomes wasteful fast when duplicates appear. For aabb, many raw permutations are the same word.

The frequency-based algorithm is better because it searches the space of unique character choices rather than the space of all index arrangements.

That does not make the problem cheap. The number of unique anagrams can still be large, but at least the algorithm is not doing needless duplicate work.

If you only want valid dictionary words

Many real anagram problems do not want every rearrangement. They want only real words. In that case, generating all unique rearrangements is only half the job. You then need a dictionary check.

A simple approach is to generate all unique candidates and filter them through a set of valid words. A more advanced approach uses a trie or prefix tree to prune branches early when the partial word cannot lead to any dictionary entry.

That pruning matters for long inputs because the search space grows factorially.

Complexity in plain language

Anagram generation is fundamentally expensive because the number of rearrangements grows very quickly with input length. No clever implementation changes that basic growth. What a good algorithm does is avoid wasting work on duplicates and dead branches.

So the goal is not to make factorial growth disappear. The goal is to spend your time only on meaningful candidates.

Common Pitfalls

• Generating raw permutations by index and then discovering many duplicate outputs.
• Forgetting that repeated letters should reduce the number of unique anagrams.
• Assuming every rearrangement is a valid word when a dictionary filter is actually required.
• Using brute force for long inputs without any pruning or deduplication.
• Storing every result in memory when streaming or yielding results would be safer.

Summary

• Anagram generation is a permutation problem, but duplicate letters require extra care.
• A backtracking algorithm based on letter counts naturally avoids duplicate outputs.
• Naive position-based permutation is often wasteful when characters repeat.
• If you want real-word anagrams, add dictionary filtering or prefix pruning.
• The search space still grows quickly, so efficiency is mostly about avoiding redundant work.