Доступ к уникальным парам значений из массива без повторения
Я пытаюсь получить доступ уникальный пары значений из массива в случайном порядке — без повторения, пока не придется.
Например, если у меня есть набор массивов A, B, C, D (как правило, четное количество элементов, но не более 20), то в первый раз я мог бы соединить A-B & CD. Но я хочу гарантировать, что в следующий раз, когда я это сделаю, я избегу повторения парного соединения и получу как A-C & B-D и A-D и B-C, прежде чем я снова получу A-B и C-D. Каждый предмет должен вызываться только один раз в каждом раунде.
Я начал с случайного перемешивания порядка массива, затем связал два значения вместе — но мне нужен способ, чтобы некоторые пары не встречались чаще, чем другие (в идеале я бы хотел, чтобы они увеличивались одинаково на всем протяжении).
Поэтому я перешел к рассмотрению перестановок — и сумел получить полный массив, содержащий все возможные пары, используя код ниже:
$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, D я получаю:
b-a
c-a
c-b
d-a
d-b
d-c
Я хочу циклически проходить через набор n-1 раз и захватывать результаты в другом массиве, но я не уверен, как сгенерировать фактический порядок из этих уникальных опций
Другими словами, я хочу превратить приведенный выше список в следующий:
1st run =>
1=> A-B,
2=> C-D,
2nd run =>
1=> A-C,
2=> B-D,
3rd run =>
1=> A-D,
2=> C-B,
Может быть, я могу сделать это более просто из $ this-> items. Я также посмотрел на пакет PEAR Math_Combinatorics, но я не был уверен, с чего начать.
Буду благодарен за любую помощь!
Решение
Ты можешь использовать алгоритм кругового турнира
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
A B
D C
-----
A D
C B
----
A C
B D
----
Другие решения
Я предполагаю, что вы хотите создать каждый спаривание ровно один раз, то есть каждое разбиение всей вашей последовательности на пары. Если вы хотите, чтобы каждая пара была только один раз, это другая проблема, решаемая в другом ответе.
Подумайте об этой проблеме рекурсивно: в начале у вас есть N элементы. Из них возьмите первого и выберите партнера для него из оставшихся N-1 элемент. Уберите эту пару из списка и откажитесь от остальных N-2 элемента. Если вы сделаете каждый выбор беспристрастным, оставшееся соединение будет также беспристрастным. Но это не гарантирует, что вы не будете повторяться раньше, чем необходимо.
Если вы действительно хотите быть уверенным, что избегаете повторения пар, сначала подумайте о том, сколько существует возможных пар. Сейчас я предполагаю, что N является четным, поэтому у вас есть только полные пары. Легко настроить это на нечетное N с одним непарным элементом. Чтобы получить общее количество возможных пар, вам нужно умножить свой выбор:
m=(n-1)*(n-3)*(n-5)*...*7*5*3*1
Так что это произведение нечетных чисел. Это A001147, также написано как двойной факториал мзнак равноN-1) !!. Обратите внимание, что эти цифры растут довольно быстро, поэтому даже для умеренных N (лайк N= 16) вам, возможно, не придется беспокоиться о повторении себя просто потому, что существует так много возможных комбинаций, что повторение довольно маловероятно.
Если вы действительно хотите быть конечно что вы избегаете повторений, вы, конечно, можете просто сгенерировать весь список и перемешать его. Но, как я только что указал, этот список может стать огромный также. Поэтому вместо этого я бы предложил вам разделить эту проблему на два этапа. Найдите способ генерировать все числа от 0 до м-1 каждый ровно один раз, и найдите способ превратить такие числа в пары. Для последнего, вы можете просто разложить ваш номер шаг за шагом. На каждом шаге index % (n-1) сделать текущий выбор и выбрать (int)(index / (n-1)) в качестве индекса для последующих выборов в рекурсивных вызовах.
Для первого из них проще всего было бы использовать PRNG с простым числом п>м как его период. Используя модульную арифметику, это должно быть легко сделать. Затем просто отбросьте все значения, которые больше или равны м. Сбрасывание означает, что вы переходите к следующему элементу в последовательности. Это даст все пары в порядке, который должен казаться довольно случайно. Если начальная точка в этой последовательности должна быть случайной, убедитесь, что если вы сначала выберете значение, которое следует отбросить, то вам придется заново инициализировать, а не переходить к следующему элементу. В противном случае некоторые элементы будут более вероятными в качестве отправных точек, чем другие.