Перестановки различного размера
Я пытаюсь написать функцию в PHP, которая получает все перестановки всех возможных размеров. Я думаю, что пример будет лучшим способом начать:
$my_array = array(1,1,2,3);
Возможные перестановки различного размера:
1 1 // * см. Примечание 2 3 1,1 1,2 1,3 // И так далее, для всех наборов размера 2 1,1,2 1,1,3 1,2,1 // И так далее, для всех наборов размера 3 1,1,2,3 1,1,3,2 // И так далее, для всех наборов размера 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 элементов, посмотреть, есть ли он уже в массиве результатов, а если нет, добавить его, а затем остановиться, когда математически больше нет возможных перестановок для этой длины., Но это некрасиво и неэффективно с точки зрения ресурсов.
Любые алгоритмы псевдокода будут с благодарностью.
Кроме того, для супер-пупер (бесполезных) бонусных баллов есть ли способ получить всего 1 перестановку с помощью функции, но сделать так, чтобы ей не пришлось пересчитывать все предыдущие перестановки, чтобы получить следующую?
Например, я передаю ему параметр 3, что означает, что он уже сделал 3 перестановки, и он просто генерирует число 4 без повторения предыдущих 3? (Передача этого параметра не обязательна, он может отслеживать глобальный или статический).
Причина, по которой я спрашиваю об этом, заключается в том, что по мере роста массива увеличивается число возможных комбинаций. Достаточно сказать, что один небольшой набор данных, содержащий всего лишь десяток элементов, быстро превращается в триллионы возможных комбинаций, и я не хочу ставить задачу PHP с одновременным хранением триллионов перестановок в своей памяти.
4 ответа
Извините, нет php-кода, но я могу дать вам алгоритм.
Это может быть сделано с небольшими объемами памяти, и так как вы не заботитесь о дуплексах, код также будет простым.
Первый: генерировать все возможные подмножества.
Если вы рассматриваете подмножество как битовый вектор, вы можете видеть, что есть соответствие 1-1 для набора и двоичного числа.
Таким образом, если в вашем массиве 12 элементов, у вас будет 2^12 подмножеств (включая пустой набор).
Таким образом, чтобы создать подмножество, вы начинаете с 0 и продолжаете увеличиваться, пока не достигнете 2^12. На каждом этапе вы читаете установленные биты в числе, чтобы получить соответствующее подмножество из массива.
После того, как вы получили одно подмножество, теперь вы можете пройти через его перестановки.
Следующая перестановка (из индексов массива, а не самих элементов) может быть сгенерирована в лексикографическом порядке, как здесь: http://www.de-brauwer.be/wiki/wikka.php?wakka=Permutations и может быть выполнена с минимальным объем памяти.
Вы должны быть в состоянии объединить эти два, чтобы дать себе функцию next_permutation. Вместо того, чтобы передавать числа, вы можете передать массив из 12 элементов, который содержит предыдущую перестановку, а также, возможно, некоторую дополнительную информацию (снова мало памяти) о том, нужно ли вам перейти к следующему подмножеству и т. Д.
На самом деле вы должны быть в состоянии найти очень быстрые алгоритмы, которые используют минимальное количество памяти, предоставляют функцию типа next_permutation и не генерируют дупликов: поиск в сети для генерации перестановок / комбинаций из нескольких множеств.
Надеюсь, это поможет. Удачи!
Лучший набор функций, которые я придумал, был предоставлен некоторым пользователем в комментариях функции shuffle на php.net. Вот ссылка. Она работает довольно хорошо.
Надеюсь, это полезно.
Кажется, что проблема заключается в попытке дать индекс каждой перестановке и иметь постоянное время доступа. Я не могу думать об алгоритме с постоянным временем, но, возможно, вы можете улучшить этот алгоритм, чтобы быть таковым. Этот алгоритм имеет временную сложность O(n), где n - длина вашего множества. Сложность пространства должна быть сведена к O(1).
Предположим, что наш набор 1,1,2,3, и мы хотим, чтобы 10-я перестановка. Также обратите внимание, что мы будем индексировать каждый элемент набора от 0 до 3. В соответствии с вашим порядком, это означает, что сначала идут перестановки одного элемента, затем два элемента и так далее. Мы будем вычитать из числа 10, пока мы не сможем полностью определить 10-ю перестановку.
Сначала идут перестановки отдельных элементов. Их 4, поэтому мы можем рассматривать это как вычитание одного из четырех раз из 10. У нас осталось 6, поэтому ясно, что нам нужно начать рассматривать перестановки двух элементов. Их 12, и мы можем рассматривать это как вычитание от трех до четырех раз из 6. Мы обнаруживаем, что при втором вычитании 3 у нас остается 0. Это означает, что индексы нашей перестановки должны быть 2 (потому что мы вычитал 3 дважды) и 0, потому что 0 - остаток. Следовательно, наша перестановка должна быть 2,1.
Разделение и модуль могут вам помочь.
Если бы мы искали 12-ю перестановку, мы столкнулись бы со случаем, когда у нас есть остаток от 2. В зависимости от вашего желаемого поведения, перестановка 2,2 может быть недействительной. Обойти это очень просто, однако, поскольку мы можем тривиально обнаружить, что индексы 2 и 2 (не путать с элементом) одинаковы, поэтому второй должен быть увеличен до 3. Таким образом, 12-я перестановка может быть тривиально рассчитывается как 2,3.
Наибольшее заблуждение сейчас заключается в том, что индексы и значения элементов совпадают. Я надеюсь, что мое объяснение алгоритма не слишком запутанное из-за этого. Если это так, я буду использовать набор, отличный от вашего примера и перефразировать вещи.
Входы: индекс перестановки k, индексированное множество S.
псевдокод:
L = {S_1}
for i = 2 to |S| do
Insert S_i before L_{k % i}
k <- k / i
loop
return L
Этот алгоритм также может быть легко модифицирован для работы с дубликатами.