🚀 go-pugleaf

<apardon@trout.vub.ac.be> writes:

> Het probleem is als volgt.
> 
> Ik heb een tabel met statistische gewichten.
> De tabel bevat n elementen waarvan er k
> moeten gekozen worden. Voor elke keuze
> die gemaakt wordt moet de kans dat een
> element er uit gekozen wordt gelijk zijn
> aan zijn gewicht gedeeld door het totaal
> gewicht (van de overblijvende elementen)
> Herhalingen zijn niet toegestaan.
> 
> Kent iemand daar een efficient algoritme voor?
> 

Als ik je goed begrijp, dan is die aanpassing die je beschrijft
nergens voor nodig. Je aanpassing verandert de relatieve
waarschijnlijkheden niet, je normaliseert ze terug om ze als som 1 te
geven.

Laten we het probleem wat formeler stellen.

Gegeven: een verzameling met n elementen x_1, ..., x_n
         n gewichten p_1, ..., p_n met als eigenschap dat de som van de p_i 1 
is. 
         een geheel getal k < n

Gevraagd: een deelverzameling S = {x_i1,...,x_ik} met k elementen zodat de 
kans dat x_i een element is van S gelijk is aan p_i.

Eerst een "naief" algoritme:

S={}
while(#S<>k)
do
{selecteer een element x_i rekening houdend met de gegeven gewichten}
if(not x_i in S) then S=S+{x_i} fi
od

De manier om zo een element te selecteren gaat als volgt: genereer een
random getal X tussen 0 en 1.

Als 0<=X<p_1 kies x_1
Als p_1<=X<p_1+p2 kies x_2
Als p_1+p_2<=X<p_1+p_2+p_3 kies x_3
...
Als p_1+p_2+...+p_{n-1}<=X<1 kies x_n

Nu wat optimizaties:

Dit algoritme kan natuurlijk heel lang draaien aangezien we altijd op
een element kunnen vallen dat we al gekozen hebben. Dit wordt erger
naarmate k groter wordt en zou heel erg kunnen zijn voor k=n-1 met een
aantal erg kleine p_i's. We kunnen ervoor zorgen dat k altijd kleiner
of gelijk is aan n/2 door voor k>n/2 het probleem te transformeren
naar het duaal probleem van het kiezen van n-k elementen die wegvallen
met aangepaste p_i.

In bovenstaande methode om een element te selecteren moeten nogal wat
vergelijkingen gemaakt worden. De methode komt eigenlijk neer op een
plaats te zoeken in een gesorteerde tabel en doet dit met een O(n)
algoritme. Je kunt uiteraard binary search gebruiken om dit tot O(log
n) te herleiden. Dit kan zelfs nog verder herleid worden tot een O(1)
bewerking via de methode van Walker. Het is een beetje lang om hier in
te typen en te motiveren, maar je vind het bijvoorbeeld in Knuth,
Vol. 2.

Afhankelijk van je soort van verdeling van gewichten zijn er nog
andere technieken. Voor bovenstaande methode helpt het als de
gewichten niet al te sterk in grootte orde verschillen.

-- 
Lieven Marchand <mal@bewoner.dma.be>
Lambda calculus - Call us a mad club