Next permutation [algorithm]

next_permutation.php

<?php

// https://www.nayuki.io/page/next-lexicographical-permutation-algorithm
/**
 * Find a next array permutation
 * 
 * @param array $input
 * @return boolean
 */
function nextPermutation(&$input)
{
	$inputCount = count($input);

	// the head of the suffix
	$i = $inputCount - 1;

	// find longest suffix
	while ($i > 0 && $input[$i] <= $input[$i - 1]) {
		$i--;
	}

	//are we at the last permutation already?
	if ($i <= 0) {
		return false;
	}

	// get the pivot
	$pivotIndex = $i - 1;

	// find rightmost element that exceeds the pivot
	$j = $inputCount - 1;
	while ($input[$j] <= $input[$pivotIndex]) {
		$j--;
	}
		
	// swap the pivot with j
	$temp = $input[$pivotIndex];
	$input[$pivotIndex] = $input[$j];
	$input[$j] = $temp;

	// reverse the suffix
	$j = $inputCount - 1;

	while ($i < $j) {
	        $temp = $input[$i];
	        $input[$i] = $input[$j];
	        $input[$j] = $temp;

	        $i++;
	        $j--;
	}

	return true;
}

// tests
$testCases = [
    [
        'input' => [0, 1, 2, 5, 3, 3, 0],
        'expect' => [0, 1, 3, 0, 2, 3, 5],
    ],
	[
        'input' => ['a', 'b'],
        'expect' => ['b', 'a'],
    ],
	[
        'input' => ['b', 'b'],
        'expect' => ['b', 'b'],
    ]
];

foreach ($testCases as $case) {
	nextPermutation($case['input']);

    if ($case['expect'] == $case['input']) {
        echo '<span style="color:green">passed:</span> ' . implode(' ', $case['expect']) . ' == ' . implode(' ', $case['input']);
    }
    else {
        echo '<span style="color:red">failed:</span> ' . implode(' ', $case['expect']) . ' <> ' . implode(' ', $case['input']);
    }

    echo '<br />';
}