Question

How to generate all possible permutations and combinations of an array of chars in PHP

Answer 1

function printPermutations(array $items): void {
    $perms = permutations($items);
    foreach ($perms as $p) {
        echo implode(" ", $p) . PHP_EOL;
    }
}
 
function printCombinations(array $items): void {
    $size = count($items);
    for ($i = 1; $i <= $size; $i++) {
        foreach (combinations($items, $i) as $ch) {
            echo implode(" ", $ch) . PHP_EOL;
        }
    }
}
 
// Generate all permutations recursively
function permutations(array $items): array {
    if (count($items) <= 1) {
        return [$items];
    }
 
    $result = [];
    foreach ($items as $i => $item) {
        $rest = $items;
        unset($rest[$i]);
        foreach (permutations(array_values($rest)) as $perm) {
            array_unshift($perm, $item);
            $result[] = $perm;
        }
    }
 
    return $result;
}
 
// Generate all combinations of given length
function combinations(array $items, int $pos): array {
    if ($pos === 0) {
        return [[]];
    }
    if (empty($items)) {
        return [];
    }
 
    $result = [];
    $first = array_shift($items);
 
    // Include first
    foreach (combinations($items, $pos - 1) as $combo) {
        array_unshift($combo, $first);
        $result[] = $combo;
    }
 
    // Exclude first
    foreach (combinations($items, $pos) as $combo) {
        $result[] = $combo;
    }
 
    return $result;
}
 
$input = ['a', 'b', 'c'];
 
echo "All permutations:" . PHP_EOL;
printPermutations($input);
 
echo PHP_EOL . "All combinations:" . PHP_EOL;
printCombinations($input);

         
         
/*
run:
  
All permutations:
a b c 
a c b 
b a c 
b c a 
c b a 
c a b 
 
All combinations:
a 
b 
a b 
c 
a c 
b c 
a b c 
  
*/

 

70+ SQL courses for beginners and professionals

Answer 2

// Generate all permutations recursively
function permutations(array $items): array {
    if (count($items) <= 1) {
        return [$items];
    }

    $result = [];
    foreach ($items as $i => $item) {
        $rest = $items;
        unset($rest[$i]);
        foreach (permutations(array_values($rest)) as $perm) {
            array_unshift($perm, $item);
            $result[] = $perm;
        }
    }
    
    return $result;
}

// Generate all combinations of given length
function combinations(array $items, int $pos): array {
    $size = count($items);
    $result = [];

    // Iterate over all bitmasks from 1 to 2^$size - 1
    for ($mask = 1; $mask < (1 << $size); $mask++) {
        $combo = [];
        for ($i = 0; $i < $size; $i++) {
            if ($mask & (1 << $i)) {
                $combo[] = $items[$i];
            }
        }
        // Only keep combinations of size $pos
        if (count($combo) === $pos) {
            $result[] = $combo;
        }
    }

    return $result;
}

function printPermutations(array $items): void {
    foreach (permutations($items) as $p) {
        echo implode(" ", $p) . PHP_EOL;
    }
}

function printCombinations(array $items): void {
    $size = count($items);
    for ($i = 1; $i <= $size; $i++) {
        foreach (combinations($items, $i) as $ch) {
            echo implode(" ", $ch) . PHP_EOL;
        }
    }
}

$input = str_split("abc");

echo "All permutations:" . PHP_EOL;
printPermutations($input);

echo PHP_EOL . "All combinations:" . PHP_EOL;
printCombinations($input);

        
        
/*
run:
 
All permutations:
a b c
a c b
b a c
b c a
c a b
c b a

All combinations:
a
b
c
a b
a c
b c
a b c
 
*/

 

70+ SQL courses for beginners and professionals