Алфавитный указатель

Ответ 1

Это звучит как приложение для генетического алгоритма:

• Выберите случайную перестановку 40 гостей - это одно размещение.
• Повторите случайную перестановку N времени (n - сколько раз вы переключаете места в ночное время).
• Объедините перестановки вместе - это хромосома для одного организма.
• Повторяйте, как много организмов вы хотите размножать в одном поколении.
• Показатель пригодности - это количество людей, которых каждый человек должен увидеть за одну ночь (или, наоборот, наоборот, количество людей, которых они не видели).
• Породите, мутируйте и вводите новые организмы, используя обычный метод, и повторяйте, пока не получите удовлетворительный ответ.

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

Ответ 2

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

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

Ответ 3

Почему бы не подражать реальному миру?

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

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

Ответ 4

Идеальный план таблицы

Ответ 5

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

Ответ 6

Ответ 7

Это было очень смешно!: D

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

Он работает следующим образом:

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

на каждом повороте порядок людей, сидящих на месте, случайный (это позволяет избежать бесконечных циклов), это "демо" рабочего алгоритма в 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

Ответ 8

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

Ответ 9

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

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

• Рассмотрим график, в котором каждый node является гостевым, а ребро (A, B) существует, если A и B НЕ сидели за одной таблицей. Найдите все связанные компоненты этого графика. Если есть какие-либо связанные компоненты размера < tableize, планировать эти подключенные компоненты в таблицах. Обратите внимание, что даже это на самом деле является примером жесткой проблемы, известной как упаковка бинов, но с первого раза уменьшающаяся, вероятно, будет прекрасной, что может быть достигнуто путем сортировки подключенных компонентов в порядке наибольшей и наименьшей, а затем поместить их каждый из них в поверните на первую таблицу, где они подходят.
• Выполните произвольную перестановку остальных элементов. (Другими словами, расположите оставшихся людей случайным образом, и вначале будет каждый.)
• Счетчик приращений, указывающий количество раундов.

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

Ответ 10

Комментарий WRT @Neodymium, здесь страница на соответствующем сайте:

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