Last active
June 20, 2021 11:19
-
-
Save esase/564c47038e4d24ecdf69f0b5832de320 to your computer and use it in GitHub Desktop.
Next permutation [algorithm]
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
<?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 />'; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment