Introduction

If you need all permutations that satisfy a set of rules, the core problem is not permutation generation alone. It is permutation generation plus pruning: the algorithm must reject partial arrangements as early as possible instead of creating every possible ordering and filtering them afterward.

Why Brute Force Gets Expensive Fast

For n elements, there are n! permutations. That explodes quickly:

• '5! = 120'
• '8! = 40320'
• '10! = 3628800'

If you generate all of them and only then check the rules, most of the work is wasted. The better approach is backtracking with constraint checks on partial solutions.

Use Backtracking with Early Rejection

Backtracking builds the permutation one position at a time. After each placement, you test whether the partial arrangement already violates any rule. If it does, stop exploring that branch.

This is exactly what makes the method practical. A rule like "A cannot be next to B" can often be checked as soon as one of them is placed beside the other, instead of waiting until the entire permutation is complete.

Example Problem

Suppose we want permutations of ["A", "B", "C", "D"] with these rules:

• 'A must appear before C'
• 'B cannot be adjacent to D'
• 'C cannot be in the first position'

A backtracking solver can encode these checks directly.

1def valid_partial(perm):
2    if perm and perm[0] == "C":
3        return False
4
5    if len(perm) >= 2:
6        if (perm[-2], perm[-1]) in {("B", "D"), ("D", "B")}:
7            return False
8
9    if "A" in perm and "C" in perm:
10        if perm.index("A") > perm.index("C"):
11            return False
12
13    return True
14
15
16def generate(items, perm, used, results):
17    if len(perm) == len(items):
18        results.append(perm.copy())
19        return
20
21    for i, item in enumerate(items):
22        if used[i]:
23            continue
24
25        perm.append(item)
26        if valid_partial(perm):
27            used[i] = True
28            generate(items, perm, used, results)
29            used[i] = False
30        perm.pop()
31
32
33items = ["A", "B", "C", "D"]
34results = []
35generate(items, [], [False] * len(items), results)
36
37for r in results:
38    print(r)

This still searches systematically, but it avoids exploring obviously invalid branches.

Different Rule Types Need Different Checks

Not all rules are equally easy to test. A useful classification is:

• position rules, such as "X must be in slot 3"
• adjacency rules, such as "Y cannot follow Z"
• ordering rules, such as "P must appear before Q"
• global rules, such as "the first three positions must contain exactly two vowels"

Position and adjacency rules are excellent for early pruning because they can often be checked immediately. Global rules may need more careful bounding logic to prune effectively before the permutation is complete.

Represent Constraints So They Are Cheap

A common mistake is to write constraint checks that repeatedly scan the whole partial permutation. That is acceptable for small inputs, but it becomes expensive when the search tree is large.

For bigger problems, maintain auxiliary state:

• a used array for membership
• current positions of important symbols
• counters for categories
• predecessor or dependency maps

That turns each pruning step into a small constant-time check instead of a repeated linear scan.

When This Becomes a Constraint-Satisfaction Problem

At some point, the problem is better viewed as a general constraint-satisfaction problem rather than a "permutations" problem. If the rules are complex, techniques such as forward checking, arc consistency, or a CSP solver may outperform handwritten brute-force backtracking.

Still, plain backtracking remains the right first tool for many interview, puzzle, and medium-sized search problems because it is simple and surprisingly effective when pruning is strong.

Common Pitfalls

• Generating every permutation first and filtering later wastes factorial work that pruning could avoid.
• Checking only full permutations misses the main advantage of backtracking, which is early rejection.
• Repeatedly scanning the whole partial arrangement for every rule makes the solver slower than necessary.
• Encoding ordering rules incorrectly can reject valid branches too early or too late.
• Forgetting that some rules interact means a branch may look valid under each rule separately but fail once the rules are combined.

Summary

• The practical way to find valid permutations is backtracking plus early rule checks.
• Strong pruning matters more than clever permutation-generation tricks.
• Position, adjacency, and ordering rules can often be checked on partial permutations.
• For larger or more complex rule sets, treat the problem as a constraint-satisfaction problem and carry more state to prune cheaply.