Questo era molto divertente! : D
Ho provato un metodo diverso ma la logica suggerita da adi92 (card + premio) è quella che funziona meglio di qualsiasi altra che ho provato.
funziona così:
- un ragazzo arriva e prende in esame tutti i tavoli
- per ogni tabella con i posti liberi si conta quante persone deve incontrare ancora, poi scegliere quella con più sconosciuta persone
- se due tabelle hanno un uguale numero di persone sconosciute, allora il ragazzo sceglierà quella con posti a sedere più liberi, in modo che non v'è più probabilità di incontrare più persone nuove
ad ogni giro l'ordine delle persone che prendono posti è casuale (questo evitare possibili loop infinito), questo è un "demo" dell'algoritmo di lavorare in pitone:
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'
Questa volontà di uscita qualcosa di simile:
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]
A causa del casuale, non sempre viene fornito con il numero minimo di interruttori, specialmente con gruppi di persone più grandi. Dovresti eseguirlo un paio di volte e ottenere il risultato con meno svolte (in modo da non stressare tutte le persone alla festa: P), ed è una cosa facile da codificare: P
PS: Sì , è possibile salvare il montepremi: P
Ci deve essere un numero uguale di maschi e femmine per tavolo? – Unknown
No, penso che il problema sia abbastanza difficile. – Hallis
Perché non creare un gruppo Facebook per restare in contatto tra loro? –