Перестановки различного размера

Question

Я пытаюсь написать функцию в 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 элементов, видя, есть ли он уже в массиве результатов, а если нет, добавьте его, а затем остановите, когда математически больше нет возможных перестановок для этой длины.Но это уродливо и неэффективно с точки зрения ресурсов.

Любые алгоритмы псевдокодов будут высоко оценены.

---

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

Например, я передаю ему параметр 3, что означает, что он уже сделал 3 перестановки, и он просто генерирует число 4 без повторения предыдущих 3?(Передача этого параметра не обязательна, он может отслеживать глобальное или статическое значение).

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

Answer 1

Извините, нет php-кода, но я могу дать вам алгоритм.

Это можно сделать с небольшими объемами памяти, и, поскольку вы не заботитесь о дублировании, код также будет простым.

Первый: генерировать все возможные подмножества.

Если вы просматриваете подмножество как битовый вектор, вы можете видеть, что существует соответствие 1-1 для набора и двоичное число.

Таким образом, если в вашем массиве было 12 элементов, у вас будет 2 ^ 12 подмножеств (включая пустой набор).

Итак, чтобы сгенерировать подмножество, вы начинаете с 0 и продолжаете увеличиваться, пока не достигнете 2 ^ 12.На каждом этапе вы читаете установленные биты в числе, чтобы получить соответствующее подмножество из массива.

После того, как вы получили одно подмножество, теперь вы можете выполнить его перестановки.

Следующая перестановка (из индексов массива, а не самих элементов) могут быть сгенерированы в лексикографическом порядке, как здесь: http://www.de -brauwer.be / wiki / wikka.php? wakka = Permutations и могут быть выполнены с минимальным объемом памяти.

Вы должны быть в состоянии объединить эти два, чтобы дать себе функцию next_permutation.Вместо того, чтобы передавать числа, вы можете передать массив из 12 элементов, который содержит предыдущую перестановку, плюс, возможно, некоторую дополнительную информацию (снова мало памяти) о том, нужно ли вам перейти к следующему подмножеству и т. Д.

Вына самом деле должен быть в состоянии найти очень быстрые алгоритмы, которые используют минимальное количество памяти, предоставляют функцию типа next_permutation и не генерируют дупликов: поиск в Интернете для поиска перестановок / комбинаций из нескольких множеств.

Надеюсь, что это поможет.Удачи!

Answer 2

Лучший набор функций, которые я придумал, был предоставлен некоторым пользователем в комментариях функции shuffle на php.net. Вот ссылка Она работает довольно хорошо.

Надеюсь, это полезно.

Answer 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

Этот алгоритм также можно легко изменить для работы с дубликатами.

Answer 4

Кажется, проблема в том, чтобы пытаться дать индекс каждой перестановке и иметь постоянное время доступа.Я не могу думать об алгоритме с постоянным временем, но, возможно, вы можете улучшить этот алгоритм, чтобы быть таковым.Этот алгоритм имеет временную сложность 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.

Самое большое заблуждение сейчас заключается в том, что индексы и значения элементов совпадают.Я надеюсь, что мое объяснение алгоритма не слишком запутанное из-за этого.Если это так, я буду использовать набор, отличный от вашего примера, и перефразировать вещи.