Newsgroup: it.comp.www.php
Titolo: estrazione pesata

Salve a tutti!
Ho un array dal quale devo estrarre n elementi a caso, e fin qui
niente di complicato.
Il problema e' che io vorrei che gli elementi dell'array con un valore
piu' alto abbiano piu' possibilità di essere estratti, mettere una
sorta di peso all'estrazione...
E' possibile? come posso fare?
Grazie mille!!
V


wrote:


E' possibile, un sistema relativamente semplice e' quello di usare un
vettore "pesato"... pero' funziona *solo* se il numero degli elementi
dell'array e' molto superiore a quello degli elementi estratti.
Mi spiego: se hai un array (Alfa, Beta, Gamma) e chiedi di estrarre i
primi tre elementi, te li ritorna sempre tutti e tre.
Quindi la loro frequenza e' di 33%, 33%, 33% - *anche* se hai chiesto
una frequenza differente.
Idem se ne chiedi due (vederlo e' un po' meno intuitivo :-)).
Se ti pòle anda' bene...
Leonardo
-- 
 What do you make, so fair and bright;
 What do you build with sails for flight;
 What do you weave with wool so white?

 wrote:

Caro ViandanteOscuro,
potresti fare cosi'. Crei una funzione di distribuzione f(x) sull'intervallo
[0,1] normalizzata a 1 (cioe' l'integrale f(x)dx su [0,1] da' 1). Poi generi
dei punti casuali nel piano [0,1]x[0,max(f(x)] e prendi solo i punti (x,y)
tali che f(x)<=y. Poi dall'array selezioni l'elemento di posizione x*count(a).
Esempi di funzioni normalizzate:
f(x)=2.0*x
f(x)=0.333*x*x
...
Implementazione con quest'ultima funzione:
define("RND_K", 1.0 / (1.0 + getrandmax()));
/**
 * Return random number in [0.0,1.0[
 * @return float
 */
function rnd()
{
    return RND_K * rand();
}
$a = array("a", "b", "c");
do {
    $x = rnd();
    $y = 0.333 * rnd();
} while( $y > 0.333 * $x * $x );
print $a[ (int)($x * count($a)) ];
Ciao,
 ___ 
/_|_\  Umberto Salsi
\/_\/  
www.icosaedro.it


ehm... non proprio, a me non serve pesare tutta l'estrazione, a me
serve che alcuni elementi dell'array abbiano probabilità maggiore di
essere estratti, in base a criteri scelti da me.
Ad esempio se ho un array cosi' composto:
ar1 (4, 6, 10, 8, 9) voglio che invece di avere probabilità 0.2 ogni
elemento, quelli sopra l'8 abbiano probabilità chesso'... .3 e il
resto diviso equamente tra gli altri elementi.

 f(x)=0.333*x*x
Errore di stampa: "0.333" leggasi invece "3" altrimenti non e' normalizzata.
Adesso che mi viene in mente, se non c'e' necessita' di seguire una
distribuzione specifica basta fare semplicemente il quadrato o il cubo di un
numero casuale tra 0 e 1, cosi' distribuisci i valori ottenuti di piu' verso
1 e meno verso 0. Piu' alta la potenza, piu' squilibrata e' la distribuzione:
$x = rnd();
print $a[ (int)($x*$x*$x * count($a)) ]


 resto diviso equamente tra gli altri elementi.
Il principio non cambia, solo che la distribuzione continua f() diventa
discreta $f[]:
$a = array("a", "b", "c");
$f = array(0.2, 0.3, 0.5); // ovviamente somma $f[] = 1.0
$n = count($a);
do {
    $x = (int) ($n * rnd());
    $y = rnd();
} while( $y > $f[$x] );
echo $a[$x];


resto diviso equamente tra gli altri elementi.
Con i caveat del post precedente:
	/*
		In ingresso: un array con pesi relativi e il numero di
		elementi desiderati.
		In uscita: un array con, se possibile, le chiavi dell'
		array $scelte.
		Es: array('a' => 4, 'b' => 1), 1
		dovrebbe ritornare o a o b, e a 4 volte piu' spesso di
		b.
	*/
        function estrai_con_frequenza($scelte, $desiderati)
        {
                $estratti       = array();
                // Per ogni estrazione
                while(!empty($scelte) && ((count($estratti)<$desiderati)))
                {
                        // Un punto a caso equiprobabile su un'area
                        // variabile
                        $punto  = rand(0, array_sum($scelte)-1);
                        // Determino a chi appartiene questo punto
                        $index  = 0;
                        $values = array_values($scelte);
                        while($punto >= $values[$index])
                                $punto -= $values[$index++];
                        unset($values);
                        $keys   = array_keys($scelte);
                        $key    = $keys[$index];
                        // Aggiungo all'estrazione
                        $estratti[] = $key;
                        // Elimino dalle scelte
                        unset($scelte[$key]);
                }
                return $estratti;
        }
Il risultato lo vedi da te:
<?php
        $scelte = array(
                'mela'  => 15,
                'pera'  => 33,
                'gatti' => 5,
                'cani'  => 11,
                'cippa' => 7,
                'lippa' => 40,
                'dingo' => 2,
        );
        $volte  = 10000;
        $previste = array();
        $base   = 0;
        $totali = count($scelte);
        foreach($scelte as $cosa => $quanto)
                $base += $quanto;
        foreach($scelte as $cosa => $quanto)
                $previste[$cosa] = number_format($quanto*100/$base, 2);
        print '<table border="1" cellspacing="0" style="font-family:
Courier">';
        for ($prove = 1; $prove <= count($scelte); $prove++)
        {
                $elementi = 0;
                $ottenute = array_combine(array_keys($scelte),
                                array_fill(0, count($scelte), 0));
                for ($i = 0; $i < $volte; $i++)
                {
                        $got = estrai_con_frequenza($scelte, $prove);
                        foreach($got as $it)
                                $ottenute[$it]++;
                        $elementi += count($got);
                }
                $previsti = $prove * $volte;
                print '<tr bgcolor="blue"><td colspan=5 style="color:
white">';
                print "$volte estrazioni di $prove/$totali elementi
($elementi/$previsti valori)";
                print "</td></tr>";
                print "<tr><th>Cosa</th><th>Frequenza</th><th>Attese
%</th><th>Attesi</th><th>Ottenuti</th></tr>";
                $norma  = 0;
                $errore = 0;
                foreach($scelte as $cosa => $quanto)
                {
                        $attass  = (int)($previste[$cosa] * $elementi /
100 + 0.5);
                        print "<tr style=\"text-align: right\"><td
bgcolor=\"lightgray\" style=\"text-align:
left\">$cosa</td><td>$quanto</td>";
                        print
"<td>$previste[$cosa]</td><td>$attass</td><td>$ottenute[$cosa]</td></tr>";
                        $errore += ($attass - $ottenute[$cosa]) * ($attass
- $ottenute[$cosa]);
                        $norma  += $attass*$attass;
                }
                $errore = number_format((100*$errore)/$norma, 2);
                print "</tr>";
                print "<tr><td>&nbsp;</td><td colspan=3>Scarto rispetto al
comportamento desiderato</td>";
                print "<td style=\"text-align:
right\">$errore%</td></tr>";
        }
        print "</table>";
?>
~
~


> essere estratti, in base a criteri scelti da me.
[..]
cerchiamo di non esagerare con troppa teoria ed implementazioni troppo
complesse..
non testato.. (il funzionamento si puo' intuire)
function lottery ($values, $frequencies)
{
 $maxFrequency = array_sum($frequencies);
 $randValue = rand(1, $maxFrequency);
 for ($i = $limit = 0; $i < count($frequencies); $i++) {
  $limit += $frequencies[$i];
  if ($randValue <= $limit) {
   return $values[$i];
  }
 }
}
probabilita' eque per tutti gli elementi..
$v = array(1, 2, 3);
$f = array(1, 1, 1);
echo lottery($v, $f)
probabilita' 25% 25% 50%..
$v = array(1, 2, 3);
$f = array(1, 1, 2);
echo lottery($v, $f)
che per convenienza puo' anche essere scritto..
$v = array(1, 2, 3);
$f = array(25, 25, 50);
echo lottery($v, $f)
mi sembra pratico veloce e semplice..
-- 
www.iuz-lab.info
 - 
www.php-faq.org

> mi sembra pratico veloce e semplice..
e anche funzionale:
$i = 5000;
$val = array();
while ( $i-- )
{
	$val[lottery($v, $f)]++;
}
print_r( $val );
direi che funziona bene (il piccolo margine d'errore è dato dalla funzione
rand che non è perfettamente equidistribuita - mt_rand non mi sembra che
migliori molto questo aspetto...)

}
Pero' cosi' estrai un solo elemento; il problema era "estrarne n".
Per estrarne due, devi chiamare due volte la funzione... che potrebbe
anche ritornarti l'elemento gia' estratto. Sicche', a quel punto devi
eliminare gli elementi estratti dal pool dell'estrazione successiva e
vedi spuntare fuori i noti problemi di distribuzione...
Leonardo "Prima legge di Ginsberg: Non puoi vincere"


 
non posso vincere, non posso pareggiare e non posso neppure abbandonare.. ma
posso sempre scommettere sull'avversario :-)
-- 
www.iuz-lab.info
 - 
www.php-faq.org