Я пытаюсь получить доступ к уникальным парам значений из массива в случайном порядке – не повторяясь до тех пор, пока мне не понадобится.
Например, если у меня есть набор массивов A, B, C, D (как правило, четное число элементов, но до 20), то в первый раз через пару я мог бы спрятать AB и CD. Но я хочу гарантировать, что в следующий раз, когда я это сделаю, я избегаю повторения моего спаривания и что у меня есть как AC & BD, так и AD и BC, прежде чем я снова получу AB и CD. Каждый предмет должен вызываться только один раз в каждом раунде.
Я начал с произвольного смешивания порядка массива, затем объединил два значения вместе, но мне нужно, чтобы некоторые пары возникали чаще, чем другие (в идеале я бы хотел, чтобы они постепенно увеличивались одинаково).
Поэтому я перешел к перестановкам – и мне удалось получить полный массив, содержащий все возможные пары, используя следующий код:
$this->items = array('A','B','C','D'); $input = $this->items; $input_copy = $input; $output = array(); $i = 0; foreach($input as $val) { $j = 0; foreach($input_copy as $cval) { if($j == $i) break; print $val.'-'.$cval.'<br/>'; //$output[] = array($val => $cval); $j++; } $i++; } //print_r($output); например, для A, B, C, DI:
ba ca cb da db dc
Я хочу выполнить цикл через n-1 раз и получить результаты в другом массиве, но я не уверен, как создать фактический порядок из этих уникальных опций
Другими словами, я хочу перевернуть список выше:
1st run => 1=> AB, 2=> CD, 2nd run => 1=> AC, 2=> BD, 3rd run => 1=> AD, 2=> CB,
Может быть, я могу сделать это проще всего из $ this-> items. Я также посмотрел на пакет Math_Combinatorics PEAR, но я не был уверен, с чего начать.
Я был бы благодарен за любую помощь!
Вы можете использовать циклический алгоритм турнира
Place elements in two rows. Fix one element - in this case A For next round shift all other elements in circular manner. Pair them. Repeat N-1 times AB DC ----- AD CB ---- AC BD ----
Я предполагаю, что вы хотите генерировать каждое спаривание ровно один раз, т. Е. Каждый раздел всей вашей последовательности попадает в пары. Если вы хотите только каждую пару ровно один раз, это другая проблема, обрабатываемая в другом ответе.
Подумайте об этой проблеме рекурсивно: в начале у вас есть n элементов. Из них возьмите первый и выберите партнера для него из оставшихся элементов n -1. Возьмите эту пару из списка и отбросьте оставшиеся элементы n -2. Если вы сделаете каждый выбор непредвзятым, то оставшееся сопряжение будет также непредвзятым. Но это не гарантирует, что вы не будете повторяться раньше, чем необходимо.
Если вы действительно хотите быть уверены, что избегаете повторения спариваний, сначала вы должны подумать о том, сколько возможных пар. Пока я буду считать, что n четно, поэтому у вас есть только полные пары. Легко настроить это на нечетное n с одним неспаренным элементом. Чтобы получить общее количество возможных спариваний, вам необходимо умножить свой выбор:
m=(n-1)*(n-3)*(n-5)*...*7*5*3*1
Так что это продукт нечетных чисел. Это A001147 , также написанный как двойной факториал m = ( n -1) !!. Обратите внимание, что эти цифры растут довольно быстро, поэтому даже при умеренном n (например, n = 16) вам не придется беспокоиться о повторении себя просто потому, что существует так много возможных пар, чтобы выбрать из этого, что повторение довольно маловероятно.
Если вы действительно хотите быть уверенным в том, что избегаете повторений, вы, конечно, можете просто сгенерировать весь список и перетасовать его. Но, как я только что указал, этот список также может стать огромным . Поэтому вместо этого я предлагаю вам разделить эту проблему на два шага. Найти способ генерации всех чисел от 0 до m -1 каждый раз один раз и найти способ превратить такие числа в пары. Для последнего вы можете просто разложить свой номер шаг за шагом. На каждом шаге возьмите index % (n-1) чтобы сделать текущий выбор, и выберите (int)(index / (n-1)) в качестве индекса для последующих выборов в рекурсивных вызовах.
Для первого, самое легкое, о чем я могу думать, будет использовать PRNG с простым числом p > m в качестве периода. Используя модульную арифметику, это должно быть легко сделать. Затем просто отбросьте все значения, которые больше или равны m . Отбрасывание означает, что вы переходите к следующему элементу в последовательности. Это даст все пары в порядке, который должен казаться довольно случайным. Если начальная точка в этой последовательности должна быть случайной, убедитесь, что если вы сначала выберете значение, которое должно быть отброшено, вам нужно снова инициализировать, а не перейти к следующему элементу. В противном случае некоторые элементы будут более вероятными в качестве отправных точек, чем другие.