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

Задача
Есть массив элементов, и необходимо вычислить все возможные варианты упорядочения массива.

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

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

Пример 4.6. pc_permute()
function pc_permute($items, $perms = array()) {
if (empty($items)) {
print join(' ', $perms) . "\n";
} 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(split(' ', 'she sells seashells'));
she sells seashells
she seashells sells
sells she seashells
sells seashells she
seashells she sells
seashells sells she

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

Впрочем, функция pc_next_permutation(), показанная в примере 4.7, немного приятнее.


Она объединяет идею Марка-Джейсона Доминуса (Mark-Jason Dominus) из «Perl Cookbook» Тома Кристиансена (Tom Christianson) и Натана Торкингтона (Nathan Torkington) (издательство O’Reilly) с алгоритмом из классического труда Эдсгера Дейкстры(Edsger Dijkstra) «A Discipline of Programming» (издательство PrenticeHall).

Пример 4.7. pc_next_permutation()

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 = split(' ', 'she sells seashells'); // подобно массиву ('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) {
print join(' ', $p) .


"\n";
}

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

Однако этот прием имеет некоторые недостатки. Для нас, программистов на PHP, более важными являются частые извлечения, вставки и
объединения массивов, т. е. то, что для Perl является центральным.

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

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


Едва ли там имеют место хоть какие-то перестановки, даже в последнем цикле перестановки, где переставляется конец.

Метод предоставляет дополнительные преимущества. Рецепт Доминуса требует общего количества перестановок для данного шаблона. Так как оно равно факториалу количества элементов в множестве, то требует довольно больших вычислительных затрат, даже с промежуточным хранением результата. Вместо определения этого числа быстрее вернуть значение false из функции pc_next_permutation(), если окажется, что $i == -1. Когда это происходит, вы вынуждены покинуть массив, исчерпав перестановки данной фразы.

Два последних замечания по реализации. Поскольку размер множества – это константа, то он определяется однажды с помощью функции count() и передается в функцию pc_next_permutation(); это быстрее, чем повторно вызывать функцию count() внутри функции. Кроме того, так как уникальность элементов множества гарантируется самой его
структурой, т. е. в нем одно и только одно вхождение каждого целого числа, то нет необходимости проводить проверку на равенство внутри первых двух циклов for. Однако это нужно делать при использовании этого рецепта для других числовых множеств, где могут встречаться дубликаты..



Оцените статью: (0 голосов)
0 5 0

Статьи из раздела PHP на эту тему:
Добавление одного массива к другому
Изменение длины массива
Инициализация массива диапазоном
Инициализация массива диапазоном целых чисел
Нахождение элемента массива с наибольшим или наименьшим значением

Вернуться в раздел: PHP / 4. Массивы