WisFaq!

Combinaties algoritme

Hoi,

Ik zit met het volgende probleem. Ik probeer met een computeralgoritme alle mogelijke combinaties van de volgende situatie te hanteren:

Als ik een land heb met S spots (noem het steden).
En ik heb M mensen. Voorts heeft elke stad ook nog een bepaalde maximum capaciteit C.

Op hoeveel manieren kan ik de mensen M over de steden S verdelen, rekening houdend met de maximale capaciteit per stad?

In werkelijkheid is mijn probleem nog iets complexer, maar dit is mijn basis vraag.

Ik wil al deze mogelijkheden in een computeralgoritme zetten.

Als ik los elke persoon 1 voor 1 zou plaatsen op een van de beschikbare locaties zou ik heel veel combinaties dubbel tellen met hetzelfde effect. En dat wil ik niet.

Voorbeeld:

Ik heb 25 mensen
Ik heb drie Steden
S1: max 14
S2: max 10
S3: max 8

Mijn eindresultaat zou alle mogelijke getallen sets moeten weergeven:

V1 = {14, 10, 1}
V2 = {13, 10, 2}
V3 = {12, 10, 3}
V? = {10, 10, 5} etc.

In mijn situatie zijn alle waarden variabelen, zowel het aantal mensen, het aantal steden, de minimumstapgrootte (aantal mensen dat in veelvoud in een stad moet komen; kan 1 zijn maar ook een hogere waarde), de capaciteit.

Bij voorbaat dank voor jullie inzichten,

Maikel
4-11-2013

Antwoord

Hoi Maikel,

Zoals als ik het begrijp gaat het om het aantal mensen. In die zin kan ik die mensen vergelijken met m gelijke knikkers. Dit maakt uit, want als ik elke persoon ook nog eens als een afzonderlijk individu beschouw, kom je op een totaal ander antwoord. De steden kun je zien als verschillende bakjes, indien de bakjes niet verschillend zijn, krijg je wederom een ander antwoord.Echter steden kun je denk ik zien als verschillende bakjes. de vergelijking wordt dan als volgt:

s1+s2+s3+s4.......sn=m Onder de voorwaarde dat ( minimum hoeveelheid en maximum hoeveelheid), Waarbij si staat voor een positief integer getal).

Het probleem is nu dat de vraag op hoeveel manieren dit kan, van een geheel andere orde is als de vraag welke manieren dit dat zijn!

Laten we van het volgende uitgaan:
Alle mensen zijn hetzelfde ( kortom allemaal dezelfde knikkers)
Alle steden zijn verschillend ( kortom allemaal verschillende bakjes)
Per stad is het aantal inwoners tussen de [0-C] 0 mensen en C mensen zijn dus mogelijk.

Dit probleem is op te lossen met een machtsreeks ( weet niet of je hier bekent mee ben?)

Per stad geldt:
$
(1 + x^0 + x^1 + x^2 ....... + x^c )
$

Stel we hebben n steden. Dan geldt voor de totaal aantal mogelijke verdelingen onder de gegeven voorwaarden.

$
\begin{array}{l}
(1 + x^0 + x^1 + x^2 ....... + x^c )^n = (\frac{{1 + x^{c + 1} }}{{1 - x}})^n \\
(1 + x^{c + 1} )^n .(1 - x)^{ - n} = \sum\limits_{p = 0}^n {(C_p^n x^{n(c + 1)} )} .\sum\limits_{p = 0}^n {(C_p^{ - n} ( - x)^n )} \\
\end{array}
$

n= aantal steden
c= maximaal per stad
m= totaal aantal mensen
C= combinatie van n boven p

Het aantal verdelingen van de m mensen is dan gelijk aan het coëfficiënt van x^m van de hierboven gegeven formule.

Dan heb je nog maar slechts het aantal mogelijkheden. Welke deze dan zijn is een heel ander verhaal. Daar zou je een computer algoritme voor moeten hebben, en laat dat nu eens precies zijn wat je wil maken, toch?

DvL

DvL
4-11-2013