Нахождение всех перестановок массива

Используйте один из двух алгоритмов перестановки, обсуждаемых далее.

Обсуждение

Функция pc_permute(), приведенная в примере 1 – это PHP модификация базовой рекурсивной функции.

примере 1

function pc_permute($items, $perms = array()) {
    if (empty($items)) {
        echo implode(' ', $perms) . "<br>";
    } else {
        for ($i = count($items) -1; $i >= 0; --$i) {
            $newitems = $items;
            $newperms = $perms;
            list($foo) = array_splice($newitems, $i, 1);
            array_unshift($newperms, $foo);
            pc_permute($newitems, $newperms);
        }
    }
}
pc_permute(explode(' ', 'she sells seashells'));

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

примере 2

function pc_next_permutation($p, $size) {
    // проходим массив сверху вниз в поисках числа, которое меньше следующего
    for ($i = $size - 1; $p[$i] >= $p[$i+1]; --$i) { }
    // если такого нет, прекращаем перестановки
    // массив перевернут: (1, 2, 3, 4) => (4, 3, 2, 1)
    if ($i == -1) { return false; }
    // проходим массив сверху вниз в поисках числа,
    // превосходящего найденное ранее
    for ($j = $size; $p[$j] <= $p[$i]; --$j) { }
    // переставляем их
    $tmp = $p[$i]; $p[$i] = $p[$j]; $p[$j] = $tmp;
    // теперь переворачиваем массив путем перестановки элементов,
    // начиная с конца
    for (++$i, $j = $size; $i < $j; ++$i, --$j) {
        $tmp = $p[$i]; $p[$i] = $p[$j]; $p[$j] = $tmp;
    }
    return $p;
}
$set = explode(' ', 'she sells seashells');
$size = count($set) -1;
$perm = range(0, $size);
$j = 0;
do {
    foreach ($perm as $i) { $perms[$j][] = $set[$i]; }
} while ($perm = pc_next_permutation($perm, $size) and ++$j);
foreach ($perms as $p) {
    echo implode(' ', $p) . "<br>";
}

Идея Доминуса состоит в том, что вместо манипуляций с самим массивом можно создавать перестановки целых чисел. Затем, чтобы получить истинную перестановку, снова ставим в соответствие числам элементы массива – оригинальная мысль. Однако этот прием имеет некоторые недостатки. Для нас, программистов на PHP, более важными являются частые извлечения, вставки и объединения массивов, т. е. то, что для Perl является центральным. Затем процесс вычисления перестановок целых чисел проходит через серию шагов, которые выполняются для каждой перестановки; и поскольку он не запоминает предыдущие перестановки, то каждый раз начинает с исходной перестановки. Зачем работает повторное выполнение, если мы можем помочь ему?