Алгоритм экспресс-знакомства

вот идея
первая работа от первого лица .. назовем его X
X должен встретиться со всеми другими людьми в комнате, поэтому мы должны разделить оставшихся людей на n групп (где n = # _of_people / capacity_per_table) и заставить его сесть с одной из этих групп на итерацию
Теперь, когда о X позаботились, мы рассмотрим следующего человека Y
WLOG Y должен быть человеком, с которым X должен был сидеть в самой первой итерации ... так что мы уже знаем группу таблицы Y для этого временного интервала ... затем мы должны разделить оставшихся людей на группы так, чтобы каждая группа сидела с Y для каждого последующего итерация .. и для каждой итерации группа X и группа Y не имеют общего лица
.. Я полагаю, если вы продолжите делать что-то подобное, вы получите оптимальное решение (если оно существует)

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

Почему бы не имитировать реальный мир?

class Person { 
    void doPeriodically() {
         do {
             newTable = random (numberOfTables);
         } while (tableBusy(newTable))
         switchTable (newTable) 
    }
}

Да, и обратите внимание, что существует аналогичный алгоритм для поиска партнера для спаривания, и, по слухам, он эффективен для тех 99% людей, которые этого не делают. проводить все свободное время, отвечая на вопросы по программированию ...

Perfect Table Plan

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

Вы можете ознакомиться с комбинаторной теорией проектирования .

Вы также можете взглянуть на проблему стабильного сопоставления. Решение этой проблемы предполагает использование алгоритма максимального потока. http://en.wikipedia.org/wiki/Stable_marriage_problem

Я бы не стал беспокоиться о генетических алгоритмах. Вместо этого я бы сделал следующее, что является небольшим уточнением повторяющихся идеальных перетасовок.

В то время как (есть два человека, которые не встречались):

1. Рассмотрим граф, в котором каждый узел является гостем, а ребро (A , B) существует, если A и B НЕ сидели за одним столом. Найдите все компонент связности этого графа. Если есть какие-либо связанные компоненты размером
2. Произвести случайную перестановку оставшихся элементов. (Другими словами, рассадите оставшихся людей случайным образом, что сначала будет всеми.)
3. Увеличивайте счетчик, показывающий количество раундов.

Повторяйте вышеупомянутое некоторое время, пока количество раундов не сойдется.

Комментарий WRT @ Neodymium, вот страница на сайте, которая имеет отношение к теме:

В ней обсуждаются генетические алгоритмы.

Это было очень забавно! : D

Я пробовал другой метод, но логика, предложенная adi92 (карта + приз), работает лучше, чем любой другой, который я пробовал.

Это работает так:

1. приходит парень и исследует все столы
2. для каждого стола со свободными местами он считает, сколько людей ему еще предстоит встретиться, затем выбирает тот, за которым больше неизвестных людей
3. , если на двух столах есть равное количество неизвестных людей, то парень выберет тот, за которым больше свободных мест, чтобы было больше шансов встретить больше новых людей

на каждом повороте порядок людей, занимающих места, является случайным (это позволяет избежать возможных бесконечных циклов), это «демонстрация» рабочего алгоритма на Python :

import random

class Person(object):

    def __init__(self, name):
        self.name = name
        self.known_people = dict()

    def meets(self, a_guy, propagation = True):
        "self meets a_guy, and a_guy meets self"
        if a_guy not in self.known_people:
            self.known_people[a_guy] = 1
        else:
            self.known_people[a_guy] += 1

        if propagation: a_guy.meets(self, False)

    def points(self, table):
        "Calculates how many new guys self will meet at table"
        return len([p for p in table if p not in self.known_people])

    def chooses(self, tables, n_seats):
        "Calculate what is the best table to sit at, and return it"
        points = 0
        free_seats = 0
        ret = random.choice([t for t in tables if len(t)<n_seats])

        for table in tables:
            tmp_p = self.points(table)
            tmp_s = n_seats - len(table)
            if tmp_s == 0: continue
            if tmp_p > points or (tmp_p == points and tmp_s > free_seats):
                ret = table
                points = tmp_p
                free_seats = tmp_s

        return ret

    def __str__(self):
        return self.name
    def __repr__(self):
        return self.name


def Switcher(n_seats, people):
    """calculate how many tables and what switches you need
        assuming each table has n_seats seats"""

    n_people = len(people)
    n_tables = n_people/n_seats

    switches = []
    while not all(len(g.known_people) == n_people-1 for g in people):
        tables = [[] for t in xrange(n_tables)]

        random.shuffle(people) # need to change "starter"

        for the_guy in people:
            table = the_guy.chooses(tables, n_seats)
            tables.remove(table)
            for guy in table:
                the_guy.meets(guy)
            table += [the_guy]
            tables += [table]

        switches += [tables]

    return switches



lst_people = [Person('Hallis'),
      Person('adi92'),
      Person('ilya n.'),
      Person('m_oLogin'),
      Person('Andrea'),
      Person('1800 INFORMATION'),
      Person('starblue'),
      Person('regularfry')]    



s = Switcher(4, lst_people)

print "You need %d tables and %d turns" % (len(s[0]), len(s))
turn = 1
for tables in s:
    print 'Turn #%d' % turn
    turn += 1
    tbl = 1
    for table in tables:
        print '  Table #%d - '%tbl, table
        tbl += 1
    print '\n'

Будет выведено что-то вроде:

You need 2 tables and 3 turns
Turn #1
  Table #1 -  [1800 INFORMATION, Hallis, m_oLogin, Andrea]
  Table #2 -  [adi92, starblue, ilya n., regularfry]


Turn #2
  Table #1 -  [regularfry, starblue, Hallis, m_oLogin]
  Table #2 -  [adi92, 1800 INFORMATION, Andrea, ilya n.]


Turn #3
  Table #1 -  [m_oLogin, Hallis, adi92, ilya n.]
  Table #2 -  [Andrea, regularfry, starblue, 1800 INFORMATION]

Из-за случайности он не всегда будет иметь минимальное количество переключателей, особенно с большим количеством людей. Затем вы должны запустить его пару раз и получить результат с меньшим количеством ходов (чтобы не беспокоить всех людей на вечеринке: P), и это легко кодировать: P

PS: Да, вы можете сэкономить призовые деньги: P