Subsets Probleem

[Verwijderd]

Ik heb een groep van 6 personen, die iedere week in 3 groepjes van 2 een opdracht moeten maken. Ik wil het zo rouleren dat in 5 weken iedereen een keer bij elke partner is geweest. Daarna herhaal ik het systeem gewoon.

Ik dacht dat dit eenvoudig was, maar nu ik dit wil programmeren valt het me tegen. Ik kan met google ook zo snel geen handig systeem/algoritme vinden om dit toe te passen, mede omdat ik niet weet hoe het zou heten. Hoe kan ik dit handig aanpakken? En het liefst op zo'n manier dat ik het kan algemeniseren waarmee ik de parameters n en s (totale groep en grootte van de subsets) kan varieren.

[RobIII]

Zoekterm: Permutaties

[Verwijderd]

Ik vrees dat ik hier niet veel aan heb. Er zijn met 6 mensen 6! permutaties en 6!/(2!*2!*2!)=90 manieren om een combinatie van 3 paren te maken. Het lastige van het probleem is alleen om uit die 90 combinaties 5 combinaties te vinden waarin ieder paar precies 1 keer voorkomt.

[Terror]

Tja, je zou kunnen sorteren (kleinste eerst) en dan dubbellen eruit gooien?

Misschien heb je hier wat aan:

http://www.cut-the-knot.org/do_you_know/AllPerm.shtml

Staan wat algoritmes beschreven. Moet je nog wel tunen voor jou situatie.

[Niemand_Anders]

Enkele dagen geleden was er een gelijk soort topic: \[.NET Linq] Recursive query op objecten.

Met wat creativiteit kun je dat vast wel omzetten naar een oplossing betreffende je uitdaging.

[KopjeThee]

Edit: laat maar.

[ Voor 102% gewijzigd door KopjeThee op 07-02-2008 14:58 ]

[Verwijderd]

volgens mij vergeet je een aantal mogelijkheden Als je 1 paar hebt, dan zijn er nog 3 mogelijheden om de overige paren samen te stellen. Bijv: w1) 12 met (34,56) of (35,46) of (36,45).

Ik weet zeker dat het mogelijk is. De KNVB krijgt het toch ook voor elkaar om iedere week x maal 2 ploegen tegen elkaar te laten spelen, zodat aan het einde van het seizoen iedereen precies 1 (of 2 keer in het geval van de eredivisie) tegen elkaar heeft gespeeld.

Een oplossing voor het probleem uit een ander topic is deze:

code:

Ronde    Thuisteam    Uitteam
1        1            6
1        2            5
1        3            4
2        4            2
2        5            1
2        6            3
3        1            4
3        2            3
3        5            6
4        2            6
4        3            1
4        4            5
5        1            2
5        5            3
5        6            4

[Verwijderd]

Oke ik ben een stapje verder. Een keywoord waar ik naar zocht is 'round-robin'. Dit is een toernooi, zoals bijvoorbeeld de eredivisie, waarin iedere ronde iedereen een andere tegenstander heeft, en na n-1 ronden iedereen een keer tegen iedereen is geweest.

Er zijn hier ook nog algoritmes voor te vinden, maar deze lijken uitsluitend gemaakt te zijn voor subsets van 2 (zoals een voetbalwedstrijd, of een paar). Ik zou het nog graag willen algemeniseren waarbij je ook bijvoorbeeld groepjes van 3 of 4 kunt maken.

[KopjeThee]

Het aantal benodigde weken kan wel flink toenemen met grotere groepen?

Het aantal verschillende groepjes van 2 mensen uit 6 is (6 boven 2) = 15. Je hebt elke week 6/2=3 groepjes nodig. Dus je krijgt dan 15/3 = 5 weken.

Bijvoorbeeld met 6 mensen en groepjes van 3, krijg je al (6 boven 3) = 20 mogelijke groepjes. Per week 6/3 = 2 groepjes nodig. Dus 20/2 = 10 weken.

Algemeen: ((n boven s)*s)/n weken nodig?

[jvdmeer]

KopjeThee schreef op donderdag 07 februari 2008 @ 16:46:
Het aantal benodigde weken kan wel flink toenemen met grotere groepen?

Het aantal verschillende groepjes van 2 mensen uit 6 is (6 boven 2) = 15. Je hebt elke week 6/2=3 groepjes nodig. Dus je krijgt dan 15/3 = 5 weken.

Bijvoorbeeld met 6 mensen en groepjes van 3, krijg je al (6 boven 3) = 20 mogelijke groepjes. Per week 6/3 = 2 groepjes nodig. Dus 20/2 = 10 weken.

Algemeen: ((n boven s)*s)/n weken nodig?

Ik neem aan dat je met 6 boven 3 bedoelt:

code:

6! / 3!   720 / 6
------- = ------- = 20
   3!        6

Is voor mij alweer ca. 15 jaar geleden dat ik daarmee iets deed.

[KopjeThee]

jvdmeer schreef op donderdag 07 februari 2008 @ 22:51:
[...]


Ik neem aan dat je met 6 boven 3 bedoelt:

code:

6! / 3!   720 / 6
------- = ------- = 20
   3!        6

Is voor mij alweer ca. 15 jaar geleden dat ik daarmee iets deed.

Ja, inderdaad (linkje). Dit helpt overigens natuurlijk nog niet veel met de oplossing. En het is ook maar een interpretatie van hoe dit probleem er in het algemeen uit zou kunnen zien... Misschien is een vraag aan de topic starter: Hoe zit dit probleem er in het algemeen uit? Misschien is dit ook wel interessant.