---

Jeg har vist brug for hjælp fra en matematiker her. :)

Der skal vælget noget tilfældigt ud fra en liste. Hvert element på listen
har en "vægt". Hvis element A har dobbelt så stor vægt som element B, skal
A have dobbelt så stor sandsynlighed for at blive valgt.

Jeg har fundet én algoritme som virker, men er ret fjollet.
En ny liste, hvor hvert element optræder lige så mange gange, som det tal,
der står som vægt. Så er det bare at vælge et helt tilfældigt element i
listen.
Men som sagt synes jeg det virker ret fjollet.

En anden metode er, at gange vægten med et tilfældigt tal, mellem 0 og 1.
Altså en ny faktor for hvert element.
Meget simpelt, og større vægt giver større sandynlighed. Men "spredningen"
bliver alt for stor. Altså dobbelt vægt gav *langt* større sandsynlighed,
end blot dobbelt så meget.

Det ser ud som om jeg er på rette spor, men jeg aner ikke hvordan jeg
kommer videre... :)

Selve måden at definere vægten på kunne godt gøres anderledes, men jeg ved
ikke lige hvordan det skulle være.

--
Mvh.

Niels Andersen
(la nels. anersyn.)

---

Niels Andersen <niels-usenet@myplace.dk> writes:

> Jeg har vist brug for hjælp fra en matematiker her. :)
>
> Der skal vælget noget tilfældigt ud fra en liste. Hvert element på listen
> har en "vægt". Hvis element A har dobbelt så stor vægt som element B, skal
> A have dobbelt så stor sandsynlighed for at blive valgt.

Jeg antager at vægtene er heltallige.

Start med at tælle alle vægtene sammen. Vælg så et tilfældigt tal mellem
1 og den samlede vægt. Start så fra den ene ende i listen of læg vægtene
sammen igen indtil du til eller over til det valgte tal. Det sidste tal
hvis vægt du lagde til er det du skal bruge.

Dette kan være langsomt, da det tager tid proportionalt med listens
længde at finde hvert tal. Til gengæld kan man fjerne elementer fra
listen i konstant tid (afhængigt af representationen af listen).

Man kan også lave en liste af "afsnits-summene" af vægtene op til
hvert nummer. Den vil være voksende, så man kan lave binær søgning
i den og finde det udvalgte tal i logaritmisk tid.

Håber det hjælper
/L
--
Lasse Reichstein Nielsen - lrn@hotpop.com
'Faith without judgment merely degrades the spirit divine.'

---

Lasse Reichstein Nielsen wrote:

> Man kan også lave en liste af "afsnits-summene" af vægtene op til
> hvert nummer. Den vil være voksende, så man kan lave binær søgning
> i den og finde det udvalgte tal i logaritmisk tid.

....men fjerne elementer i liniær tid. Måske man kunne lave et binært
træ i stedet med summen af vægtene af underliggende knuder placeret
i hver knude. Så vil søgning, indsættelse og fjernelse af elementer
tage logaritmisk tid. Men det er også en hel del mere kompliceret end
de andre løsninger.

-Claus

---

Lasse Reichstein Nielsen wrote in <hej22vg1.fsf@hotpop.com>:
>> Der skal vælget noget tilfældigt ud fra en liste. Hvert element på listen
>> har en "vægt". Hvis element A har dobbelt så stor vægt som element B,
>> skal A have dobbelt så stor sandsynlighed for at blive valgt.

> Jeg antager at vægtene er heltallige.

Helt i orden, det er de da bare så. :)

> Start med at tælle alle vægtene sammen. Vælg så et tilfældigt tal mellem
> 1 og den samlede vægt. Start så fra den ene ende i listen of læg vægtene
> sammen igen indtil du til eller over til det valgte tal. Det sidste tal
> hvis vægt du lagde til er det du skal bruge.

Det lyder en del mere matematisk end min bonde-metode. :)

Jeg må jo så prøve at skrive noget fornuftigt kode ud fra det. Jeg havde
håbet at finde en metode der kan skrive som et database-kald, men det kan
jeg vist ikke med denne. :)

> Dette kan være langsomt, da det tager tid proportionalt med listens
> længde at finde hvert tal.

Yeps. Problemet er heller ikke listens længde, jeg er så heldig at vi
snakker nok 10 elementer, i hvert fald ikke over 50.
Min bekymring er mere, at det skal gøres relativt tit.

Nå, men tak for hjælpen, jeg tror det var det svar, jeg skulle have. :)

--
Mvh.

Niels Andersen
(la nels. anersyn.)

---

Scripsit Niels Andersen <niels-usenet@myplace.dk>
> Lasse Reichstein Nielsen wrote in <hej22vg1.fsf@hotpop.com>:

> >> Der skal vælget noget tilfældigt ud fra en liste. Hvert element på listen
> >> har en "vægt". Hvis element A har dobbelt så stor vægt som element B,
> >> skal A have dobbelt så stor sandsynlighed for at blive valgt.

> > Jeg antager at vægtene er heltallige.

> Helt i orden, det er de da bare så. :)

Det er ikke nødvendigt for at Lasses metode virker.

> > Start med at tælle alle vægtene sammen. Vælg så et tilfældigt tal mellem
> > 1 og den samlede vægt. Start så fra den ene ende i listen of læg vægtene
> > sammen igen indtil du til eller over til det valgte tal. Det sidste tal
> > hvis vægt du lagde til er det du skal bruge.

> Det lyder en del mere matematisk end min bonde-metode. :)

Nej. Prøv at læs det igen, og forsøg at lad være med at være imponeret
af at det er skrevet af en der ved hvad han snakker om.

> Yeps. Problemet er heller ikke listens længde, jeg er så heldig at vi
> snakker nok 10 elementer, i hvert fald ikke over 50.

Så er det næppe besværet værd at forsøge at være smart (med binære
træer eller andet halløj som Clause foreslår).

--
Henning Makholm "Det må være spændende at bo på
en kugle. Har I nogen sinde besøgt de
egne, hvor folk går rundt med hovedet nedad?"

---

Henning Makholm <henning@makholm.net> writes:
> Scripsit Niels Andersen <niels-usenet@myplace.dk>

> Det er ikke nødvendigt for at Lasses metode virker.

Søreme nej, jeg er vist for vant til at min rand() returnerer en int :)

> > Det lyder en del mere matematisk end min bonde-metode. :)
>
> Nej. Prøv at læs det igen, og forsøg at lad være med at være imponeret
> af at det er skrevet af en der ved hvad han snakker om.

Ja, jeg skulle måske have uddybet konstruktionen lidt mere. Det er
nemmelig "næsten præcis" den samme metode som at lade hvert element
optræde mere end en gang i listen.

Den "samlede vægt" er jo netop længden af den liste hvor hvert element
optræder lige så mange gange som sin vægt. Man undgår bare at lave
listen, og sparer derfor noget plads. Til gengæld skal man betale lidt
ekstra tid for at finde ud af hvad der ville have stået på den
udvalgte plads i listen.

Hvad der er smartest at gøre afhænger helt af
- hvor mange elementer der er i listen (få, mange eller et astronomisk antal)
- hvor store vægtene er, og om de er heltal (f.eks, svært at lave en ny liste
hvor et element optræder halvanden gang :))
- Hvilke andre operationer man vil lave på den oprindelige liste
(f.eks. tilføje/fjerne elementer, ændre vægte), og hvor
ofte man gør det i forhold til at finde et tilfældigt tal.

Hvis det er en kort liste som ikke skal ændres fra gang til gang, og
med små, heltallige vægte, og hvor man skal slå op mange gange, så
tror jeg at jeg ville bruge din oprindelige metode: bygge en liste
hvor hvert element optræder lige så mange gange som sin vægt, og så
vælge et tilfældigt element i den liste.

/L
--
Lasse Reichstein Nielsen - lrn@hotpop.com
'Faith without judgment merely degrades the spirit divine.'

---

"Niels Andersen" <niels-usenet@myplace.dk> wrote in message
news:w5iY8.3804$Yf1.303145@news010.worldonline.dk...

> Der skal vælget noget tilfældigt ud fra en liste. Hvert element på listen
> har en "vægt". Hvis element A har dobbelt så stor vægt som element B, skal
> A have dobbelt så stor sandsynlighed for at blive valgt.

Der er allerede foreslået binær søgning i den kumulerede vægt.

Jeg vil blot bidrage med en alternativ løsning. Så har du lidt at vælge
mellem

Algoritme: (kaldes "rejection method")
Vælg et tilfældigt element (uniformt fordelt)
Vælg et tilfældigt tal i [0 ... max vægt[ (kan vælges som heltal hvis alle
vægtene er heltal)
Hvis det valgte elements vægt er mindre end eller lig med det tilfældige
tal, så start forfra (rejection).

Fordele ved denne algoritme:
- Kan anvendes selvom man har "uendeligt mange" elementer (fx. et reelt
interval)
- Kører i konstant tid, under milde forudsætninger. Ingen forud-beregninger
på vægtene kræves (her kan der jo ellers indsnige sig lineær tid, hvis man
ikke skal bruge ret mange udtrækninger)

Forudsætninger for at algoritmen er god:
- Max-vægten er begrænset
- Gennemsnitsvægten er ikke meget lille i forhold til max-vægten. Fx. halvt
så stor ville være glimrende.


Mvh. Bjarke

---

Bjarke Dahl Ebert wrote in <6tmY8.3965$Yf1.341799@news010.worldonline.dk>:

>> Der skal vælget noget tilfældigt ud fra en liste. Hvert element på listen
>> har en "vægt". Hvis element A har dobbelt så stor vægt som element B,
>> skal A have dobbelt så stor sandsynlighed for at blive valgt.

> Algoritme: (kaldes "rejection method")

Hey, den kan jeg lide! Det er nemlig lykkedes mig at lave hele algoritmen i
en database-forespørgsel. :)

Til de nysgerrige:
SELECT id FROM tabel WHERE RAND()*12<weight ORDER BY RAND() LIMIT 1

Jeg har her defineret vægt-skalaen til at gå fra 0-12. (hvor 0 er "skal
slet ikke udvælges").

Der er en teoretisk risiko for, at der ikke kommer nogen resultater, så
lige den ene ting må jeg tage hensyn til i programmet.

Den er godt nok ikke så god, hvis der er mange elementer (da beregningen
foretages mindst én gang på alle elementer), men det er der heldigvis ikke
her. :)

Jeg har lavet en test med 10.000 forespørgsler, og fordelingen så ganske
nydelig ud. Der var vist ikke mere fejl end der skal være, når det klares
med tilfældighed. :)

Jeg siger mange tak for jeres hjælp, det kunne ikke være bedre. :)

--
Mvh.

Niels Andersen
(la nels. anersyn.)

---

"Niels Andersen" <niels-usenet@myplace.dk> wrote in message
news:iWwY8.4829$Yf1.388336@news010.worldonline.dk...
> Bjarke Dahl Ebert wrote in <6tmY8.3965$Yf1.341799@news010.worldonline.dk>:
>
> > Algoritme: (kaldes "rejection method")
>
> Hey, den kan jeg lide! Det er nemlig lykkedes mig at lave hele algoritmen
i
> en database-forespørgsel. :)
>
> Til de nysgerrige:
> SELECT id FROM tabel WHERE RAND()*12<weight ORDER BY RAND() LIMIT 1

Jer er bange for at det er en forkert implementation af "rejection method".
Elementer med store vægte vil have for stor sandsynlighed for at blive
valgt.
Antag at der er 1000 elementer med vægt 1 og kun ét element med vægt 2.
Dette ene element vil blive valgt hver anden gang!

Det du i stedet skal gøre, er at vælge et tilfældigt element i databasen
(uden at se på vægt). Derefter skal du med "rejection method" afgøre om
dette elements vægt er stor nok. Hvis ikke, starter du forfra (med et nyt
tilfældigt tal at sammenligne med)


Bjarke

---

"Bjarke Dahl Ebert" <bebert@worldonline.dk> writes:

> "Niels Andersen" <niels-usenet@myplace.dk> wrote in message
> news:iWwY8.4829$Yf1.388336@news010.worldonline.dk...
>
> > Til de nysgerrige:
> > SELECT id FROM tabel WHERE RAND()*12<weight ORDER BY RAND() LIMIT 1
>
> Jer er bange for at det er en forkert implementation af "rejection method".
> Elementer med store vægte vil have for stor sandsynlighed for at blive
> valgt.
> Antag at der er 1000 elementer med vægt 1 og kun ét element med vægt 2.
> Dette ene element vil blive valgt hver anden gang!

Ikke at jeg er en haj til SQL, men jeg tror RAND() bliver beregnet
påny for hvert række i tabellen. Altså vil elementer med vægt 1 have
1/12 chance for at komme med i "anden runde", og dem med vægt 2 vil
have 2/12 chance. Det eneste problem er at det kan gå galt hvis ingen
af elementerne overlever den første sortering. Så er der ikke et element
at vælge til sidst.

Jeg tror dog heller ikke fordelingen bliver helt korrekt. Hvis vi
sætter max-vægt til 2, og har tre elementer, to med vægt 1 (a,b) og et
med vægt 2 (c), så har hvert element med vægt 1 netop 50% chance for
at overleve første sortering, så de mulige resultater før (ORDER
BY...) er (med 25% sandsynlighed for hver:

1) c
2) a c
3) b c
4) a b c

Derefter vælger vi en tilfældig af disse (uniformt
tilfældigt). Sandsynligheden for at ende med element c er så:

1) 100%
2) 50%
3) 50%
4) 33%

Da hver af disse disjunkte muligheder har sandsynlighed 25% bliver
den samlede sandsynlighed for at vælge c præcist:

25% + 12.5% + 12.5% + 8.33% = 58.33%

Sandsynligheden skulle kun have været 50%, så et eller andet er galt.

> Det du i stedet skal gøre, er at vælge et tilfældigt element i databasen
> (uden at se på vægt). Derefter skal du med "rejection method" afgøre om
> dette elements vægt er stor nok. Hvis ikke, starter du forfra (med et nyt
> tilfældigt tal at sammenligne med)

Han har gjort det lidt omvendt. Først tager han alle elementerne og se
om de ville blive rejected, derefter tager han en tilfældig ud der
ikke er rejected. Som sagt kan det gå galt. Rejection metoden kan bruge
arbitrært mange forsøg før den finder et element, og SQL-metoden forsøger
at gøre de samme med et fast, endeligt antal forsøg.

/L
--
Lasse Reichstein Nielsen - lrn@hotpop.com
'Faith without judgment merely degrades the spirit divine.'

---

Niels Andersen wrote in <iWwY8.4829$Yf1.388336@news010.worldonline.dk>:
>> Algoritme: (kaldes "rejection method")
> Til de nysgerrige:
> SELECT id FROM tabel WHERE RAND()*12<weight ORDER BY RAND() LIMIT 1

Da jeg præsenterede den for database-gruppen fik jeg et andet foreslag, som
jeg så bruger nu:

SELECT id FROM tabel WHERE weight>0 ORDER BY RAND()/weight ASC LIMIT 1

Denne metode har flere fordele. Jeg behøver ikke kende skalaen. Jeg er
sikker på altid at få et svar retur. Den simplere, hvilket jo altid er
godt. :)

Jeg har testet begge SQL'er med 10.000 prøver, og de giver begge en vældig
fin fordeling. Den ligger meget tæt op ad vægt-fordelingen, forskellen
tilskriver jeg tilfældigheden.

Jeg må nok hellere forklare hvad den gør. :)

Først udvælges alle, som har en vægt over nul.
For hver genereres der et tilfældigt tal mellem 0 og 1, som divideres med
vægten.
De sorteres så efter dette tal i stigende rækkefølge, og den første
udvælges, altså den, som gav det mindste tal.

Jeg synes det tydeligt fremgår, at større vægt giver større sandsynlighed
for udvælgelse. Men jeg har ikke beregnet på om fordelingen bliver korrekt.

I stedet har jeg, som sagt, testet det. Det ser ganske fint ud, og blive
taget i brug i dag. Så må tiden vise om fordelingen bliver lige så god når
det bruges til det, det er lavet til. :) (Men hvorfor skulle den ikke det?)

--
Mvh.

Niels Andersen
(la nels. anersyn.)

---

Niels Andersen <niels-usenet@myplace.dk> writes:

> Niels Andersen wrote in <iWwY8.4829$Yf1.388336@news010.worldonline.dk>:
> >> Algoritme: (kaldes "rejection method")
> > Til de nysgerrige:
> > SELECT id FROM tabel WHERE RAND()*12<weight ORDER BY RAND() LIMIT 1
>
> Da jeg præsenterede den for database-gruppen fik jeg et andet foreslag, som
> jeg så bruger nu:
>
> SELECT id FROM tabel WHERE weight>0 ORDER BY RAND()/weight ASC LIMIT 1
>
> Denne metode har flere fordele. Jeg behøver ikke kende skalaen. Jeg er
> sikker på altid at få et svar retur. Den simplere, hvilket jo altid er
> godt. :)
>
> Jeg har testet begge SQL'er med 10.000 prøver, og de giver begge en vældig
> fin fordeling. Den ligger meget tæt op ad vægt-fordelingen, forskellen
> tilskriver jeg tilfældigheden.

Ikke kun. Hvis man tager et simpelt tilfælde, et element med vægt 1
(a) og et element med vægt 2 (b).
Så sammenligner vi RAND() og RAND()/2. Sandsynligheden for at den første
er mindst er kun 1/4 (se tegning nedenfor) og ikke 1/3 som den skulle være.
Så, der er et eller andet galt med fordelingen.

Tegning: samtlige mulige udfald for RAND() og RAND()/2 ligger i firkanten
[0...1]*[0...1/2]
Jeg markerer (*) de udfald hvor a blive valgt, da RAND() er mindst:

RAND()
^
1 +----------------------------------+
| |
| |
| |
| |
| |
| |
1/2_| |
| *|
| ******|
| ***********|
| ****************|
| *********************|
| **************************|
| *******************************| RAND()/2
0 +----------------------------------+>
0 1/2

Alle udfald er lige sandsynlige, så derfor er der 1/4 chance for at vælge a.

/L
--
Lasse Reichstein Nielsen - lrn@hotpop.com
'Faith without judgment merely degrades the spirit divine.'

---

Lasse Reichstein Nielsen wrote in <8z4c80qz.fsf@hotpop.com>:
>> SELECT id FROM tabel WHERE weight>0 ORDER BY RAND()/weight ASC LIMIT 1
[...]
>> Jeg har testet begge SQL'er med 10.000 prøver, og de giver begge en
>> vældig fin fordeling. Den ligger meget tæt op ad vægt-fordelingen,
>> forskellen tilskriver jeg tilfældigheden.
>
> Ikke kun. Hvis man tager et simpelt tilfælde, et element med vægt 1
> (a) og et element med vægt 2 (b).

Søreme så, så er sandsynligheden for b 3/4. Det er da unægteligt et stykke
fra de 2/3 det skulle have været.

Well, som sagt gik det fint med min prøve. Jeg tror det går alligevel, det
behøver ikke være så nøjagtigt.

Det ser ud til at hvis det skal gøres præcist bliver det ikke så simpelt.
Og jeg vil egentlig hellere have det simpelt, og bare præcist nok. :)

Med den valgte løsning skriver jeg blot et tal som vægt, med den skala jeg
lige lyst til. Udvælgelsen foregår med en simpel SQL-query. Perfekt. :)

Jeg vil dog forsøge at huske de andre metoder jeg har lært. Jeg kan se at
det giver mere korrekte resultater, og i et større projekt er det jo heller
ikke så vanskeligt at lave. :)

--
Mvh.

Niels Andersen
(la nels. anersyn.)

---

"Bjarke Dahl Ebert" <bebert@worldonline.dk> writes:

> Jeg vil blot bidrage med en alternativ løsning. Så har du lidt at vælge
> mellem
>
> Algoritme: (kaldes "rejection method")
> Vælg et tilfældigt element (uniformt fordelt)
> Vælg et tilfældigt tal i [0 ... max vægt[ (kan vælges som heltal hvis alle
> vægtene er heltal)
> Hvis det valgte elements vægt er mindre end eller lig med det tilfældige
> tal, så start forfra (rejection).

Vældig snedig algoritme! Det tog mig lidt tid at tjekke at den faktisk
giver den rigtige fordeling (men jeg var også dum og glemte et led :).
Men ikke bare det, man behøver, så vidt jeg kan se, ikke bruge "max
vægt". Man kan bruge ethvert tal der er større end eller lig med max
vægten, og det virker stadig, bare langsommere. Wicked!

/L
--
Lasse Reichstein Nielsen - lrn@hotpop.com
'Faith without judgment merely degrades the spirit divine.'

---

Niels Andersen wrote:
> Jeg har fundet én algoritme som virker, men er ret fjollet.
> En ny liste, hvor hvert element optræder lige så mange gange, som
> det tal, der står som vægt. Så er det bare at vælge et helt
> tilfældigt element i listen.
> Men som sagt synes jeg det virker ret fjollet.

Hvis du ønsker at optimere hastigheden på et tabel opslag uden at
tænke på plads forbrug så lyder det som en fornuftig måde at løse
problemet på. Hvis du kun har få elementer, så ville jeg sige at
det er overkill at gøre det på nogen anden måde.

Hvis dine elementer er store, så kan du kan evt. altid lave en
tabel, der indeholder numret på elementet i en anden tabel.
så er det kun en tabel af integers. Men det afhænger også af
hvor stor sandsyneligheden er for det mindst sandsynelige
element er og hvor præcist du vil estimere denne.

Ellers ville jeg sortere elementer så de mest sandsynelige
står først, dvs. sortere decending efter vægt, og til hver
vægt addere summen af alle tidligere vægte, så er det blot
at vælge et tilfældigt tal mellem 0 og summen af alle vægte,
og finde det første element i tabellen med sumvægt>=tilfældigt tal.

Da listen er præsorteret vil de mest sandsynelige testes før
alle de andre. Så den minst sandsynelige koster mest at finde.
Så søgningen er stadig linær i n.

--
Mvh. Carsten Svaneborg
Where do you not want to go tomorrow:
http://www.softwarepatenter.dk