Introduction

Generating all permutations of a string in PHP is a classic recursion exercise, but practical implementations need to handle duplicate characters, memory pressure, and runtime growth. The number of permutations grows factorially, so algorithm choice matters as input length increases. A clean implementation starts with correctness, then adds deduplication and iteration strategies.

Recursive Baseline for Unique Characters

If all characters are distinct, a recursive swap or prefix method is straightforward. The function below returns every permutation as a list.

1<?php
2function permutations(string $s): array {
3    $len = strlen($s);
4    if ($len <= 1) {
5        return [$s];
6    }
7
8    $result = [];
9    for ($i = 0; $i < $len; $i++) {
10        $ch = $s[$i];
11        $rest = substr($s, 0, $i) . substr($s, $i + 1);
12
13        foreach (permutations($rest) as $p) {
14            $result[] = $ch . $p;
15        }
16    }
17
18    return $result;
19}
20
21print_r(permutations("abc"));

This is easy to understand and test. It is a good baseline for interviews and small inputs.

Handle Duplicate Characters Correctly

If the input contains repeated characters, naive recursion returns duplicates. You can deduplicate after generation, but it wastes time and memory. Better approach is pruning duplicates during recursion.

1<?php
2function uniquePermutations(string $s): array {
3    $chars = str_split($s);
4    sort($chars);
5    $used = array_fill(0, count($chars), false);
6    $result = [];
7
8    $backtrack = function(array $path) use (&$backtrack, &$result, &$used, $chars): void {
9        if (count($path) === count($chars)) {
10            $result[] = implode("", $path);
11            return;
12        }
13
14        for ($i = 0; $i < count($chars); $i++) {
15            if ($used[$i]) {
16                continue;
17            }
18            if ($i > 0 && $chars[$i] === $chars[$i - 1] && !$used[$i - 1]) {
19                continue;
20            }
21
22            $used[$i] = true;
23            $path[] = $chars[$i];
24            $backtrack($path);
25            array_pop($path);
26            $used[$i] = false;
27        }
28    };
29
30    $backtrack([]);
31    return $result;
32}
33
34print_r(uniquePermutations("aab"));

This avoids repeated output while preserving lexicographic order.

Use a Generator for Memory Efficiency

Returning all permutations as one array can exhaust memory for larger inputs. A generator yields values one by one.

1<?php
2function permuteGenerator(string $prefix, string $rest): Generator {
3    if ($rest === "") {
4        yield $prefix;
5        return;
6    }
7
8    $len = strlen($rest);
9    for ($i = 0; $i < $len; $i++) {
10        $ch = $rest[$i];
11        $next = substr($rest, 0, $i) . substr($rest, $i + 1);
12        yield from permuteGenerator($prefix . $ch, $next);
13    }
14}
15
16foreach (permuteGenerator("", "abcd") as $p) {
17    echo $p, PHP_EOL;
18}

This pattern is useful when permutations feed a search pipeline and you can stop early after the first matching candidate.

Complexity and Practical Limits

For n unique characters, count is n!. Even 10! is already very large. Plan safeguards:

• reject inputs above a chosen threshold
• stream results with generators
• stop early if a downstream condition is satisfied

You can estimate expected count first:

1<?php
2function factorial(int $n): int {
3    $f = 1;
4    for ($i = 2; $i <= $n; $i++) {
5        $f *= $i;
6    }
7    return $f;
8}
9
10echo factorial(8), PHP_EOL;

Testing for Correctness

Add quick assertions:

• expected count for unique input
• no duplicates for repeated-character input
• deterministic ordering if required

1<?php
2$out = uniquePermutations("aab");
3sort($out);
4assert($out === ["aab", "aba", "baa"]);

Small tests catch most logic errors before performance tuning begins.

Common Pitfalls

• Generating all permutations into memory when streaming would suffice.
• Ignoring duplicate-character pruning and returning repeated strings.
• Forgetting factorial growth and allowing unbounded input length.
• Mixing multibyte text with byte-based indexing functions.
• Benchmarking on tiny strings and assuming behavior scales linearly.

Summary

• Start with recursive correctness, then optimize for duplicates and memory.
• Use sorted characters plus visited tracking to avoid duplicate output.
• Prefer generators when consumers process permutations incrementally.
• Add input-size guardrails because factorial growth is steep.
• Validate behavior with small deterministic tests before scaling.