Случайные пары, которые не повторяются

Question

Этот маленький проект / проблема вышел из левого поля для меня. Надеюсь, кто-то может помочь мне здесь. У меня есть некоторые грубые идеи, но я уверен (или, по крайней мере, надеюсь), что существует простое, довольно эффективное решение.

Заранее спасибо .... псевдокод в порядке. Я обычно работаю в .NET / C #, если это проливает свет на ваше решение.

Дано:

Пул из n человек, которые будут встречаться на регулярной основе. Мне нужно сформировать пары, которые ранее не встречались. Пул людей будет медленно меняться со временем. Для целей спаривания (A & B) и (B & A) составляют одну и ту же пару. История предыдущих спариваний сохраняется. Для цели задачи предположим четное число людей. Для каждой встречи (коллекции пар) и отдельных будет пара только один раз.

Есть ли алгоритм, который позволит нам сформировать эти пары? В идеале что-то лучше, чем просто упорядочить пары в случайном порядке, сгенерировать спаривания и затем проверить историю предыдущих спариваний. В целом, случайность внутри спаривания в порядке.

Чуть больше:

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

Answer 1

Исходя из ваших требований, я думаю, что вам действительно нужны квазислучайные числа, которые в конечном итоге приводят к равномерному охвату ваших данных (т. Е. Все объединяются друг с другом один раз).Квазислучайные спаривания дают вам гораздо менее «сгруппированный» результат, чем простые случайные спаривания, с дополнительным преимуществом, состоящим в том, что вы получаете гораздо больший контроль над полученными данными, поэтому вы можете контролировать правило уникальных спариваний, не обнаруживая,рандомизированные пары дублируют исторически рандомизированные пары.

Проверьте эту запись в Википедии:

http://en.wikipedia.org/wiki/Low-discrepancy_sequence

Более хорошее чтение:

http://www.google.com/url?sa=t&source=web&cd=10&ved=0CEQQFjAJ&url=http%3A%2F%2Fwww.johndcook.com%2Fblog%2F2009%2F03%2F16%2Fquasi-random-sequences-in-art-and-integration%2F&ei=6KQXTMSuDoG0lQfVwPmbCw&usg=AFQjCNGQga_MKXJgfEQnQXy1qrHcwfOr4Q&sig2=ox7FB0mnToQbrOCYm9-OpA

Я пытался найти библиотеку C #, которая помогала бы вам генерировать искомые квазислучайные спреды, но единственные библиотеки, которые я мог найти, были в c / c ++.Но я все же рекомендую загрузить исходный код, поскольку там есть полная логика квазислучайных алгоритмов (ищите квази-Монте-Карло ):

http://www.gnu.org/software/gsl/

Answer 2

Интересная идея для преобразования стандартного поиска в выбор вероятности:

• Загрузка истории в структуре с O (1) «содержит» тесты, например, HashSet из (A, B) пар.
• Цикл каждой из 0,5 * n * (n-1) возможных пар
  • проверка, есть ли это спаривание в истории
  • , если нет, переходите к следующей итерации цикла
  • увеличить счетчик "число найдено"
  • сохранить соединение как "результат" с вероятностью 1 / "число найдено" (т. Е. Всегда для первого найденного неиспользованного соединения)
• Наконец, если у «результата» есть ответ, используйте его, иначе все возможности исчерпаны

Это будет выполняться за O (n ^ 2) + O (размер истории), и это приятнообнаруживает случай, когда все вероятности исчерпаны.

Answer 3

Есть ли способ заказать два элемента?Если это так, вы можете сохранить один (возможно, только половину) хэш-тест на каждую итерацию, всегда упорядочивая пару одинаковым образом.Итак, если у вас есть A, B, C и D, сгенерированные возможные пары будут [AB, CD] [AC, BD] или [AD, BC].как:

pair_everyone (pool, pairs, history):
  if pool is empty:
    all done, update global history, return pairs

  repeat for pool_size/2:
    pick element1 (randomly from pool)
    pick element2 (randomly from pool)
    set pair=pair(e1, e2)
    until pair not in history or all possible pairs tried:
      pick element1 (randomly from pool)
      pick element2 (randomly from pool)
      set pair=pair(e1, e2)

    if pair is not in history:
      result=pair_everyone(pool-e1-e2, pairs+pair, history+pair)
      if result != failure:
        return result
    else:
      return failure

Answer 4

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

Это еще не ответ, но есть вероятность, что это обычная проблема графа с известными решениями.

Одна вещь, которую мы можем сказать в этот момент, заключается в том, что в некоторых случаях может не быть решения (вам придется повторить некоторые предыдущие пары).

Также может быть проще рассмотреть двойной граф(обмен ролями вершин и узлов: узлы будут парами и единым человеком между парами вершин).

Answer 5

Сформируйте верхнюю диагональную матрицу с вашими элементами

  Individual   A   B  C  D
           A   * 
           B   *   *
           C   *   *  *
           D   *   *  *  *

Каждый пустой элемент будет содержать True, если пара была сформирована, и False, если нет.

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

При удалении отдельного лица, удалить строку и столбец.

Если производительность является проблемой, вы можете сохранить последнюю пару, сформированную для строки в счетчике, тщательно обновляя ее при удалении

При добавлении лица добавьте последнюю строку & col.

Answer 6

Как насчет:

• создать набор CI всех текущих лиц

, затем:

• случайным образом выбрать одного человека A и удалитьиз CI
• создать новый набор возможных партнеров PP, скопировав CI и удалив всех предыдущих партнеров A
• , если PP пуст, отсканируйте список найденных пар и поменяйте местами A для отдельного C, которыйв паре с кем-то, не входящим в историю А, и у которого все еще есть возможные партнеры по КИ.Пересчитайте PP для A = C.
• , если PP не пустой, выберите одно отдельное B из PP, которое нужно соединить с A
• , удалите B из CI
• , повторяйте, пока не будет новой парыможно найти

Answer 7

Ваша лучшая ставка, вероятно, равна:

1. Загрузить историю в структуре с быстрым доступом, например, HashSet из (A, B) пар.
2. Создание совершенно случайного набора пар (например, путем случайного перемешивания списка лиц и разбиения на соседние пары)
3. Проверьте, есть ли каждое спаривание в истории (должны быть проверены как (A, B), так и (B, A))
4. Если ни одна из пар не найдена, у вас есть совершенно новый набор пар, как требуется, иначе перейдите к 2

Обратите внимание, что шаг 1 можно выполнить один раз и просто обновить при создании новых пар, если вам нужно эффективно создавать большое количество новых уникальных пар.

Также обратите внимание, что вам нужно будет принять некоторые дополнительные меры предосторожности, если есть вероятность того, что все возможные пары будут исчерпаны (в этом случае вам нужно выйти из цикла!)

Answer 8

при запуске создайте список всех возможных пар.

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

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