Permutations - all possible sets of numbers

Permutations - all possible sets of numbers

  1. Blog
  2. 15 November 2026
  3. 3 min read

Stefan Bogdanescu

Founder & Senior Architect

Generating Permutations in PHP: Theory and Implementation

When you are asked to generate all possible sets of numbers where each number appears exactly once, you are dealing with permutations. Specifically, for a set of $n$ distinct elements, the total count is calculated using the factorial function ($n!$). For your specific case involving numbers 0 through 8, $n=9$. The calculation is straightforward: $9 \times 8 \times 7 \times 6 \times 5 \times 4 \times 3 \times 2 \times 1$, which equals 362,880. This number dictates the memory and CPU budget required for any solution; you cannot simply store all results in an array if you are processing millions of rows in a database, but it is trivially manageable for modern PHP environments handling this specific scale.

The mathematical logic behind why this works relies on the fundamental principle of counting. You have 9 slots to fill. The first slot can be any of the 9 numbers. Once chosen, 8 remain for the second slot. Then 7, and so on. If you were arranging items where order didn't matter, you would divide by $n!$ to get combinations, but your examples clearly show that 0-1-2... is distinct from 0-1-3..., confirming you need permutations.

To implement this in PHP without relying on external libraries like the symfony/contracts or iter-tools, a recursive backtracking approach is often the most memory-efficient for generating these sequences one by one. This method builds a partial permutation, tracks which numbers have been used via a boolean mask or a checked array, and swaps elements to explore different orders.

Here is a practical implementation using an iterative swap-based algorithm. This avoids deep recursion stack overhead and allows you to iterate through the full set of 362,880 permutations without storing them all in memory simultaneously:

<?php

function getPermutations(array $items): array {
    $n = count($items);
    $permutations = [];
    
    // Start with the sorted array as the base state
    $current = $items;
    $visitedCount = 0;
    $totalPermutations = factorial($n);

    while ($visitedCount < $totalPermutations) {
        $permutations[] = $current;
        
        // Find the rightmost index i such that current[i] > current[i-1]
        // Actually, for standard next_permutation logic:
        // 1. Find largest i where arr[i] < arr[i+1]
        $i = $n - 2;
        while ($i >= 0 && $current[$i] >= $current[$i + 1]) {
            $i--;
        }

        if ($i < 0) {
            // We have reached the last permutation, reset to first
            $permutations = []; 
            sort($current);
            continue;
        }

        // Find largest j such that arr[j] > arr[i]
        $j = $n - 1;
        while ($current[$j] <= $current[$i]) {
            $j--;
        }

        // Swap current[i] and current[j]
        $temp = $current[$i];
        $current[$i] = $current[$j];
        $current[$j] = $temp;

        // Reverse the sequence from i+1 to end
        reverseArray($current, $i + 1);
        
        $visitedCount++;
    }

    return $permutations;
}

function factorial(int $n): int {
    $result = 1;
    for ($i = 2; $i <= $n; $i++) {
        $result *= $i;
    }
    return $result;
}

function reverseArray(array &$arr, int $start): void {
    $end = count($arr) - 1;
    while ($start < $end) {
        // Note: Since input is 0-8, we assume standard integer comparison works fine.
        // If dealing with large integers, ensure they fit in standard types.
        $temp = $arr[$start];
        $arr[$start] = $arr[$end];
        $arr[$end] = $temp;
        $start++;
        $end--;
    }
}

// Usage
$numbers = range(0, 8);
$results = getPermutations($numbers);

// Print first 5 for verification
foreach (array_slice($results, 0, 5) as $perm) {
    echo implode('-', $perm) . PHP_EOL;
}

The core of this solution lies in the "next permutation" algorithm. Instead of recursively building paths, which creates a tree structure in memory, this method mutates an array to generate the lexicographically next sequence. This is highly efficient for streaming results. If you need to print every single line, outputting directly inside the loop rather than collecting into an array prevents memory exhaustion on larger datasets.

In a Laravel application context, you might find this pattern useful when generating test data or creating complex combinatorial fixtures. While Laravel does not have a native permutations helper in its core collection facade, you can wrap this logic in a service class if you need to reuse the generator across multiple controllers or jobs. Remember that if $n$ grows beyond 20, the factorial explodes, and you must switch strategies to process permutations lazily or in chunks to avoid crashing the web server.

Our network