[php] Een soort kansberekening

[Verwijderd]

Ik zit met een klein probleempje. Ik heb een tabel vol met foto's. Deze wil ik random op een pagina zetten. Maar mensen kunnen ook stemmen op een foto.
De foto met de meeste stemmen moet ook de meeste kans hebben om te worden geplaatst.

Ik had het ongeveer zo gedacht:
als de foto tussen de 75% en 100% van de stemmen zit draait de foto 4x mee in een selectieronde. Tussen de 50% en 75% 3x, 25% en 50% 2x en 0% en 25% 1x.

Ik vroeg me af hoe dit algoritme eruit moet zien. Ik zit me al helemaal suf te piekeren.

Iemand ?

[ACM]

Als je die getallen van je pakt kom je al behoorlijk ver lijkt me?

Eventueel doe je het zo:
Bepaal een treshold, bijv alles wat 1x mee mag draaien op (totaal is 4+3+2+1 = 10) 1/10e van het totaal aantal stemmen.

Vervolgens neem je:
(1/10,2/10), (2/10-4/10) etc als bereiken en bereken je een random getal.

Dat random getal moet tussen 0 en 1 liggen en kan dus binnen een van de bereiken vallen (met een grotere kans voor de vaker gestemde foto's)

Vervolgens bereken je die selectie (alle foto's die dus een waarde in dat bereik hadden) en daar selecteer je random weer eentje uit.

Met een hoop schuren en schaven kan je dat een aardige oplossing opleveren

[Infinitive]

Misschien moet je het wat handiger aanpakken. Wat denk je van iets als:

1. Tel het totaal aantal stemmen op (dus van alle foto's bij elkaar).
2. Neem een random getal tussen 1 en het aantal stemmen (of 0 en het aantal stemmen-1).
3. Vervolgens ga je alle foto's af en tel je het aantal stemmen per foto bij elkaar op totdat je bij de foto bent aanbeland waarbij het totaal >= het random getal dat je getrokken hebt.
Dus iets als:
- het totaal aantal stemmen is 200. Je trekt 120. Vervolgens ga je naar de eerste foto. Die heeft 5 stemmen. 0+5 <= 120? Nee. tel 5 bij de 0 op. Volgende foto. Die heeft 10 stemmen. 5+10 <= 120? Nee. tel 10 bij de 5 op. Volgende foto. Deze heeft 100 stemmen. 15+100 <= 120? Nee. Tel 100 bij de 15 op. Volgende foto. Deze heeft 20 stemmen. 20+115 <= 120? Ja. Deze foto heb je uitgekozen.

Nadeel is alleen dat dit nogal inefficient is wanneer je veel foto's hebt. En dat je dit proces voor elke foto die je op de pagina wilt hebben, moet herhalen (waarbij je de al geplaatste foto's uit zowel het totaal als uit de rij die je langs loopt weglaat (via een if-je)).

(* om het random getal te bepalen met het gebruik van een random generator die tussen 0-1 een antwoord geeft, dit getal vermenigvuldigen met het aantal stemmen. Je krijgt dan een waarde tussen 0 en aantal stemmen-1).

Een verbetering zou zijn:
- bij de foto's houd je de cumulatieve som van de stemmen tot de opgegeven foto bij.
- stel de de random foto index is i.
- dan kan je nu via een binaire zoekalgoritme zoeken naar die bepaalde foto. (e.g. pak de middelste foto. is i <= aan de som tot daaraan toe, zoek dan links anders rechts. etc. Totdat je nog maar 1 foto over houd).
- je hoeft dan maar 1x de rij langs om per foto de cumulatieve som te bepalen en daarna kan je vele malen sneller door de rij heen (uitgaande van veel foto's).
- echter, je wilt niet 1 random foto, je wilt er meer. Je kan dit proces herhalen, maar dan doet bij die "trekking" de eerder gekozen foto's ook weer mee. De kans hierop is niet zo groot (afhankelijk van het aantal foto's). Wat je dan zou kunnen doen is als er een foto uit je trekking komt die al geplaatst is, pak dan de volgende foto (of de eerste foto als je bij de laatste foto uit de rij getrokken hebt), totdat je een foto tegenkomt die je nog niet eerder getrokken hebt. (Let er dan wel op dat het aantal foto's groter of gelijk het aantal foto's is dat je wilt plaatsen!).

[Verwijderd]

Op zondag 20 januari 2002 19:02 schreef runningman het volgende:
Ik zit met een klein probleempje. Ik heb een tabel vol met foto's. Deze wil ik random op een pagina zetten. Maar mensen kunnen ook stemmen op een foto.
De foto met de meeste stemmen moet ook de meeste kans hebben om te worden geplaatst.

Ik had het ongeveer zo gedacht:
als de foto tussen de 75% en 100% van de stemmen zit draait de foto 4x mee in een selectieronde. Tussen de 50% en 75% 3x, 25% en 50% 2x en 0% en 25% 1x.

Ik vroeg me af hoe dit algoritme eruit moet zien. Ik zit me al helemaal suf te piekeren.

Iemand ?

lijkt me slechte keuze: als je de foto's met meer stemmen meer laat zien, gaan die meer en meer stemmen krijgen, er van uitgaande dat niet iedereen alle foto's zal bekijken en stemmen. (ik denk aan iets van HotOrNot).

[Verwijderd]

Op zondag 20 januari 2002 19:39 schreef Jppr het volgende:

[..]

lijkt me slechte keuze: als je de foto's met meer stemmen meer laat zien, gaan die meer en meer stemmen krijgen, er van uitgaande dat niet iedereen alle foto's zal bekijken en stemmen. (ik denk aan iets van HotOrNot).

Het is niet zozeer dat de foto's met de meeste stemmen alleen maar te zien zijn, maar die foto's hebben meer kans om gepubliceerd te worden.

[Verwijderd]

Heel simpel algoritme:

Sorteer de foto's op aantal stemmen.
Geef ze allemaal een rangnummer (index).

While {x/som(x) > r} Do

{x <- Trek een getal tussen 0 en het aantal foto's plus 1.
r<- Trek een random getal tussen o en 1.}

x is het nummer van je foto.


Je ziet dat bij deze procedure niet 4 categorieen zijn die je met verschillende kansen toont, maar elk aantal stemmen krijgt zijn eigen kans (die in dit geval linear oploopt met je rangnummer).

Als je het algoritme meer afgestemd wil hebben, hoor ik het wel: je kunt de 'verwerp kans' functie niet alleen functie laten zijn van het rangnummer, maar ook rechtstreeks van het aantal stemmen, of logaritmisch van het rangnummer.

Je kunt er ook een blokfunctie van maken, zoals jouw eerste idee was, maar dat ziet er minder elegant uit.

[Verwijderd]

Op zondag 20 januari 2002 19:43 schreef runningman het volgende:

[..]

Het is niet zozeer dat de foto's met de meeste stemmen alleen maar te zien zijn, maar die foto's hebben meer kans om gepubliceerd te worden.

wat bedoel je met gepubliceerd? kan je misschien wat meer uitleg geven over de site?