Running Dinner: welke mogelijke tafelindelingen?

[RunningDinner]

Dag mensen,


In mijn woonplaats organiseren we jaarlijks een Running DInner, met als doel mensen uit alle lagen van de bevolking op een ontspannen manier, onder het genot van een maaltijd, met elkaar in contact te brengen.

Wat is een Running Dinner precies? In 6 huizen wordt een 3-gangenmenu geserveerd (voorgerecht, hoofdgerecht, nagerecht). 24 deelnemers beginnen op 6 verschillende adressen (A, B, C, D, E, F) aan een voorgerecht: op elk adres zitten dan 4 personen aan tafel (naast de kok en gastheer/-dame die op hun eigen adres blijven). Na het voorgerecht gaan alle 24 deelnemers naar een ander adres voor het hoofdgerecht en zitten niet aan tafel met een persoon die ze deze avond al eerder troffen. Hetzelfde na het hoofdgerecht: iedereen vertrekt weer naar een adres waar ze nog niet eerder waren deze avond en zitten dan ook weer met alleen onbekenden aan tafel.

Ik zou heel graag willen weten hoeveel en welke tafelindelingen hier mogelijk zijn. Ik zou ook graag willen weten hoe ik het antwoord zelf had kunnen bedenken, want sommige jaren hebben we te maken met variaties op bovenstaande: bijvoorbeeld 7 i.p.v. 6 adressen waar gekookt wordt of twee deelnemers die perse de hele avond samen ingedeeld willen worden.

Misschien is het handig om, voor de manier van uitleggen, te weten wat mijn niveau wat betreft wiskunde is:

In een ver verleden heb ik 5 jaar wiskundeles gehad op het HAVO. Ik vond het een heel leuk vak, maar mijn kennis ervan is aardig weggezakt.


Hartelijke groeten en alvast heel erg bedankt!

[siep]

Dit is een variant van het derangement probleem, zie bijvoorbeeld
https://en.wikipedia.org/wiki/Derangement
Daarbij zoeken we omwisselingen (permutaties) van personen (elementen), zodanig dat niemand op dezelfde plaats blijft (bv. trekken van lootjes bij sinterklaasviering: iedereen moet precies 1 keer getrokken worden, maar niemand mag zichzelf trekken).

Jouw probleem heeft echter veel meer eisen: er zijn meerdere gangen en meerdere huizen,
en elke gang (trekking) moet iedereen steeds in een verschillend huis EN samen met verschillende andere personen aan tafel.

De oplossing van jouw probleem is daarom ingewikkelder dan die van het derangement probleem.

Als ik om te beginnen dit als zoekprobleem door de computer laat oplossen, krijg ik dit als eerste resultaten:
(hier oplossingen voor een 5 gangen menu, heb je minder gangen, dan laat je gewoon de gangen die je te veel hebt weg)


5 huizen, 20 personen:

Code: Selecteer alles

            1e gang        2e gang        3e gang        4e gang        5e gang
huis A     1  2  3  4     5  9 13 17     7 12 15 18     8 11 14 19     6 10 16 20
huis B     5  6  7  8     1 10 14 18     2 11 16 17     4  9 15 20     3 12 13 19
huis C     9 10 11 12     2  6 15 19     1  8 13 20     3  5 16 18     4  7 14 17
huis D    13 14 15 16     3  7 11 20     4  5 10 19     1  6 12 17     2  8  9 18
huis E    17 18 19 20     4  8 12 16     3  6  9 14     2  7 10 13     1  5 11 15

6 huizen, 24 personen:

Code: Selecteer alles

            1e gang        2e gang        3e gang        4e gang        5e gang
huis A     1  2  3  4     5  9 13 17    12 15 19 22     7 10 16 18     6 11 14 23
huis B     5  6  7  8     1 10 14 21     2  9 20 24     4 12 13 23     3 16 17 22
huis C     9 10 11 12     2  6 18 22     1  5 16 23     3 15 20 21     8 13 19 24
huis D    13 14 15 16     3  7 19 23     8 11 18 21     1  6 17 24     4  5 10 20
huis E    17 18 19 20     4 11 15 24     3  6 10 13     8  9 14 22     2  7 12 21
huis F    21 22 23 24     8 12 16 20     4  7 14 17     2  5 11 19     1  9 15 18

7 huizen, 28 personen:

Code: Selecteer alles

            1e gang        2e gang        3e gang        4e gang        5e gang
huis A     1  2  3  4     5  9 13 17     6 10 16 19    11 14 24 25     7 12 21 28
huis B     5  6  7  8     1 10 14 18     2  9 23 26     3 15 20 21    11 13 22 27
huis C     9 10 11 12     2  6 21 25     1  5 24 28     8 13 19 26     3 16 18 23
huis D    13 14 15 16     3  7 22 26     4 11 17 21     1  6  9 27     2  5 10 20
huis E    17 18 19 20     4  8 23 27     3 12 13 25     2 16 22 28     6 15 24 26
huis F    21 22 23 24    11 15 19 28     7 14 20 27     4  5 12 18     1  8 17 25
huis G    25 26 27 28    12 16 20 24     8 15 18 22     7 10 17 23     4  9 14 19

Hieraan moeten we zelfs nog meer eisen gaan toevoegen:
- een aantal tweetallen personen zal gekoppeld willen blijven
- wat als het aantal personen niet precies deelbaar is door 4 (bijvoorbeeld 22 personen)
- zijn er ook huizen tussen waar er 5 of meer mensen aan tafel kunnen?
etc.

Heb je wellicht al een concreet voorbeeld (met aantal permanente koppels, aantal deelnemers, aantal huizen)?

[Raymondm]

Goedenavond,

Ik heb hetzelfde probleem.
De oplossing van arie klinkt goed.

Alleen ben ik niet begaafd om een "zoekprobleem op te lossen" op mijn computer.

Ik ben op zoek naar een schema met 3 gangen, 8 huizen en 32 personen.

Graag, zou ik ook weten hoe ik dat kan doen op mijn computer met x gangen, y huizen en z personen.

Dank,
Raymond

[siep]

Voor 8 huizen, 3 gangen en 32 personen is er een vrij eenvoudige oplossing:



of in tabelvorm:

Code: Selecteer alles

             gang 1:        gang2:         gang 3:
huis 1:     1  2  3  4    29 26 23 20    17 22 27 32
huis 2:     5  6  7  8     1 30 27 24    21 26 31  4
huis 3:     9 10 11 12     5  2 31 28    25 30  3  8
huis 4:    13 14 15 16     9  6  3 32    29  2  7 12
huis 5:    17 18 19 20    13 10  7  4     1  6 11 16
huis 6:    21 22 23 24    17 14 11  8     5 10 15 20
huis 7:    25 26 27 28    21 18 15 12     9 14 19 24
huis 8:    29 30 31 32    25 22 19 16    13 18 23 28

Heb je voor het verassings-element liever iets minder structuur in het schema, dan krijg je zoiets:

Code: Selecteer alles

             gang 1:        gang2:         gang 3:
huis 1:    31  7 24 28    27 13 11  3     5 26 32  1
huis 2:     8 19 12 14    10  7 26  9    11 23 22 18
huis 3:    27  4  6 25    19 32 22 17    29  7 14 15
huis 4:    21  1  9 23    14  2 18 25    27 17 28 16
huis 5:    11 16  5 29    21 15  6 12     4  9 13 19
huis 6:    15 32 10 18     5 23  4 24    21 20 25 30
huis 7:     3 17 26 20    16  1 30 31    24  2  8  6
huis 8:    13  2 22 30     8 20 29 28    31  3 12 10

ofwel




Voor de computer bestaan er vele zoek-algoritmen (zie bv. https://en.wikipedia.org/wiki/Search_algorithm) die binnen redelijke tijd een oplossing (of een redelijke oplossing) kunnen vinden.

Als je dit zelf gaat bouwen zal je waarschijnlijk deze 4 tabellen willen gebruiken:
[1] huis-gang-persoon: het schema met een oplossing voor je probleem
[2] persoon-persoon: welke personen elkaar wel of niet ontmoet hebben
[3] persoon-huis: welke persoon al in welk huis geweest is
[4] persoon-gang: welke persoon er al is ingedeeld per maaltijdgang.

Je algoritme zal er dan globaal zo uitzien:
voeg aan elke open plaats in schema [1] steeds een persoon toe die voldoet aan alle voorwaarden (tabel [2] t/m [4]),
- indien die persoon er is: update je tabellen en ga door met de volgende plaats
- indien er geen geschikte personen over zijn: ga dan terug in je zoekboom en kies ergens een alternatieve persoon
Ga hiermee door tot je tabel klaar is.


Op het web zijn overigens ook programma's voor running dinner schema's te vinden,
Hierin zitten doorgaans ook opties voor extra randvoorwaarden ingebouwd (zie de "extra eisen" in mijn eerste post hierboven).
Op https://www.youtube.com/watch?v=tD0rOtbjwG0 zie je een uitgebreide handleiding voor zo'n programma.
Ik heb verder geen ervaring met deze programma's en ken ook geen van de ontwerpers daarvan, maar mogelijk heb je er iets aan.

[francis_sciencetalk]

Ik heb 12 huizen, 31 deelnemers (nieuwe buurt waarin mensen meedoen die nog geen huis hebben...) en ben bijna klaar met de indeling, alleen loop ik er nu tegenaan dat mensen bij elkaar zitten bij verschillende gangen. Bij mij speelt mee dat de koppels bij elkaar willen blijven, dat er 2 koppels zijn die samen het hoofdgerecht willen bereiden en een koppel en een persoon die ook samen het hoofdgerecht willen bereiden. Ik heb vier groepen per gerecht (4 huizen waar voor-4 huizen waar hoofd- en vier huizen waar nagerecht wordt verzorgd). Heb dus 15 koppels en een solist. Is er iemand die kan helpen....? WK tot en met VWO 4, Veel statistiek bij universitaire opleiding sociale wetenschappen. En toch.....

[siep]

Code: Selecteer alles

Voorgerecht:
huis  1:    A E I M
huis  2:    B F J N
huis  3:    C G K O
huis  4:    D H L P

Code: Selecteer alles

Hoofdgerecht:
huis  5:    E F C D
huis  6:    G H A B
huis  7:    I O L N
huis  8:    J P K M

Code: Selecteer alles

Nagerecht:
huis  9:    K B D I
huis 10:    L A C J
huis 11:    M F H O
huis 12:    N E G P

Hier een mogelijke oplossing.
De koppels zijn genummerd A t/m P, waarbij H de solist is.
Koppels A, B, C en D verzorgen het voorgerecht
Koppels (E+F), (G+solist H), I en J verzorgen het hoofdgerecht (zo nodig kunnen O en P assisteren bij I resp. J)
Koppels K, L, M en N verzorgen het nagerecht.

De koppels komen elkaar maximaal 1 keer tegen, dus elk koppel ontmoet 9 andere koppels.

Bedoel je dit?

[annet matthijssen]

Ik zoek een rouleerschema voor 3 gangen, 7 adressen en 21 stellen. Per adres/gang kunnen er 3 stellen plaats nemen.

[R_Bena]

Verdeel de 21 stellen in 7 groepen van 3 stellen: elk groepje is 1 adres.

Deze 7 adressen worden elk aan één gang toegewezen (voorgerecht, hoofdgerecht, nagerecht). Elk adres is dus 1 keer host, bij een specifieke gang.