Я пытаюсь написать функцию на PHP, которая получает все перестановки всех возможных размеров. Я думаю, что лучший способ начать с примера:
$my_array = array(1,1,2,3);
Возможные перестановки разного размера:
1 1 // * See Note 2 3 1,1 1,2 1,3 // And so forth, for all the sets of size 2 1,1,2 1,1,3 1,2,1 // And so forth, for all the sets of size 3 1,1,2,3 1,1,3,2 // And so forth, for all the sets of size 4
Примечание: мне все равно, есть дубликат или нет. Для целей этого примера все будущие дубликаты опущены.
Что у меня есть в PHP:
function getPermutations($my_array){
$permutation_length = 1;
$keep_going = true;
while($keep_going){
while($there_are_still_permutations_with_this_length){
// Generate the next permutation and return it into an array
// Of course, the actual important part of the code is what I'm having trouble with.
}
$permutation_length++;
if($permutation_length>count($my_array)){
$keep_going = false;
}
else{
$keep_going = true;
}
}
return $return_array;
}
Самое близкое, что я могу придумать, - это перетасовать массив, выбрать первые n элементов, посмотреть, есть ли он уже в массиве результатов, а если нет, добавить его, а затем остановиться, когда математически больше нет возможных перестановок для этой длины . Но это некрасиво и неэффективно.
Приветствуются любые алгоритмы псевдокода.
Кроме того, для супер-пуперских (бесполезных) бонусных очков, есть ли способ получить только одну перестановку с функцией, но сделать так, чтобы ей не приходилось пересчитывать все предыдущие перестановки, чтобы получить следующую?
Например, я передаю ему параметр 3, что означает, что он уже сделал 3 перестановки, и он просто генерирует номер 4 без повторения предыдущих 3? (Передавать ему параметр не обязательно, его можно отслеживать в глобальном или статическом виде).
Я спрашиваю об этом потому, что по мере роста массива увеличивается и количество возможных комбинаций. Достаточно сказать, что один небольшой набор данных всего с дюжиной элементов быстро разрастается до триллионов возможных комбинаций, и я не хочу ставить перед PHP задачу одновременного удержания в своей памяти триллионов перестановок.
