Introduction

If the goal is to find strings in a set that are permutations of a target string, you should not generate all permutations and test membership one by one. The efficient approach is to normalize each string into a canonical representation, such as its sorted characters or character counts, and compare those signatures.

What "Matching Permutations" Means

Two strings are permutations of each other if they contain exactly the same characters with the same multiplicities, possibly in a different order.

Examples:

• 'listen and silent match'
• 'abba and baba match'
• 'abb and ab do not match'

So the real question is not "can I generate the permutations" but "can I compare strings by multiset of characters."

The Simple Canonical Form: Sorted Characters

For many cases, the easiest solution is to sort the characters in each string. All permutations then collapse to the same normalized key.

1def canonical(s):
2    return "".join(sorted(s))
3
4target = "listen"
5words = {"silent", "enlist", "google", "inlets", "stone"}
6
7matches = {word for word in words if canonical(word) == canonical(target)}
8print(matches)

This is easy to read and correct for ordinary string matching.

Why This Is Better Than Generating Permutations

Generating all permutations of a string of length n takes n! possibilities in the worst case. That becomes infeasible very quickly.

For example:

• length 5 gives 120 permutations
• length 8 gives 40320
• length 10 gives 3628800

Filtering the set by canonical form is much cheaper. If you have m candidate strings of average length n, the sorted-key approach costs about O(m * n log n) instead of factorial blowup.

A Faster Signature for Fixed Alphabets

If performance matters and the alphabet is small or known in advance, character counts are often better than sorting.

1from collections import Counter
2
3def signature(s):
4    return tuple(sorted(Counter(s).items()))
5
6target = "abba"
7words = {"baba", "aabb", "abbb", "baab"}
8
9matches = {word for word in words if signature(word) == signature(target)}
10print(matches)

This is especially useful when strings are long or when sorting each string would be unnecessarily expensive.

For lowercase English letters only, you can use a fixed-size count vector:

1def lowercase_signature(s):
2    counts = [0] * 26
3    for ch in s:
4        counts[ord(ch) - ord("a")] += 1
5    return tuple(counts)

That avoids both permutation generation and general-purpose sorting.

Filtering a Large Collection Efficiently

If you need to run many queries, preprocess the set into groups keyed by signature.

1from collections import defaultdict
2
3def canonical(s):
4    return "".join(sorted(s))
5
6words = {"silent", "listen", "enlist", "google", "inlets", "stone"}
7groups = defaultdict(set)
8
9for word in words:
10    groups[canonical(word)].add(word)
11
12query = "listen"
13print(groups[canonical(query)])

Now each query becomes a cheap dictionary lookup rather than a scan of the entire set.

This is the right design when you are effectively building an anagram index.

Case Sensitivity and Normalization

Real text often needs preprocessing:

• lowercase everything if matching should be case-insensitive
• strip whitespace if phrases are allowed
• normalize Unicode if accented forms should compare consistently

Example:

1import unicodedata
2
3def normalize_text(s):
4    s = unicodedata.normalize("NFC", s)
5    s = s.lower().replace(" ", "")
6    return s

Do this before computing the signature, otherwise apparently equivalent strings may fail to match.

Common Pitfalls

• Generating all permutations of the target string and checking set membership, which becomes factorial and impractical very quickly.
• Comparing only sorted unique characters and forgetting character counts, which breaks cases such as abb versus ab.
• Ignoring normalization rules such as case, spaces, or Unicode form when the application expects those differences to be irrelevant.
• Recomputing signatures for the full set on every query when a precomputed index would make repeated lookups much cheaper.
• Using a solution designed for unrestricted Unicode when the real input is fixed lowercase ASCII and a much simpler count vector would be faster.

Summary

• To filter for permutation matches, compare canonical signatures instead of generating permutations.
• Sorting characters is the simplest correct solution.
• Character-count signatures are often faster when the alphabet is fixed or small.
• Precompute groups by signature if you need repeated queries over the same set.
• Define normalization rules up front so matching behavior is consistent and unsurprising.