Тасование с ограничениями на пары

Question

У меня есть n списки длиной m. предположим, что n*m является четным. я хочу получить случайно перемешанный список со всеми элементами, при условии, что элементы в местах i,i+1, где i=0,2,...,n*m-2 никогда не приходят из одного и того же списка. редактировать: кроме этого ограничения я не хочу смещать распределение случайных списков. то есть решение должно быть эквивалентно полному случайному выбору, который переставляется до тех пор, пока не выполнится ограничение.

пример:

list1: a1, a2

список2: b1, b2

list3: c1, c2

разрешено: b1, c1, c2, a2, a1, b2

запрещено: b1, c1, c2, b2, a1, a2

Answer 1

Очень быстрый и простой метод, который я пробую:

random shuffle
loop over the pairs in the list:
   if pair is bad:
   loop over the pairs in the list:
      if both elements of the new pair are different than the bad pair:
         swap the second elements
         break

это всегда найдет решение? будут ли решения иметь то же распределение, что и наивные перетасовки, до тех пор, пока не будет найдено законное решение?

Answer 2

Вариант b выше, который позволяет избежать тупиков: на каждом шаге вы выбираете дважды. Сначала случайно выбрал предмет. Во-вторых, случайным образом выберите, где его разместить. На K-м шаге есть k дополнительных мест для размещения предмета (новый предмет может быть вставлен между двумя существующими предметами). Естественно, вы выбираете только из разрешенных мест. Деньги!

Answer 3

1. организовать ваши списки в список списков
2. сохранить каждый элемент в списке как кортеж с индексом списка в списке списков
3. петля n * m раз
4. на четных поворотах - сведите в один список и просто раздайте поп-арт - вы получите предмет и группу предметов
5. на нечетных ходах - временно удалить последнюю группу предметов и выскочить, как и раньше - в конце добавить удаленную группу обратно

важно - как избежать тупиков?

может возникнуть тупик, если все остальные предметы принадлежат только к одной группе.
чтобы избежать этого, проверяйте в каждой итерации длины всех списков
и проверить, длиннее ли список, чем сумма всех остальных .
если true - получить этот список

таким образом, вам никогда не останется только один полный список

---

вот суть с попыткой решить это в python https://gist.github.com/YontiLevin/bd32815a0ec62b920bed214921a96c9d

Answer 4

Возможное решение состоит в том, чтобы думать о вашем числе, установленном как n кусков элемента, каждый кусок имеет длину m. Если вы случайным образом выберете для каждого блока по одному элементу из каждого списка, то вы никогда не попадете в тупик. Просто убедитесь, что первый элемент в каждом чанке (кроме первого чанка) будет иметь список, отличный от последнего элемента предыдущего чанка.

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

Наконец, еще одно возможное решение состоит в том, чтобы последовательно рандомизировать число в каждой позиции, но только из тех, которые «могут быть помещены туда», то есть, если вы введете число, ни одно из ограничений не будет нарушено, то есть у вас будет хотя бы возможное решение.