Wisk probl: hoeveel deelverzamelingen te maken van x getalle

[JeroenTheStig]

Ik heb een aantal getallen, (getallen 1 tot en met 12). Deze wil ik in groepjes van 3 verdelen:

{1,2,3},{4,5,6},{7,8,9},{10,11,12}

Nu de vraag: Met welke formule kan ik uitrekenen hoeveel VERSCHILLENDE verzamelingen te maken zijn. Een getal mag niet 2 keer voorkomen!

Ik bedoel dus het volgende:

{1,2,3},{4,5,6},{7,8,9},{10,11,12}
{1,2,4},{3,5,6},{7,8,10},{9,11,12}
{1,2,5},{3,4,6},{7,12,9},{10,11,8}
{1,2,6},{3,4,5},{7,8,9},{10,11,12}
{1,3,4},{2,5,6},{7,8,9},{10,11,12}
{1,3,5},{2,4,6},{7,8,9},{10,11,12}
{1,3,6},{2,4,5},{7,8,9},{10,11,12}

enz enz enz

Is het mogelijk om dit te berekenen, en wie weet een slimme manier om deze verzamelingen stuk voor stuk te laten zien?

Ik heb zelf geen flauw idee hoe ik dit kan doen, ik heb het namelijk nodig om de beste oplossing voor een programma te berekenen. Per verzameling kan ik een true of een false terugkrijgen. Ik heb ook al aan backtracking gedacht, maar dit wordt me toch echt even te moeilijk met dit probleem.

Maar als er te veel oplossingen zijn (ik verwacht dat de verschillende verzamelingen erg groot zijn) dan zal ik er denk ik toch wel aan moeten denken om die backtracking te gebruiken, maar dat is een zorg voor later.

Iemand die mij verder kan helpen?

[Verwijderd]

Volgens mij is het 12! / (4!*3!) , dus 3326400 verzamelingen....

[MSalters]

Simpel: hoeveel mogelijkheden zijn er om 12 getallen in 2 groepen van 6 te verdelen:
12!/6!6!, die vervolgens elk in 6!/3!3! groepen kunnen worden onderverdeeld. Als je
{1,2,3},{4,5,6},{7,8,9},{10,11,12} en {4,5,6},{7,8,9},{10,11,12}, {1,2,3} apart wil tellen moet je nog delen door 4!.

[Verwijderd]

Hmmm.... aan de andere kant... die opdeling in groepjes doet er helemaal niet toe, want je kunt ze net zo goed achter elkaar zetten en de haakjes erbij denken. Het gaat er dus gewoon om hoeveel combinaties er zijn met de getallen 1-12 achter elkaar. Voor de eerste van de reeks zijn er 12 mogelijkheden, voor de tweede zijn er nog 11 over, voor de derde 10, etc. Dus 12*11*10*.... etc mogelijkheden. Is dus 12! = 479001600 mogelijkheden

[Alarmnummer]

*weet weer waarom hij altijd een enorme hekel had aan kansberekening*

[edit]
en ik vind wel dat als je 20 keer achter elkaar een 6 hebt gegooid met een dobbelsteen dat die 21 keer niet 1/6 is, maar veeeeeeel minder! Een dobbelsteen heeft dus wel geheugen

[Neman]

Verwijderd schreef op 29 augustus 2002 @ 17:59:
Hmmm.... aan de andere kant... die opdeling in groepjes doet er helemaal niet toe, want je kunt ze net zo goed achter elkaar zetten en de haakjes erbij denken. Het gaat er dus gewoon om hoeveel combinaties er zijn met de getallen 1-12 achter elkaar. Voor de eerste van de reeks zijn er 12 mogelijkheden, voor de tweede zijn er nog 11 over, voor de derde 10, etc. Dus 12*11*10*.... etc mogelijkheden. Is dus 12! = 479001600 mogelijkheden

Lijkt mij helemaal juist, ik sluit me er bij aan.

[ACM]

Alarmnummer schreef op 29 augustus 2002 @ 18:00:
en ik vind wel dat als je 20 keer achter elkaar een 6 hebt gegooid met een dobbelsteen dat die 21 keer niet 1/6 is, maar veeeeeeel minder! Een dobbelsteen heeft dus wel geheugen

Nee, dan is de kans dat het een zuivere dobbelsteen is erg klein
Wat trouwens statistiek is

[Larry4]

(n) = n!/(k!(n-k)!)
(k)

(12) = 220 mogelijkheden voor 1 3tal
( 3 )

(12) + (9) + (6) + (3) = 220 + 84 + 20 + 1 = 325
(3) (3) (3) (3)

toch is alweer tijd geleden combinatoriek enzo

[ACM]

Larry4 schreef op 29 augustus 2002 @ 18:04:
toch is alweer tijd geleden combinatoriek enzo

Dit komt mij ook als goed over

[.oisyn]

Verwijderd schreef op 29 augustus 2002 @ 17:59:
Hmmm.... aan de andere kant... die opdeling in groepjes doet er helemaal niet toe, want je kunt ze net zo goed achter elkaar zetten en de haakjes erbij denken. Het gaat er dus gewoon om hoeveel combinaties er zijn met de getallen 1-12 achter elkaar. Voor de eerste van de reeks zijn er 12 mogelijkheden, voor de tweede zijn er nog 11 over, voor de derde 10, etc. Dus 12*11*10*.... etc mogelijkheden. Is dus 12! = 479001600 mogelijkheden

fout, want { 1, 2, 3 } en { 3, 2, 1 } zijn dezelfde deelverzameling

[Verwijderd]

Aaaahhh... ligt er maar net aan he... Misschien denkt hij er wel heel anders over... maar dan was m'n first clue toch wel juist dus?

[.oisyn]

Larry4 schreef op 29 augustus 2002 @ 18:04:
(n) = n!/(k!(n-k)!)
(k)

(12) = 220 mogelijkheden voor 1 3tal
( 3 )

(12) + (9) + (6) + (3) = 220 + 84 + 20 + 1 = 325
(3) (3) (3) (3)

toch is alweer tijd geleden combinatoriek enzo

je moet het vermenigvuldigen, niet bij elkaar optellen
voorbeeld: als je de verzameling { 1, 2, 3, 4 } hebt, en je wilt dat onderverdelen in 2 groepjes van 2. Om 1 groepje te maken doe je

code:

( 4 )  =  6
( 2 )

dan heb je nog 2 getallen over, dus de volgende zou worden:

code:

( 2 ) = 1
( 2 )

daar is ook maar 1 mogelijkheid voor. Het totaal is dus 6 * 1 = 6, en niet 6 + 1 = 7 zoals jij beschrijft

[.oisyn]

Verwijderd schreef op 29 augustus 2002 @ 18:34:
Aaaahhh... ligt er maar net aan he... Misschien denkt hij er wel heel anders over... maar dan was m'n first clue toch wel juist dus?

nou, stel je gebruikt jouw stelling: aantal mogelijkheden = 12! = 479001600

alleen als je dan kijkt naar de eerste 3 getallen, dan zijn er 3! = 6 manieren om ze te ordenen. Dus per groepje moet je delen door 6 (om de dubbele weg te werken)
Je hebt 4 groepjes, dus je deelt in totaal door 3!⁴
12! / 3!⁴ = 369600


als je het antwoord van Larry4 pakt, met mijn verbetering erbij (dus * ipv +), dan kom je op 220 * 84 * 20 * 1 = 369600


.edit: pak je de post van MSalters erbij, dan kom je op eerst 12!/6!/6! = 924 mogelijkheden, waarvan er zowel links als rechts nog eens 6!/3!/3! = 20 mogelijkheden zijn, dus 924 * 20 * 20 = wederom 369600

[.oisyn]

nou is het dus aan de topicstarter of {{1,2},{3,4}} == {{3,4},{1,2}}, zo ja dan moeten we nog delen door 4! zoals MSalters al aangaf, aangezien er 4! = 24 mogelijkheden zijn om 4 groepjes te ordenen

(kom je uit op 369600 / 4! = 15400 mogelijkheden)

[JeroenTheStig]

.oisyn schreef op 29 augustus 2002 @ 18:13:

[...]


fout, want { 1, 2, 3 } en { 3, 2, 1 } zijn dezelfde deelverzameling

Inderdaad, vandaar dat ik de verzamelinghaakjes heb gebruikt.. ik lees even verder, dit zijn nogal wat reacties binnen een uurtje

thanx alvast !

[JeroenTheStig]

.oisyn schreef op 29 augustus 2002 @ 18:51:
nou is het dus aan de topicstarter of {{1,2},{3,4}} == {{3,4},{1,2}}, zo ja dan moeten we nog delen door 4! zoals MSalters al aangaf, aangezien er 4! = 24 mogelijkheden zijn om 4 groepjes te ordenen

(kom je uit op 369600 / 4! = 15400 mogelijkheden)

Die verzamelingen zijn inderdaad gelijk. Anders zit ik dingen dubbel te checken in m'n programma, en daar wordt ie alleen maar trager van...

al ben ik bang dat het al een trage boel wordt, want met 30 verschillende cijfers kun je heel wat mogelijkheden maken

[Verwijderd]

Volgens mij is dan toch het enige juiste antwoord mijn 1e reactie! (het 2e bericht). Maar goed, ik ben stronteigenwijs, dus dat betekent niet meteen dat het ook echt het goede antwoord is!

[JeroenTheStig]

ik zal hem een paar keer testen.. het zal wel een grote ellende worden als het antwoord klopt, want dan moet ik echt backtracking gebruiken
en daar moet ik dan eerst maar eens even flink in oefenen

[JeroenTheStig]

Verwijderd schreef op 29 augustus 2002 @ 17:55:
Volgens mij is het 12! / (4!*3!) , dus 3326400 verzamelingen....

even een testje: ik heb 4 getallen, en die wil ik in groepjes van 2 hebben.

volgens je formule is de uitkomst dan: 4! / (2! * 2!)

is 1*2*3*4 / (1*2 * 1*2) = 24/4 = 6

maar ik kom niet verder dan dit:

{{1,2},{3,4}}
{{1,3},{2,4}}
{{1,4},{2,3}}

Of zie ik die andere drie nu even over het hoofd misschien? volgens mij niet hoor...

ik ga er trouwens van uit dat {{1,2},{3,4}} == {{4,3},{1,2}}

[JeroenTheStig]

nog een test:

6 getallen, en die wil ik in groepjes van 3:

volgens de formule: 6! / (2! * 3!) = 720 / 12 = 60


Ik kom niet verder dan:

{{1,2,3},{4,5,6}}
{{1,2,4},{3,5,6}}
{{1,2,5},{3,4,6}}
{{1,2,6},{3,4,5}}
{{1,3,4},{2,5,6}}
{{1,3,5},{3,4,6}}
{{1,3,6},{2,4,5}}
{{1,4,5},{2,3,6}}
{{1,4,6},{2,3,5}}
{{1,5,6},{2,3,4}}

[Larry4]

(6)*(3) = 6! / (3!(6-3)!) = 720 / 36 = 20 * 1 = 20
(3) (3)


Maar de 2 deelverzamelingen zijn ook nog
combineer baar dus delen door 2! (zoals .oisyn al zei) is 20 / 2 = 10 dan klopt het wel

[Alarmnummer]

BoKToR schreef op 29 augustus 2002 @ 20:09:
ik ga er trouwens van uit dat {{1,2},{3,4}} == {{4,3},{1,2}}

In een verzameling is de volgorde en het aantal keren dat een element erin voorkomt onbelangrijk. (Aantal mag dan natuurlijk niet ineens op 0 worden gezet).

[.oisyn]

Verwijderd schreef op 29 augustus 2002 @ 19:38:
Volgens mij is dan toch het enige juiste antwoord mijn 1e reactie! (het 2e bericht). Maar goed, ik ben stronteigenwijs, dus dat betekent niet meteen dat het ook echt het goede antwoord is!

het spijt me, maar dit:

Verwijderd schreef op 29 augustus 2002 @ 17:55:
Volgens mij is het 12! / (4!*3!) , dus 3326400 verzamelingen....

slaat eigenlijk helemaal nergens op
waar is die berekening op gebaseerd? Kun je er eens een uitleg bij geven?

Wat jij bedoelt is waarschijnlijk het binomiaal coefficient, oftewel n-boven-k, wat n! / (k! * (n - k)!) is, waar MSalters en Larry4 dus mee aan kwamen zetten

[Soultaker]

Om maar even in de praktijk te kijken hoe het werkt, heb ik een scriptje gemaakt dat de mogelijke combinaties genereert.

Voor 4 groepjes van 3 getallen is het aantal resultaten 15400, als mijn algoritme correct is. Kijk zelf op:
http://maks.student.utwen...eperen.php?sets=4&sizes=3
Met de broncode:
http://maks.student.utwente.nl/~maks/groeperen.phps

Om de uniekheid van de oplossingen te garanderen noteer ik de oplossingen in een normaalvorm: de getallen worden gesorteerd weergegeven in de deelverzamelingen, de 'overkopelende' verzameling van verzamelingen is gesorteerd op het eerste element van de bevatte verzamelingen.

Hiervan uitgaande genereer ik alle mogelijk combinaties door alle getallen (1 tot en met 12 in het voorbeeld) in volgorde toe te voegen, waarbij een getal alleen in die verzamelingen geplaatst kan worden die nog niet vol is. Aangezien de getallen in volgorde toegevoegd worden is de 'interne' ordening gegarandeerd (een getal wordt immers uitsluitend toegevoegd aan een verzameling van kleinere getallen). Om ook de 'externe' ordening te kunnen garanderen, kan een getal alleen geplaatst worden in een verzameling waar geen lege verzamelingen aan vooraf gaan (anders zou er later een hoger getal tussen gevoegd kunnen worden).

Waarschijnlijk is uit de constructie van het algoritme of de opbouw van de normaalvorm ook wel een zinnige formule van het aantal oplossingen te vinden. Ze stomweg allemaal berekenen is natuurlijk niet de bedoeling.

edit:
Aangezien .oisyn al op 15400 uitkwam, is zijn formule waarschijnlijk wel correct. Nu heb je er in ieder geval ook een aardig algoritme bij om alle mogelijke oplossingen te produceren.

[Verwijderd]

Volgnes mij kloppen de antwoorden van .oisyn en Soultaker. Maar goed ik heb pas 2/5 van mijn opleiding tot wiskundige achter de rug ;-).

[Grum]

Oftewel:

x in groepjes van y: x! / y!^(x/y) / (x/y)!

12! / 3!^(12/3) / (12/3)! = 479001600 / 1296 / 24 = 15400

Of natuurlijk:

x in y groepjes: x! / (x/y)!^y / y!

Tis maar wat je leuk vindt om uit te zoeken

[JeroenTheStig]

Mensen, hardstikke bedankt voor jullie hulp, ik denk dat ik er nu wel uit kom!
Soultaker, super dat je even een scriptje wilde maken, dit maakt de zaak al heel wat duidelijker! Bedankt!

[JeroenTheStig]

Soultaker,

Ik heb nog een paar vraagjes over je php-script:

Wat bedoel je met 'array()' in het volgende stukje code:


for($s=0; $s<$sets; ++$s) $sol[$s]=array();


Ik heb zelf nog nooit iets in php geschreven, dus die php-commando's ken ik ook niet. Wat wordt er bedoelt met dat stukje code?

Het volgende begrijp ik ook niet: wat doet 'count' in het volgende stukje:


for($s=0;$s<$sets;++$s)
{
if(count($sol[$s])<$sizes) // Wat gebeurt hier?!?!?!?!?
{
$nsol=$sol; $nsol[$s][]=$n;
$solutions+=solve($nsol, $n+1);
}
if(count($sol[$s])==0) break; // wat gebeurt hier?!?!?!?!?
}

alvast bedankt

[Apollo_Futurae]

array() maakt een lege array
count($array) geeft het aantal elementen in $array

[JeroenTheStig]

for($s=0; $s<$sets; ++$s) $sol[$s]=array();

Dit begrijp ik niet, want die sol is toch een 2 dimensionale array? Kan iemand dit in java-code vertalen? Misschien dat ik er dan wel wat van begrijp

[JeroenTheStig]

het lijkt namelijk net of er in het scriptje 1-dimensionale en 2-dimensionale arrays worden gebruikt, en dat komt niet helemaal goed lijkt mij... het zal dus wel de schrijfwijze zijn van php, alleen heb ik geen flauw idee hoe ik het in Java kan schrijven

[Apollo_Futurae]

php kent geen multi-dimensionale arrays;
dit kun je ondervangen door arrays van arrays te gebruiken.
for($s=0; $s<$sets; ++$s) $sol[$s]=array(); betekent, dat $sol[ i ] een array moet worden, voor 0 <= i < $sets.

[ Voor 0% gewijzigd door Apollo_Futurae op 31-08-2002 21:04 . Reden: [ i] zonder spaties kan uiteraard niet :+ ]

[JeroenTheStig]

hmm... maar hoe verklaar je het volgende?

for($p=0; $p<$sizes; ++$p)
{
echo " ".($sol[$s][$p] + 1);
echo $p<($sizes-1)?",":" ";
}


wat is '$sol[$s][$p]' dan?

[Grum]

Kan je niet gewoon eventjes de php manual doorlezen ofzo ?

$sol[ $s ][ $p ] is nix anders dan het $p'de item van het $s'de item van $sol

Oftewel $sol is een array met arrays erin.

code:

$sol = array(
             array(),
             array() //, etc
           );

[JeroenTheStig]

ach ja Grum, ik heb al even vluchtig op php.net gekeken, maar hier word ik ook niet veel wijzer van
Maar als ik het nu zo zie, dan is die array afhandeling in php een stuk slimmer in elkaar gezet dan in Java...
je kunt hier steeds een item aan toevoegen, en php past de grootte van de array wel aan.. in Java wil dat helaas niet, zonder extra code er omheen..

[Grum]

Maar in princiepe heb je deze code helemaal niet nodig (volgens je eerste topic ging het alleen over het berekenen van het aantal mogelijkheden.

Zet gewoon x! / (x/y)!^y / y! om in de juiste taal.

[JeroenTheStig]

ja, dat was de eerste stap. Ik heb volgens mij ook gevraagd of het mogelijk was om alle mogelijkheden slim uit te draaien, en dat werkt prima met dat stukje code.
dussssssssss

[Grum]

dusssssss moet je ff php leren

[JeroenTheStig]

niks daarvan
ik moet alleen dit stukje even ombouwen naar Java, daar ga ik geen php voor leren, da's mij te veel werk.