Это было очень смешно! : D
Я пробовал использовать другой метод, но логика, предложенная adi92 (card + prize), является той, которая работает лучше, чем любая другая, которую я пробовал.
Это работает так:
- парень приходит и проверяет все таблицы
- для каждой таблицы со свободными местами он подсчитывает, сколько людей он должен встретиться еще, а затем выбрать один с более неизвестным люди
- , если две таблиц имеют равное количество неизвестных людей, то парень будет выбрать один с более свободными местами, так что есть больше вероятности встретить новые человек
при каждом повороте порядок людей, принимающих мест является случайным (это позволит избежать возможных бесконечных циклов), то это является «демо» рабочего алгоритма в питоне:
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
Должно ли быть одинаковое количество мужчин и женщин на стол? – Unknown
Нет, я думаю, что проблема достаточно сложная, как есть. – Hallis
Почему бы вам просто не создать группу Facebook, чтобы поддерживать связь друг с другом? –