¡Este fue muy divertido! : D
Probé con un método diferente pero la lógica sugerida por adi92 (tarjeta + premio) es la que funciona mejor que cualquier otra que probé.
funciona así:
- un tipo llega y examina todas las tablas
- para cada mesa con asientos libres que cuenta la cantidad de gente que tiene que cumplir, sin embargo, a continuación, elegir el que tenga más desconocida
personas
- si dos tablas tienen un número igual de personas desconocidas entonces el chico va a elegir el que tenga asientos más libre, por lo que hay más probabilidad de conocer más gente nueva
En cada vuelta del orden de las personas que toman asientos es al azar (esto evitar posibles bucles infinitos), este es un "demo" del algoritmo de trabajo en 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'
Esto sería algo así como:
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]
Debido a lo aleatorio, no siempre tendrá la cantidad mínima de interruptores, especialmente con grupos de personas más grandes. Debería ejecutarlo un par de veces y obtener el resultado con menos giros (para no estresar a todas las personas en la fiesta: P), y es fácil codificar: P
PD: Sí , puede guardar el dinero del premio: P
¿Tiene que haber un número igual de hombres y mujeres por mesa? – Unknown
No, creo que el problema ya es bastante difícil. – Hallis
¿Por qué no creas un grupo de Facebook para mantenerte en contacto? –