Получить все (следующие) подмножества или перестановки (или что-то)

Question

Я не совсем уверен, какое слово использовать здесь, поэтому извините, если я использую неправильную терминологию.

Я пытаюсь создать функцию для получения следующей перестановки строки, содержащей текущую строку и строку допустимых символов.

Например,

<pre>
<?php
$current = '';
$allowed = 'ab';

function next(&$current, &$allowed) {
    // This is where I need help
}

echo next($current, $allowed) . "\n";
echo next($current, $allowed) . "\n";
echo next($current, $allowed) . "\n";
echo next($current, $allowed) . "\n";
echo next($current, $allowed) . "\n";
echo next($current, $allowed) . "\n";
echo next($current, $allowed) . "\n";
echo next($current, $allowed) . "\n";
echo next($current, $allowed) . "\n";
echo next($current, $allowed) . "\n";
echo next($current, $allowed) . "\n";
echo next($current, $allowed) . "\n";
echo next($current, $allowed) . "\n";
echo next($current, $allowed) . "\n";
echo next($current, $allowed) . "\n";

Должно возвращаться

a
b
aa
ab
ba
bb
aaa
aab
aba
abb
baa
bab
bba
bbb
aaaa

... и т. д.

Я пытаюсь сделать это как на PHP, так и на JavaScript, поэтому буду благодарен за помощь на любом языке.

Answer 1

function nextPermutation(&$current, $allowed) {
    if (empty($current)) {
        $current = $allowed[0];
    } else {
        for ($i = strlen($current) - 1; $i >= 0; $i--) {
            $index = strpos($allowed, $current[$i]);
            if ($index < strlen($allowed) - 1) {
                $current[$i] = $allowed[$index + 1];
                break;
            } else {
                $current[$i] = $allowed[0];
                if ($i == 0) {
                    $current = $allowed[0] . $current;
                    break;
                }
            }
        }
    }
    return $current;
}