Нахождение всех перестановок на PHP в функциональном стиле

Во время недавнего гугления по какому-то поводу попалась мне на глаза заметка, в которой автор приводил реализацию алгоритма получения всех перестановок (permutations) на PHP. Видимо, по той причине, что обработка входного массива выполнялась "по месту", что существенно экономило память,  реализация алгоритма получилась весьма витиеватой. То есть, чтобы разобраться, как он работает, пришлось натурально браться за ручку и бумагу ))

И вот задумался я, а можно ли как-то все это реализовать в более понятном ключе ?....


Ведь что такое множество перестановок для некоторого массива размерности N ? Алгоритм его получения можно условно представить таким псевдокодом:

Функция ВсеПерестановки(ВходнойМассив)
       Результат = ПустойМассив();
       Цикл по I от 1 до РазмерВходногоМассиваN
             ПромежуточныйМассив = ВходнойМассив за вычетом элемента с индексом I;
             ПромежуточныеПерестановки = ВсеПерестановки(ПромежуточныйМассив);
             Цикл ПромежуточныеПерестановки как Перестановка
                       Перестановка = ЭлементВходногоМассива с индексом I + Перестановка; 
             КонецЦикла;
             Результат = Результат + ПромежуточныеПерестановки;
       КонецЦикла;
       Вернуть Результат;
КонецФункции;

То есть, налицо рекурсивный алгоритм, где каждое решение для массива размерности N основывается на решении задачи для массива размерности N-1. Для того, чтобы получить решение для массива размерности N,  нужно для каждого элемента этого массива выполнить следующие действия: получить промежуточный массив, который не содержит этого элемента
(размерность этого массива будет на 1 меньше), затем вызвать рекурсивно нашу функцию ВсеПерестановки() для этого промежуточного массива меньшей размерности, к полученным результатам функции "доклеить" в самое начало тот элемент, который мы удаляли из входного массива на первом шаге, а затем обработанный таким образом результат добавить для накопления в аккумулятор, значение которого будет возвращено по выходу из функции.

На мой взгляд, алгоритмически это решение весьма несложное для понимания. Попробуем реализовать этот алгоритм на PHP, применяя, по возможности, функциональный подход :)
Вот что получилось у меня:

===
function permutations($input) {
    if (count($input) <= 1) return array($input);
    $result = array();  
    foreach ($input as $v) {
          $reduce = array_filter($input,
                                 function ($e) use($v) { return $e !== $v; }
                    );
          $result = array_merge( $result, 
                        array_map(
                             function ($e) use ($v) { array_unshift( $e, $v); return $e; },
                             permutations( $reduce )
                        )
                    );
    }
    return $result;
}===
Вызов функции выглядит следующим образом:

$input = range(1, 5, 1);
$result = permutations($input);

Первый вызов - range() - возвращает нам массив, заполненный числам от 1 до 5 подряд.
Тут важный момент - все элементы массива должны быть различны, поэтому если вам нужно формировать перестановки для массива, в котором есть дубликаты, вы можете сформировать
массив индексов, как указано выше, получить перестановки для него, а потом использовать полученный результат для индексации оригинального массива.

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

Теперь давайте разберем, как работает permutations(). Она всегда возвращает массив массивов (даже для одного элемента). Это сделано специально, чтобы чуть упростить обработку результатов вложенного вызова самой себя. Итак, если на входе у нас пустой массив или массив, состоящий из одного элемента, мы возвращаем его же, но упакованным в массив.
То есть, на входе array(5), на выходе - array ( array (5) ).
Если же массив имеет более одного элемента, мы выполняем следующее: для каждого элемента $v массива мы формируем при помощи array_filter() промежуточный массив $reduce, который содержит все элементы входного массива за исключением этого элемента $v. После этого, мы вызываем permutations() для массива $reduce. Полученный результат обрабатываем при помощи array_map(), которая к каждому элементу массива перестановок добавляет в начало
элемент $v функцией array_unshift(). Далее, мы просто накапливаем полученные таким образом результаты в массиве $result, и после прохода по всему массиву $input возвращаем $result.
Все достаточно очевидно. Так как permutations() использует анонимные функции, то
требуется PHP версии не ниже 5.3 (это ограничение обходится написанием внешних функций, которые будут подаваться как callback в те же array_map() или array_filter().
 
Конечно, у такого подхода есть большой минус - он весьма "жруч" в плане памяти. Объясняется это, как минимум тем, что и array_map(), и array_merge(), и array_filter() в результате своей работы формируют новые массивы (функциональная иммутабельность! =)) Плюс еще и невозможность явно освобождать память в процессе работы. Я пытался вызывать внутри цикла unset(), но пользы это не принесло, к сожалению.
В общем, при попытке вызвать permutations() для входного массива, содержащего 10 элементов
(чуть более 3 с половиной миллионов перестановок), вываливается сообщение о нехватке ОЗУ:
==
Fatal error: Allowed memory size of 134217728 bytes exhausted (tried to allocate 36 bytes)
==
Так что функцию можно применять либо как учебную, либо на массивах весьма ограниченной размерности.

Вот, пожалуй, и все на данный момент.

Дополнение. 

Кстати, проверив работу функции, о которой я писал в самом начале этого поста, на размерности 10 элементов, я получил то же сообщение о нехватке памяти.  То есть, проблема, в первую очередь, определяется не тем, что array_* функции иммутабельны и в PHP нет явного управления выделением и освобождением памяти,  а тем, что все перестановки накапливаются в одном результирующем массиве, и уже этот массив целиком подается на выход функции permutations(). Решением проблемы может стать использование генераторов в PHP, которые появились в версии 5.5. То есть, вместо накопления результатов в массиве $result можно будет выдавать наверх каждую отдельную перестановку вызовом yield. По идее, это должно работать. Для более ранних версий PHP можно предусмотреть явный вызов из permutations() некоторой callback-функции с передачей в неё последней полученной перестановки  как параметра. Это, конечно, будет не так изящно, как использование генератора, но тоже вполне приемлемо.