Permutaties doen vreemd

[Daos]

Een collega kwam vandaag met de vraag hoe groot de kans is dat je bij lootjes trekken jezelf iemand zichzelf of dezelfde als vorig jaar trekt bij in totaal 6 personen.

Ik ben dat nu aan het doorrekenen en krijg een vreemd resultaat: de kans is afhankelijk van wat er vorig jaar getrokken is, ookal had vorig jaar geen een persoon zichzelf getrokken. Hoe kan dat nu weer??

Voorbeelden (personen zijn genummerd vanaf 0; elke positie in de string stelt een persoon voor en het nummer dat daar staat is welke persoon hij getrokken heeft; bij bv 5x2xxx heeft persoon 0 persoon 5 getrokken en heeft persoon 2 zichzelf getrokken):
- bij vorig jaar 123450 krijg ik 80 geldige trekkingen
- bij vorig jaar 234501 krijg ik 82 geldige trekkingen

Hoe weet ik nu wat de kans is? Over alle mogelijke vorige jaren heen loopen en dan het gemiddelde berekenen lijkt mij (net) niet te doen...

Extra data (om te zien of mijn progsel goed is):
Bij 4 personen en vorig jaar 1230 krijg ik 2 geldige trekkingen:

0123 (invalid)
0132 (invalid)
0213 (invalid)
0231 (invalid)
0312 (invalid)
0321 (invalid)
1023 (invalid)
1032 (invalid)
1203 (invalid)
1230 (invalid)
1302 (invalid)
1320 (invalid)
2013 (invalid)
2031 (invalid)
2103 (invalid)
2130 (invalid)
2301
2310 (invalid)
3012
3021 (invalid)
3102 (invalid)
3120 (invalid)
3201 (invalid)
3210 (invalid)

Bij 4 personen en vorig jaar 2301 krijg ik 4 geldige trekkingen:

0123 (invalid)
0132 (invalid)
0213 (invalid)
0231 (invalid)
0312 (invalid)
0321 (invalid)
1023 (invalid)
1032
1203 (invalid)
1230
1302 (invalid)
1320 (invalid)
2013 (invalid)
2031 (invalid)
2103 (invalid)
2130 (invalid)
2301 (invalid)
2310 (invalid)
3012
3021 (invalid)
3102 (invalid)
3120 (invalid)
3201 (invalid)
3210

[RobIII]

Daos schreef op woensdag 11 november 2015 @ 20:51:
Een collega kwam vandaag met de vraag hoe groot de kans is dat je bij lootjes trekken jezelf of dezelfde als vorig jaar trekt bij in totaal 6 personen.

2:6 (Ofwel 1/3 ofwel 33,333...%)
Er zijn 6 lootjes, je wil niet jezelf noch persoon X want die had je vorig jaar. Blijven er nog 4 over. Hence: 2:6. Voila.

[ Voor 6% gewijzigd door RobIII op 11-11-2015 20:58 ]

[Daos]

Sorry, verkeerd geformuleerd. Moet zijn dat iemand zichzelf of dezelfde als vorig jaar trekt. Kans op ongeldige trekkingen dus.

[RobIII]

Daos schreef op woensdag 11 november 2015 @ 20:58:
Moet zijn dat iemand zichzelf of dezelfde als vorig jaar trekt. Kans op ongeldige trekkingen dus.

Da's toch nog steeds 1) niet jezelf en 2) niet persoon X? Er vallen er dus altijd 2 af. Dus bij N lootjes is de kans 2:N.

[edit]
Oh... Je wil weten hoe groot de kans is, als iedereen een lootje getrokken heeft, dat de hele "ronde" een resultaat oplevert dat goed is voor iedereen.

[ Voor 19% gewijzigd door RobIII op 11-11-2015 21:02 ]

[HyperioN]

RobIII schreef op woensdag 11 november 2015 @ 20:59:
[...]


Da's toch nog steeds 1) niet jezelf en 2) niet persoon X? Er vallen er dus altijd 2 af. Dus bij N lootjes is de kans 2:N.

Als je met 6 personen bent, moet er natuurlijk 6 keer getrokken worden. Dat bedoelt hij denk ik.

1e trekking: 6 lootjes beschikbaar; kans dat persoon X zichzelf of dezelfde als vorig jaar trekt is 2/6.
Indien goed getrokken:
2e trekking: 5 lootjes beschikbaar; kans dat persoon Y zichzelf of dezelfde als vorig jaar trekt is ...?
--- etc.

Probleem is dus, dat je niet weet wie X getrokken heeft.
De tweede trekking kan dus 2/5 zijn (indien persoon X níet persoon Y heeft en ook niet degenen die persoon Y vorig jaar had); maar kan ook 1/5 zijn (als persoon X persoon Y getrokkken heeft óf degene die persoon Y vorig jaar had)..
Je zou dus de kans dat persoon X persoon Y of degene-die-Y-vorig-jaar-had trekt moeten doorrekenen in de tweede trekking, enzovoort.
Maar hoe..?

[ Voor 7% gewijzigd door HyperioN op 11-11-2015 21:07 ]

[RobIII]

HyperioN schreef op woensdag 11 november 2015 @ 21:05:
Probleem is dus, dat je niet weet wie X getrokken heeft.

Daarom lijkt 't me verstandiger om na iemand die een kaartje trekt een 'ok' / 'af' te geven; dan hoef je niet elke keer een hele ronde uit te zitten. Maar zitten we nu de kans te berekenen of een algoritme voor 't toekennen van mensen aan andere mensen te verzinnen? Want waarom zou je dit met permuties (net zo lang doorgaan tot er 1 "geldig" is) oplossen en niet gewoon gericht?

[ Voor 26% gewijzigd door RobIII op 11-11-2015 21:11 ]

[Daos]

HyperioN schreef op woensdag 11 november 2015 @ 21:05:
[...]

Als je met 6 personen bent, moet er natuurlijk 6 keer getrokken worden. Dat bedoelt hij denk ik.

1e trekking: 6 lootjes beschikbaar; kans dat persoon X zichzelf of dezelfde als vorig jaar trekt is 2/6.
Indien goed getrokken:
2e trekking: 5 lootjes beschikbaar; kans dat persoon Y zichzelf of dezelfde als vorig jaar trekt is ...?
--- etc.

Probleem is dus, dat je niet weet wie X getrokken heeft.
De tweede trekking kan dus 2/5 zijn (indien persoon X níet persoon Y heeft en ook niet degenen die persoon Y vorig jaar had); maar kan ook 1/5 zijn (als persoon X persoon Y getrokkken heeft óf degene die persoon Y vorig jaar had)..

Dat is inderdaad wat ik bedoel. edit: alleen bedoel ik met trekking een permutatie waarbij iedereen een lootje getrokken heeft.

Je zou dus de kans dat persoon X persoon Y of degene-die-Y-vorig-jaar-had trekt moeten doorrekenen in de tweede trekking, enzovoort.
Maar hoe..?

Daarom loop ik alle permutaties af en kijk ik of ze geldig zijn. Ik vind het alleen zo raar dat het aantal geldige permutaties afhankelijk is/lijkt van de trekking vorig jaar.

RobIII schreef op woensdag 11 november 2015 @ 21:07:
[...]

Daarom lijkt 't me verstandiger om na iemand die een kaartje trekt een 'ok' / 'af' te geven; dan hoef je niet elke keer een hele ronde uit te zitten.

Het gaat om de berekening/bepaling van de kans. Niet om het werkelijke trekken van de lootjes.

[ Voor 3% gewijzigd door Daos op 11-11-2015 21:16 ]

[HuHu]

Bij 1230 vorig jaar, is 2031 nu toch valid? Jij hebt m als invalid staan en dat klopt niet lijkt me.

[GlowMouse]

HuHu schreef op woensdag 11 november 2015 @ 22:21:
Bij 1230 vorig jaar, is 2031 nu toch valid? Jij hebt m als invalid staan en dat klopt niet lijkt me.

Nee, want de 3 staat op dezelfde plek.

Daos schreef op woensdag 11 november 2015 @ 20:51:
Hoe weet ik nu wat de kans is? Over alle mogelijke vorige jaren heen loopen en dan het gemiddelde berekenen lijkt mij (net) niet te doen...

Waarom niet?
Beter zou het zijn om de kans te baseren op de daadwerkelijke trekking van vorig jaar.

[HuHu]

GlowMouse schreef op woensdag 11 november 2015 @ 22:25:
[...]

Nee, want de 3 staat op dezelfde plek.

Verhip, je hebt gelijk. En ik had nog wel extra goed gekeken... dacht ik.

[Morrar]

Volgens mij is de totale kans op een goede uitkomst :

Alle mogelijkheden - som_over_alle_personen(kans op jezelf + kans op persoon vorig jaar).

Kans op jezelf voor persoon i is:

1 / (aantal personen - i) - kans dat een eerder persoon je getrokken heeft. Dus

Eerste = 1 / 6 - 0
Tweede = 1 / 5 - 1 / 6
Derde = 1 / 4 - 1 / 6 + 1 / 5
etc.

En dan een soortgelijke berekening voor de kans dat je de persoon van vorig jaar trekt.

Of zit ik er nu naast?

[ Voor 16% gewijzigd door Morrar op 12-11-2015 00:25 ]

[BramV]

"Een collega kwam vandaag met de vraag hoe groot de kans is dat je bij lootjes trekken jezelf iemand zichzelf of dezelfde als vorig jaar trekt bij in totaal 6 personen"

Wat gaat die collega eigenlijk met de kansberekening doen ?

[Daos]

De collega was aan het klagen over de vele trekkingen die moeten gebeuren en vroeg hardop af wat de kans is dat alles goed gaat. Dat was voor mij een mooie reden om het probleem door te rekenen met de computer.

De kans is overigens vrij klein: maar 11% kans dat het lukt met 6 personen. Gemiddeld is dan pas na 9 ronden/trekkingen alles in orde.

[Morrar]

Daos schreef op donderdag 12 november 2015 @ 18:56:
De collega was aan het klagen over de vele trekkingen die moeten gebeuren en vroeg hardop af wat de kans is dat alles goed gaat. Dat was voor mij een mooie reden om het probleem door te rekenen met de computer.

De kans is overigens vrij klein: maar 11% kans dat het lukt met 6 personen. Gemiddeld is dan pas na 9 ronden/trekkingen alles in orde.

Je kunt het natuurlijk wel zo programmeren dat het in 1 keer goed gaat. Voor ieder persoon doe je:

1. Haal jezelf en degene die je vorig jaar had uit de pool
2. Als er personen overblijven:
- trek een willekeurig persoon
3. Als er geen personen overblijven (alleen jezelf en degene die je vorig jaar had over):
- ruil jezelf met een willekeurig ander persoon die jou vorig jaar niet had

[BramV]

Daos schreef op donderdag 12 november 2015 @ 18:56:
De collega was aan het klagen over de vele trekkingen die moeten gebeuren en vroeg hardop af wat de kans is dat alles goed gaat. Dat was voor mij een mooie reden om het probleem door te rekenen met de computer.

De kans is overigens vrij klein: maar 11% kans dat het lukt met 6 personen. Gemiddeld is dan pas na 9 ronden/trekkingen alles in orde.

Ja, 11% is weinig maar elk percentage veranderd niets aan het probleem en de klachten... Je had beter je tijd kunnen besteden aan een oplossing :-)

[wimjongil]

Je voorbeeld is best logisch toch? Je hebt vier personen: 0123. Twee trekkingen van vorig jaar: 1230 en 2301. Bij de tweede trekking zie je direct dat er twee groepjes zijn ontstaan: 0 en 2 hebben elkaar en 1 en 3 hebben elkaar. Beide groepen kunnen alleen iemand van de andere groep trekken in de nieuwe, maar dat kan wel op twee manieren. 2*2=4.

Bij 1230 zit iedereen aan de volgende persoon gekoppeld, dit zorgt ervoor dat er minder mogelijkheden zijn om een valide nieuwe trekking te maken. Je zult als het ware de hele trekking een plek op moeten schuiven (wat je ook ziet in je antwoorden). Je kunt 0123 op vier plekken beginnen, maar je mist de vorige trekking en de volgorde 0123. Je houdt dus 2 mogelijkheden over.

Er is hier dus inderdaad sprake van conditionele kansen.

[Daos]

wimjongil schreef op vrijdag 13 november 2015 @ 12:47:
Je voorbeeld is best logisch toch? Je hebt vier personen: 0123. Twee trekkingen van vorig jaar: 1230 en 2301. Bij de tweede trekking zie je direct dat er twee groepjes zijn ontstaan: 0 en 2 hebben elkaar en 1 en 3 hebben elkaar. Beide groepen kunnen alleen iemand van de andere groep trekken in de nieuwe, maar dat kan wel op twee manieren. 2*2=4.

Bij 1230 zit iedereen aan de volgende persoon gekoppeld, dit zorgt ervoor dat er minder mogelijkheden zijn om een valide nieuwe trekking te maken. Je zult als het ware de hele trekking een plek op moeten schuiven (wat je ook ziet in je antwoorden). Je kunt 0123 op vier plekken beginnen, maar je mist de vorige trekking en de volgorde 0123. Je houdt dus 2 mogelijkheden over.

Er is hier dus inderdaad sprake van conditionele kansen.

Bedankt voor de uitleg