[VB.net] Kansberekening

[xandie]

Ik ben begonnen met het leren van VB.net. Ik ben nog niet veel verder geraakt dan wat met variabelen te spelen en enkele eenvoudige progjes te schrijven.
Nu ben ik bezig met een programma om mensen in groepen te verdelen en die groepen dan in een array te steken

Het aantal groepen is altijd 5
Het aantal personen per groep is minimum 1
Het totaal aantal personen varieert.

Mijn doel is om het aantal mogelijke combinaties te berekenen en dan alle mogelijke combinaties in een array bij te houden.

Vraag1;
"hoe kan ik het aantal mogelijke combinaties berekenen.
Vraag 2:
Hoe kan ik al die combinaties in een array zetten.

voorbeeld: (in de uiteindelijke array komen natuurlijk tientallen van deze tabellen)

Groep 1	Groep 2	Groep 3	Groep 4	Groep 5
Persoon 1	Persoon 3	Persoon 2	Persoon 4	Persoon 8
Persoon 6	Persoon 5	Persoon 10	Persoon 9	Persoon 7
Persoon 12	Persoon 11	Persoon 15	Persoon 17	Persoon 16
Persoon 13	Persoon 18	Persoon 14	Persoon 20	Persoon 23
Persoon 21	Persoon 19	Persoon 22

Dit is wat ik heb.

Visual Basic .NET:

        'De personen worden opgeslagen in arrstrPersonen
        Dim arrstrPersonen() As String
        Dim intteller, intAantal As Integer
        intaantal = InputBox("geef het aantal personen")
        For intteller = 0 To (intaantal - 1)
            arrstrpersonen(intteller) = InputBox("Geef persoon " & (intteller + 1))
        Next

  
      
        'aantal mogelijke combinaties berekenen (intAantalcombinaties)  
        Dim intaantalCombinaties As Integer
        intaantalCombinaties = 

        'combinaties opslagen in array 
        ' arrstrcombinaties(persoon, groep, tabelnummer)
        Dim arrstrCombinaties(,,) As Integer

        For intteller = 0 To (intaantalCombinaties - 1)
        arrstrCombinaties(, , intteller) = arrstrPersonen()
        Next

Ik wil geen code hebben als antwoord, ik heb liever een manier waarop ik het zou kunnen doen.
Mijn excuses als ik mijn vraag niet duidelijk stel

Alvast bedankt om deze tekst door te lezen

Edit: Ik heb het wat verduidelijkt

[ Voor 34% gewijzigd door xandie op 10-06-2013 23:11 . Reden: Verduidelijking ]

[Gomez12]

Klopt je voorbeeld array wel? Want ik snap hem in ieder geval niet, elke groep bevat persoon 1, 2x een persoon 3, enkel persoon 4 5 en 6 lijken te kunnen varieren.

Simplistisch manier uit je vraagstelling lijkt mij : Haal 1 voor 1 de mensen op, geef ze een random groep van 1 tot 5 en controleer of er binnen die groep nog plek is (zoniet opnieuw random groep, of als het om grotere aantallen mensen gaat elimineer de groep en ga alleen random 1 tot 4 plaatsen in het verdere traject). Alleen dit levert nooit van zijn leven een tabel op zoals jij hem geeft. Dus of ik begrijp je vraag niet, of ik begrijp je tabel niet (laatste sowieso)

[xandie]

Gomez12 schreef op maandag 10 juni 2013 @ 21:51:
Klopt je voorbeeld array wel? Want ik snap hem in ieder geval niet, elke groep bevat persoon 1, 2x een persoon 3, enkel persoon 4 5 en 6 lijken te kunnen varieren.

Simplistisch manier uit je vraagstelling lijkt mij : Haal 1 voor 1 de mensen op, geef ze een random groep van 1 tot 5 en controleer of er binnen die groep nog plek is (zoniet opnieuw random groep, of als het om grotere aantallen mensen gaat elimineer de groep en ga alleen random 1 tot 4 plaatsen in het verdere traject). Alleen dit levert nooit van zijn leven een tabel op zoals jij hem geeft. Dus of ik begrijp je vraag niet, of ik begrijp je tabel niet (laatste sowieso)

Mijn tabel was idd fout (ik heb hem aangepast )

Het aantal groepen is altijd 5
Het aantal personen per groep is minimum 1
Het totaal aantal personen varieert.

Mijn doel is om het aantal mogelijke combinaties te berekenen en dan alle mogelijke combinaties in een array bij te houden.

De tabel in de eerste post is een voorbeeld, in de uiteindelijke array gaan zo 100den tabellen staan.

[ Voor 17% gewijzigd door xandie op 10-06-2013 23:46 ]

[Zeebonk]

Ik ga uit van geen boven limiet aan het aantal mensen per groep: (laat maar horen als ik het mis heb)

combinations = binominal_coef(people, groups) * groups ^ (people - groups)

binominal_coef(people, groups) = aantal mogelijkheden voor de de eis: personen per groep >= 1

groups ^ (people - groups) = aantal mogelijkheden om de rest van de personen in te delen: elk nog niet geplaatste persoon kan in elk van de vijf groepen worden geplaatst.

Invullen voor people = 10, groups = 5:
binominal_coef(10, 5) * 5 ^ (10 - 5)
binominal_coef(10, 5) * 5 ^ 5 = 787.500 combinaties

Dit is een prachtig probleem om recusief uit te werken, maar ik ben bang dat met een taal als VB.NET al snel tegen stack overflows zult aanlopen. Wat je sowiezo zou kunnen doen is eerst alle mogelijkheden van de binominal_coef bepalen, en daarna voor elk gevonden veld de rest van de invulling doen. Dan heb je per onderdeel voor 10 mensen, 5 groepen: binominal_coef(10, 5)=252 combianties en 5^5=3125. Wat volgens mij al een stuk beter op de stack past

[Gomez12]

Hoe bedoel je 100den tabellen?

Als ik 1000 personen heb, dan kan ik die toch kwijt in 1 tabel met in elke groep 200 personen?
Indien dit klopt dan kan je mijn eerder gegeven brute-force taktiek gebruiken.

En het aantal mogelijke combinaties is puur afhankelijk van wat je basis vereisten zijn voor een tabel, wil je een evenredige spreiding (dus met 1000 personen 200 per groep) dan is het vrij simpel uit te rekenen, maar sta je ook een onevenredige spreiding toe (996 personen in 1 groep, rest van de groepen 1 persoon) dan moet je of meer grenzen definieren of je gaat echt gigantisch grote getallen krijgen.

Let er wel op dat er computertechnisch wel een verschil zit tussen theoretisch mogelijke combinaties en daadwerkelijk voorkomende combinaties (binnen een redelijk tijdsbestek) vanwege simpele dingen als dat een computer slechts is in random getallen. Wil jij "snel" 1 miljoen "random" getallen verkrijgen dan gaat dit op je thuiscomputer niet meer random zijn.

En alle combinaties bijhouden, weet waar je aan begint. Dit gaat heel erg snel oplopen en is erg afhankelijk van je condities (zijn bijv bij 5 personen er 5 combinaties mogelijk of slechts 1, en bij 10 personen zijn dat er echt 787.500 (ik geloof zeebonk gelijk ) of zijn dat er een heel stuk minder omdat jij een heleboel gelijk vindt)

[pedorus]

In je voorbeeld heb je 23 personen verdeeld over 5 groepen. Ik doe even 2 aannames:
1. De groepsnummers maken niet uit. Dus 5 personen verdelen over 5 groepen geeft 1 als totaal aantal combinaties en geen 5!
2. Je wilt maximaal 1 verschil hebben tussen het hoogste aantal personen en het laagste aantal.

Het aantal combinaties wordt dan in het voorbeeld van 23 personen 23!/(5!*5!*5!*4!*4!)/3!/2!=2.164.447.024.740
Voor 24 personen wordt het 24!/(5!*5!*5!*5!*4!)/4!/1! en voor 25 personen wordt het 25!/(5!*5!*5!*5!*5!)/5!. Zie het verband.

Het lijkt me duidelijk dat je dit niet in een array gaat stoppen, want anders had je deze vraag niet gesteld.

Zeebonk schreef op dinsdag 11 juni 2013 @ 00:04:
Ik ga uit van geen boven limiet aan het aantal mensen per groep: (laat maar horen als ik het mis heb)

combinations = binominal_coef(people, groups) * groups ^ (people - groups)

Je hebt denk ik last van overlappende combinaties, dus dat geeft ook met afwijkende aannames slechts een upper bound. Probeer anders de 30 combinaties volgens jouw formule bij 6 personen eens uit te schrijven. Volgens mijn methode zijn het er maar 15.

[ Voor 13% gewijzigd door pedorus op 11-06-2013 00:34 . Reden: quote is duidelijker ]

[xandie]

Zeebonk schreef op dinsdag 11 juni 2013 @ 00:04:
Ik ga uit van geen boven limiet aan het aantal mensen per groep: (laat maar horen als ik het mis heb)

Correct, in realiteit zal dit waarschijnlijk nooit hoger dan 50 zijn

combinations = binominal_coef(people, groups) * groups ^ (people - groups)

binominal_coef(people, groups) = aantal mogelijkheden voor de de eis: personen per groep >= 1

groups ^ (people - groups) = aantal mogelijkheden om de rest van de personen in te delen: elk nog niet geplaatste persoon kan in elk van de vijf groepen worden geplaatst.

Invullen voor people = 10, groups = 5:
binominal_coef(10, 5) * 5 ^ (10 - 5)
binominal_coef(10, 5) * 5 ^ 5 = 787.500 combinaties

Dit is een prachtig probleem om recusief uit te werken, maar ik ben bang dat met een taal als VB.NET al snel tegen stack overflows zult aanlopen. Wat je sowiezo zou kunnen doen is eerst alle mogelijkheden van de binominal_coef bepalen, en daarna voor elk gevonden veld de rest van de invulling doen. Dan heb je per onderdeel voor 10 mensen, 5 groepen: binominal_coef(10, 5)=252 combianties en 5^5=3125. Wat volgens mij al een stuk beter op de stack past

Ik heb geen idee wat: binominal_coef betekent (ga ik morgen eens bekijken )

Gomez12 schreef op dinsdag 11 juni 2013 @ 00:12:
Hoe bedoel je 100den tabellen?

Deze tabel komt bijvoorbeeld in arrstrcombinaties(rij, kolom, 1)

Groep 1	Groep 2	Groep 3	Groep 4	Groep 5
Persoon 1	Persoon 3	Persoon 2	Persoon 4	Persoon 8
Persoon 6	Persoon 5	Persoon 10	Persoon 9	Persoon 7
Persoon 12	Persoon 11	Persoon 15	Persoon 17	Persoon 16
Persoon 13	Persoon 18	Persoon 14	Persoon 20	Persoon 23
Persoon 21	Persoon 19	Persoon 22

Deze tabel komt bijvoorbeeld in arrstrcombinaties(rij, kolom, 2)

Groep 1	Groep 2	Groep 3	Groep 4	Groep 5
Persoon 17	Persoon 16	Persoon 1	Persoon 4	Persoon 8
Persoon 12	Persoon 11	Persoon 15	Persoon 3	Persoon 2
Persoon 6	Persoon 5	Persoon 10	Persoon 9	Persoon 7
Persoon 13	Persoon 18	Persoon 14	Persoon 20	Persoon 23
Persoon 21	Persoon 19	Persoon 22

Als ik 1000 personen heb, dan kan ik die toch kwijt in 1 tabel met in elke groep 200 personen?
Indien dit klopt dan kan je mijn eerder gegeven brute-force taktiek gebruiken.

Het zal niet evenredig verdeeld zijn. Een ander programma gaat berekenen hoeveel personen er per groep moeten zijn. Ik wil ze wel +-1 laten afwijken.
Bijvoorbeeld:
Aantal personen: 8
Een ander programma berekent dan het aantal personen per groep.
groep 1: 1
groep 2: 3
groep 3: 2
groep 4: 1
groep 5: 1

Maar, ik wil dan ook alle mogelijke combinaties weten voor +-1 en aantal personen in een groep kan nooit < 0 zijn.
In dit geval wil ik ook volgende combinaties weten:
groep 1: 2
groep 2: 2
groep 3: 2
groep 4: 1
groep 5: 1

groep 1: 1
groep 2: 4
groep 3: 2
groep 4: 1
groep 5: 1

groep 1: 1
groep 2: 2
groep 3: 3
groep 4: 1
groep 5: 1

en zo verder

pedorus schreef op dinsdag 11 juni 2013 @ 00:33:
In je voorbeeld heb je 23 personen verdeeld over 5 groepen. Ik doe even 2 aannames:
1. De groepsnummers maken niet uit. Dus 5 personen verdelen over 5 groepen geeft 1 als totaal aantal combinaties en geen 5!

Fout, de groepsnummers maken wel degelijk uit.
Een persoon die in groep A zit zou misschien gelukkiger zijn als hij in groep B zit.

2. Je wilt maximaal 1 verschil hebben tussen het hoogste aantal personen en het laagste aantal.

Fout, ik wil 1 verschil hebben ten opzichte van het aantal personen dat ik berekend heb. (dat had ik mss niet zo duidelijk vermeld )

Het lijkt me duidelijk dat je dit niet in een array gaat stoppen, want anders had je deze vraag niet gesteld.

Nu ik een beter inzicht krijg in de grootte van de getallen lijkt mij dit inderdaad niet realistisch

@Zeebonk: je hebt denk ik last van overlappende combinaties, dus dat geeft ook met afwijkende aannames slechts een upper bound. Probeer anders de 30 combinaties volgens jouw formule bij 6 personen eens uit te schrijven. Volgens mijn methode zijn het er maar 15.

Dit:

Groep 1	Groep 2	Groep 3	Groep 4	Groep 5
Persoon 1	Persoon 2	Persoon 3	Persoon 4	Persoon 6
				Persoon 5

is hetzelfde als dit:

Groep 1	Groep 2	Groep 3	Groep 4	Groep 5
Persoon 1	Persoon 2	Persoon 3	Persoon 4	Persoon 5
				Persoon 6

Momenteel beginnen er tabellen dansen voor mijn ogen

[Zeebonk]

@pedorus: je hebt gelijk, de binom klopt daar niet. Ik ging wel uit van de relevantie van de groep nummers.

In plaats van de binom neem je dan voor het invullen van de eerste [aantal groepen] mensen:
Product(k=0 to groups, (people - k) * (groups - k))

[pedorus]

xandie schreef op dinsdag 11 juni 2013 @ 01:02:
Fout, de groepsnummers maken wel degelijk uit.
Een persoon die in groep A zit zou misschien gelukkiger zijn als hij in groep B zit.

Dus de groepen doen bijvoorbeeld een andere activiteit. Dat is simpel te verhelpen, de delingen na de ) weg halen in mijn formules. Het lijkt me duidelijk dat de hoeveelheid combinaties nu nog verder toeneemt.

Fout, ik wil 1 verschil hebben ten opzichte van het aantal personen dat ik berekend heb. (dat had ik mss niet zo duidelijk vermeld )

De formule blijft hetzelfde, maar moet dan toegepast worden voor alle toegestane mogelijkheden van de groepsgroottes (en de combinaties tel je op). Dan heb je dus een stukje software nodig om die toegestane mogelijkheden erin te voeren.

[Woy]

xandie schreef op dinsdag 11 juni 2013 @ 01:02:
[...]
Dit:

Groep 1	Groep 2	Groep 3	Groep 4	Groep 5
Persoon 1	Persoon 2	Persoon 3	Persoon 4	Persoon 6
				Persoon 5

is hetzelfde als dit:

Groep 1	Groep 2	Groep 3	Groep 4	Groep 5
Persoon 1	Persoon 2	Persoon 3	Persoon 4	Persoon 5
				Persoon 6

Momenteel beginnen er tabellen dansen voor mijn ogen

Is dat ook hetzelfde als:

Groep 1	Groep 2	Groep 3	Groep 4	Groep 5
Persoon 2	Persoon 1	Persoon 3	Persoon 4	Persoon 6
				Persoon 5

[xandie]

Woy schreef op dinsdag 11 juni 2013 @ 08:16:
[...]

Is dat ook hetzelfde als:

Groep 1	Groep 2	Groep 3	Groep 4	Groep 5
Persoon 2	Persoon 1	Persoon 3	Persoon 4	Persoon 6
				Persoon 5

Incorrect, dat is wel degelijk verschillend. Een andere groep betekent een andere activiteit.

Dus dit is wat ik nu heb:
aantal combinaties is totaalPersonen! /(AantalP1!*AantalP2!*AantalP2!*AantalP3!*AantalP5!)

voorbeeldje:
aantal personen = 23
aantal groep 1= 5
aantal groep 2= 4
aantal groep 3= 6
aantal groep 4= 5
aantal groep 5= 3

aantal mogelijke combinaties = 23! / (5!*4!*6!*5!*3!) = 1.7315576e+13

Visual Basic .NET:

'factorial operation bestaat standaard niet in VB.net
Function Factorial(ByVal number As integer) As double
If number <= 1 Then
Return (1)
Else
Return number * Factorial(number - 1)
End If
End Function 


private sub form_btnoK ...
'De personen worden opgeslagen in arrstrPersonen 
        Dim arrstrPersonen() As String 
        Dim intteller, intAantal As Integer 
        intaantal = InputBox("geef het aantal personen") 
        For intteller = 0 To (intaantal - 1) 
            arrstrpersonen(intteller) = InputBox("Geef persoon " & (intteller + 1)) 
        Next 
  
        'aantal personen per groep
        Dim intLgroepA, intLgroepB, intLgroepC, intLgroepD, intLgroepE As Integer
        intLgroepA = Integer.Parse(txtLgroepA.text)
        '...


        'aantal mogelijke combinaties berekenen (intAantalcombinaties)   
        Dim dblAantalCombinaties As double 
        dblAantalCombinaties =  Factorial(intaantal) / (factorial(intLgroepA) *  factorial(intLgroepB) * factorial(intLgroepC) * factorial(intLgroepD) * factorial(intLgroepE)

        messagebox.show(dblAantalCombinaties.tostring)

        'combinaties opslagen in array  
        ' arrstrcombinaties(persoon, groep, tabelnummer) 
        Dim arrstrCombinaties(,,) As Integer 

        For intteller = 0 To (intaantalCombinaties - 1) 
        arrstrCombinaties(, , intteller) = arrstrPersonen() 
        Next
end sub

Nu is mijn vraag: Hoe kan ik alle mogelijke combinaties in een array opslaan?
Een array zal natuurlijk te klein zijn en in realiteit zal ik het ergens anders moeten opslaan, maar het gaat mij vooral over het principe

Ik zal mijn wiskundige kennis toch nog eens moeten bijwerken .

[Gomez12]

xandie schreef op dinsdag 11 juni 2013 @ 19:17:
[...]
Nu is mijn vraag: Hoe kan ik alle mogelijke combinaties in een array opslaan?
Een array zal natuurlijk te klein zijn en in realiteit zal ik het ergens anders moeten opslaan, maar het gaat mij vooral over het principe

Wat is je doel met het opslaan?

Want ik denk namelijk dat het al veel sneller efficienter is om een andere vorm van opslag te kiezen en dan als laatste stap nog een berekening te doen dan om letterlijk alles uit te schrijven.

[xandie]

Gomez12 schreef op dinsdag 11 juni 2013 @ 20:42:
[...]

Wat is je doel met het opslaan?

Want ik denk namelijk dat het al veel sneller efficienter is om een andere vorm van opslag te kiezen en dan als laatste stap nog een berekening te doen dan om letterlijk alles uit te schrijven.

Wel mijn eigenlijke doel is dat het programma mensen uit een database gaat halen en die dan bij een groep in te delen. In de database staat per persoon per groep een score tussen 0 en 10 die weergeeft hoe graag ze in die groep zitten. 10 is ik wil hier heel graag inzitten, 0 is ik wil hier absoluut niet in zitten.
Elke groep moet ook 1 groepsleider bevatten. De personen hebben in de database aangegeven of ze dat willen doen of niet.
Ook zijn er relaties tussen de personen. Standaard wil iedereen even graag met elkaar in een groep zitten en krijgt die relatie 5 punten. Als mensen dit cijfer groter maken wilt dit zeggen dat ze graag met die persoon in een groep willen zitten en als ze dit cijfer kleiner maken willen ze niet bij die persoon in de groep.
Op basis van die gegevens kan je dan de maximale score en verdeling berekenen.

Mijn bedoeling was om alle mogelijke combinaties te berekenen en dan die verdelingen door een ander programma te halen die de optimale score berekent. Nu ik weet dat het zoveel verdelingen zijn moet ik dus efficienter gaan zijn met de mogelijke combinaties te berekenen.Ik zou bijvoorbeeld al in het begin kunnen gaan zien of elke groep een groepsleider bevat en dat ik dan enkel diegene die daar aan voldoen ga opslaan.

Maar nu zit ik vast op hoe ik alle mogelijke combinaties kan berekenen, ik zou dan natuurlijk enkel de combinaties opslaan die aan de voorwaarde voldoen dat er in elke groep een groepsleider zit.

(misschien moet ik het projectje gewoon even laten liggen tot ik wat meer programmeer ervaring heb )

[Gomez12]

Waarom zou je alle combinaties moeten berekenen om een optimale score te berekenen?

Ik zou zeggen begin gewoon met indelen, pas op het punt dat je met meerdere mogelijkheden hetzelfde puntenaantal behaalt sla je deze tussenresultaten op. Dan bereken je alle posities vanuit dit tussenresultaten en elk minder voordelig pad laat je vallen. Heb je nog maar 1 pad over dan kan het tussenresultaat weg totdat je weer op een punt komt dat er meerdere paden zijn.

Een pad wat niet het voordeligste is moet je simpelweg niet opslaan maar zo snel mogelijk kwijtraken.

Bij dit soort vragen is het de kunst om zo snel mogelijk zo veel mogelijk te elimineren, niet alles maar uit gaan brute-forcen en dan over die resultaten te gaan rekenen.

[pedorus]

In plaats van intLgroepA t/m E is een array handiger. Voor het genereren kun je kijken naar manieren waarop permutaties worden gegenereerd. Je maakt hier permutaties van personen. Hier heb je een extra voorwaarde: binnen een groep moeten de getallen van de personen oplopen (om dubbelen te voorkomen).

Of met groepsleiders: binnen een groep moet de eerste een groepsleider zijn, en moeten de getallen van de andere personen oplopen.

Gomez12 schreef op dinsdag 11 juni 2013 @ 21:20:
Waarom zou je alle combinaties moeten berekenen om een optimale score te berekenen?

Vanwege NP-compleetheid valt er wellicht weinig uit te sluiten?

Maar alle combinaties afgaan gaat dus alleen voor kleinere gevallen. Dat is bij een roosterprobleem, wat dit is, wat ongebruikelijk.

[Gomez12]

pedorus schreef op dinsdag 11 juni 2013 @ 21:34:
Vanwege NP-compleetheid valt er wellicht weinig uit te sluiten?

Ik zou zeggen, toon eerst maar eens de NP-compleetheid noodzakelijkheid aan

Ik zie vooralsnog geen noodzaak om niet te kunnen reduceren, wellicht dat je (in theorie want ik zie even niet hoe) niet de 100% optimale indeling krijgt, maar dan krijg je iets van een 99,9% optimale indeling in 1/10000e van de tijd.

[_js_]

Volgens mij is er op dit forum eens een programming contest geweest waarin dezelfde vraag werd gesteld, maar dan met mensen die bij elkaar in vakantiehuisjes moesten slapen, je kunt dat topic eens opzoeken en kijken of daar nog wat ideeën of code tussen staat waar je wat mee kunt.

[SmiGueL]

_js_ schreef op dinsdag 11 juni 2013 @ 23:46:
Volgens mij is er op dit forum eens een programming contest geweest waarin dezelfde vraag werd gesteld, maar dan met mensen die bij elkaar in vakantiehuisjes moesten slapen, je kunt dat topic eens opzoeken en kijken of daar nog wat ideeën of code tussen staat waar je wat mee kunt.

Programming Contest Nieuwe Stijl: Contest 3 *uitslagen!* ?

Ziet er nog wel wat ingewikkelder uit

[ Voor 5% gewijzigd door SmiGueL op 12-06-2013 00:05 ]