Newsgroup: it.comp.lang.c
Titolo: calcolo combinatorio

Salve.
C'e` qualcuno che sa se esiste in rete del codice sorgente C/C++ (free) o
comunque qualche libreria (sempre free) che implementi algoritmi di generazione
di combinazioni semplici o con ripetizione, permutazioni, disposizioni, ecc.
Grazie,
Marco Guidi

gu...@sssup1.sssup.it
 ha scritto nel messaggio ...

Perché non farle da solo? Magari evita di implementare l'operatore
fattoriale e alleggerisci le funzioni seguendo la strada più breve ponendo
ad esempio n!/k! come
risultato = 1;
for{ i=n; i>k; i--} risultato *= i;
--
Francesco Trotta
http://space.tin.it/computer/ftrotta
Elimina "x_" dal mio indirizzo per mandarmi
un messaggio direttamente

 for{ i=n; i>k; i--} risultato *= i;
La via migliore, per i coefficienti binomiali, e' di pensare se c'e'
una qualche relazione tra ognuno di essi ed il precedente ...
-- 
Maurizio Loreti                      
http://wwwcdf.pd.infn.it/~loreti/mlo.html
Un. of Padova, Dept. of Physics - Padova, Italy          
lor...@padova.infn.it

 writes:
Mi spieghero` meglio:
punto 1: tipiche domande da compito d'esame.
  Quello che devo fare non serve per un compito, visto che non sono piu'
  studente (mi avevano proposto il dottorato ma sono fuori dai limiti di eta`,
  visto che tra poco piu' di un mese compiro` 32 anni e qui al S.Anna e`
  richiesto di avere meno di 30 anni per partecipare a concorsi per il
  dottorato). Qui al S. Anna sono semplicemnte un contrattista che si occupa
  attualmente di ultimare un progetto sui sistemi real-time, tra l'altro senza
  avere nemmeno accesso ai libri della biblioteca, essendo esterno alla scuol.
  In ogni caso la domanda che avevo postato sul newsgroup non ha niente a che
  fare con il mio contratto o con attivita` di ricerca varie,
  ma piuttosto nasce dal fatto che alcuni miei amici mi hanno
  chiesto a piu` riprese piccoli (o anche non piccoli, visto che non avendo
  loro molto a che fare con i computer a volte non si rendono bene conto dello
  sforzo necessario per realizzare certe applicazioni) programmi per sviluppae
  sistemi per il gioco del lotto, corsa tris, ecc. (attivita` per le quali non
  prendo una lira). Uso questo account per accedere al newsgroup perche`
  e` l'unico modo che ho attualmente per l'accesso ad internet.
punto 2: perche' non svilupparle da solo.
  Intanto perche' se non avessi gia` provato a svilupparle da solo non avrei
  postato il messaggio sul newsgroup. Piu` avanti dettagliero` meglio quello
  che ho provato a fare da solo.
  Quello che mi interessa non e` tanto calcolare il numero di combinazioni,
  permutazioni, ecc. ma piuttosto di generarle. Cioe` io sono perfettamente
  a conoscenza, ad esempio, del fatto che il numero di combinazioni semplici
  di n oggetti k a k e` pari a n su k ed ho gia' sviluppato delle funzioni che
  mi consentono di "contare" le varie combinazioni, disposizioni, ecc.
  Il fatto e` che contarle non equivale a generarle. Ad esmpio dire che
  in un insieme di 5 numeri ci sono 10 ambi e` abbastanza semplice
  (5 su 2 = 5!/(2!*(5-2)!) = 120/(2*6) = 10).
  A questo punto pero` dovrei dire quali sono le combinazioni (ad esempio
  se i 5 numeri sono 1,2,3,4,5 i possibili ambi sono:
  1 2
  1 3
  1 4
  1 5
  2 3
  2 4
  2 5
  3 4
  3 5
  4 5
 Un possibile modo che ho trovato per generare  gli ambi e i terni
 in n numeri e` il seguente:
int ambi(int n) {
  int i,j;
  int *array;
  if(n < 2)  return -1;
  if((array=malloc(n*sizeof(int))) == NULL) return -1;
  /***************************************************************************
     riempio l'array nel modo piu` banale, ma nulla mi vieterebbe di riempirlo
     con elementi diversi
   **************************************************************************/
  for(i = 0; i < n; i++) array[i] = i+1;
  for(i = 0; i < n-1; i++)
    for(j = i+1; j < n; j++) {
        printf("%d %d\n",array[i],array[j]);
    }
   return 0;
}
int terni(int n) {
  int i,j,h;
  int *array;
  if(n < 3)  return -1;
  if((array=malloc(n*sizeof(int))) == NULL)  return -1;
  /***************************************************************************
     riempio l'array nel modo piu` banale, ma nulla mi vieterebbe di riempirlo
     con elementi diversi
   *********************************************************************/
  for(i = 0; i < n; i++) array[i] = i+1;
  for(i = 0; i < n-2; i++)
    for(j = i+1; j < n-1; j++)
      for(h = j+1; h < n; h++) {
        printf("%d %d %d\n",array[i],array[j],array[h]);
      }
  return 0;
}
Ovviamente questa non e` una tecnica molto soddisfacente in quanto dovrei
scrivere una funzione per ognuna delle possibili kple in n numeri. Poiche`
k puo` assumere valori tra 1 ed n, dovrei avere circa n funzioni (magari
qualcuna stupida la potrei evitare, tipo quelle per k = 1 o k = n). Pero`
visto che n puo` variare, dovrei scrivere un numero variabile di funzioni
al variare di n.
Quello che mi servirebbe (e che da solo non riesco ad implementare) e` un modo
per passare da funzioni che contengano al proprio interno k cicli for annidati
a funzioni che contengano un solo ciclo for del tipo (indico con CSnk il numeo
di combinazioni semplici di n elementi k a k):
for(z = 0; z < CSnk ; z++) {
    printf(<la z-esima kpla>);
}
Il problema e` che da solo ho gia` provato e non sono approdato a molto
(ora non ho con me i miei appunti, per cui non riesco a spiegare in dettaglio
quello che ho gia` provato, comunque ho adottato una specie di "metodo
galileiano". Cioe` ho generato con il metodo dei for annidati tutte
le possibili quaterne in 10 numeri e, osservando i risultat, ho cercato
di stabilire delle relazioni
tra i vari elementi da utilizzarle in un ciclo for unico. Il problema e` che
anche in quel caso ottenevo l'annidamento di alcune istruzioni, tipo k if
annidati, che mi spostavano il problema dalla eliminazione dell'annidamento
di k for alla eliminazione dell'annidamento di k if).
Spero di aver chiarito meglio il problema. Non lo avevo fatto in precedenza
perche` l'argomento mi sembrava piuttosto tedioso e non volevo
annoiare gli utenti del newsgroup, visto che mi sembrava che la cosa piu`
semplice fosse ricorrere a librerie gia` implementate ma visto che
mi e` stato proposto di svilupparle da solo, ne approfitto per chiedere
se qualcuno ha qualche idea in proposito.
Comunque credo che se a Padova danno queste robe nei compiti, non mi sarei
laureato se mi fossi iscritto in quell'ateneo.
Marco Guidi.


 laureato se mi fossi iscritto in quell'ateneo.
Perche'?  Combinazioni, permutazioni e via dicendo sono un ottimo
esempio di procedure ricursive; dopo si mostra anche la maniera non
ricursiva, si esemplifica il loop unrolling; e sono un ottimo banco di
prova per controllare il grado di apprendimento.
Seconda domanda: perche' vuoi sistemi per il gioco del lotto?  Tutti i
numei sono ugualmente probabili e metodi matematici non ne esistono.
I ritardi sono una sciocchezza.  Premetto subito che mi occupo
professionalmente di fisica e di statistica; e che ho gia' affrontato
una volta questa discussione, solo per vedere (dopo che il thread si
era concluso) ripostare la stessa domanda dopo una settimana!  A quel
punto ho deciso che, se qualcuno e' cosi' tonto da voler inventare il
modo sicuro di vincere, non cerchero' mai piu' di fargli cambiare
idea.


 idea.
  Sono perfettamente daccordo con te sul fatto che se uno ha dei soldi
  da investire nel gioco, il moglior investimento che ne puo` fare
  e` quello di non giocarli ma metterli da parte. Il problema e` che,
  a quanto pare, il potere della pubblicita` e` molto piu` forte di qualsiasi
  argomentazione matematica. Ad esempio se alcuni giornali specializzati in
  queste robe riportano in proma pagina: "questa settimana abbiamo realizzato
  10 terno con i nostri sistemi e 2 quaterne", la gente ritiene che quello
  sia un modo per guadagnare non pensando che per realizzare 10 terni e` stato
  proposto il gioco di  80.000 terni e poiche` un terno paga poco piu` di 4000
  volte la posta...
  Non riesco a spiegarlo ad alcuni miei amici!!
  A forza di pensare a questa roba comunque mi sono venuti due "dubbi" che
  forse tu potresti chiarirmi:
  1- Se uno ha soldi "infiniti" potrebbe pensare che giocando un estratto con
     aumento della puntata prima o poi guadagnera` qualcosa in quanto, se
     p = probabilita` che l'estratto esca = 1/18
     probabilita di uscita dell'estratto alla prima estrazione = p
     probabilita di non uscita dell'estratto alla prima estrazione = 1-p;
     probabilita di uscita dell'estratto alla seconda estrazione = (1-p)p;
     probabilita di uscita dell'estratto alla terza estrazione = (1-p)^2 * p;
     probabilita' di uscita in almeno una estrazione
     = somme(per k da 0 a infinito) (1-p)^k*p = p/(1-(1-p))=1
     Quindi se uno ritiene che i suoi soldi approssimino bene l'infinito
     potrebbe pensare di vincere
L'obiezione al punto 1- e` ovvia: l'infinito non e` mai approssimato bene
 2- come e` dimostrabile che i numeri sono equiprobabili ?
    Voglio dire: supponiamo che la massa di probabilita` dei vari numeri
    sia incognita. Un metodo per stimarla potrebbe essere quello di
    guardare le statistiche dei numeri usciti in passato e cercare
    di fare una stima della massa di probabilita` a partire dalla
    statistica.  Ovviamente nessuno garantisce che cio` che e` valso
    in passato varra` anche in futuro, ma questa e` una tecnica che
    ingegneristicamente si applica in alcuni casi (as esempio
    per calcolare il working-set in un sistema paginato, per
    limitare il numero di page-fault, si
    usano spesso le pagine riferite piu` recentemente nel passato,
    anche se in realta` il working-set dovrebbe essere costituito dalle pagine
    a cui si deve accedere nel futuro).
   Fare l'assunzione che i numeri siano equiprobabili e` dimostrabile ?
Marco Guidi.


      potrebbe pensare di vincere
Il ragionamento e' corretto; ma se si hanno soldi infiniti, perche'
giocare?


   permutazioni, ecc. ma piuttosto di generarle.
Credo che dovresti concentrarti su un metodo ricorsivo.
EMG

 professionalmente di fisica e di statistica;
Ah, ecco spiegato come mai tu sia fra quei pochi... :-)
EMG

  2- come e` dimostrabile che i numeri sono equiprobabili ?
Certo, questa è una domanda migliore. Se il sistema di estrazione fosse
difettoso allora si potrebbero studiare statisticamente questi difetti
ed approfittare del fatto. Ma francamente non credo sia così.
EMG

gu...@sssup1.sssup.it
 ha scritto nel messaggio ...
[.....]
Ciao,
tempo fa avevo postato del codice che fa proprio quello che cerchi.
Usa la ricorsione e, se non e' conveniente dal punto di vista della
velocita', permette pero' quell'elasticita' di avere il K variabile.
Il vettore IX[] contiene la combinazione corrente.
Occorre derivare dalla classe e ridefinire il metodo show_comb().
Il metodo prepara(), probabilmente, non sara' mai ridefinito e converrebbe
renderlo inline.
Ciao
Nazzareno
// ---------------------------------------------------------------------
// classe per simulazione di cicli nidificati in numero variabile
class Ciclo
{
  public:
  Ciclo();
  virtual ~Ciclo();
  virtual bool init(int c, int d);
  virtual bool run();
  protected:
  virtual void show_comb() = 0;
  virtual bool get_break() { return false; } // nessuna interruzione di
default
//  virtual
  void prepara(int i,int level);
  void calcola(int i,int level);
  bool ciclo(int n,int level);
  int Cicli;  // k di n_su_k
  int Dim;    // n di n_su_k
  int *IX;
};
-------------------------------------------------------------------
// implementazione
Ciclo::Ciclo() : Cicli(0), Dim(0), Progr(0), IX(0)
{  }
Ciclo::~Ciclo(void)
{
    delete []IX;
}
bool Ciclo::init(int c, int d)
{ 
    Cicli = c; 
    Dim = d;
    delete []IX;
    return  (IX=new int[Cicli]) != NULL;
}
bool Ciclo::run() 
{ 
    return ciclo(0,0); 
}
void Ciclo::prepara(int i,int level) 
{  
    IX[level] = i; 
}
void Ciclo::calcola(int i, int level)
{  
    prepara(i,level);
    show_comb();
}
bool Ciclo::ciclo(int n,int level)
{
  if(level >= Cicli)     // superato il numero di cicli di iterazione
      return true;
  if(level == Cicli-1) {  // ultimo ciclo
      for(int i=n;i<Dim;++i)
          calcola(i,level); 
       return(true);
      }
  if(get_break())
      return false;
  for(int i=n;i<Dim;++i) {    // si richiama per l'iterazione successiva
      prepara(i,level);
 
   if(!ciclo(i+1,level+1))
          return false;
      }
  return true;
}

di combinazioni semplici o con ripetizione, permutazioni, disposizioni,
ecc.
Questo puo' andar bene per generare le combinazioni di ambi, terni, etc..,
del lotto.
Su linea di comando devi inserire cosa generare 2=ambi, 3=terni, 4, 5.
Se cambi total puoi lavorare anche meno di 90 numeri.
<<<<<<<<<<<---------------------------->>>>>>>>>>>>>>
#include "stdio.h"
#include "stdlib.h"
int * comb,n,total=90;
void gencomb ( int level,int start )
{
  int  i;
  if( level>=0 ) for( i=start ; i<=total-level ; i++ )
    comb[level]=i,gencomb( level-1,i+1 );
  else
  {
    printf( "\n" );
    for( i=0 ; i<n ; i++ )  printf( " %2d",comb[i] );
  }
}
int  main ( int argc,char * argv[] )
{
  n=atoi( argv[1] );
  if( argc<2 || !n || n>5 )  return 2;
  comb=malloc( sizeof( *comb )*n );
  if( !comb )  return 1;
  gencomb( n-1,1 );
free( comb );
  return 0;
}
<<<<<<<<<<<---------------------------->>>>>>>>>>>>>>
ciao
donCiccio

>  2- come e` dimostrabile che i numeri sono equiprobabili ?
Bella domanda.
Andrea Laforgia
----
I guai ve li andate a cercare : 
quando Bill Gates annuncio' che avrebbe fatto scrivere 
Windows98 a Topo Gigio perche' non gli avete creduto ?

 (Attenzione : non ho detto che "possano uscire", ma che "escano effettivamente")
Qui la situazione è diversa. E' come nella tombola. Man mano che peschi
una nera quelle bianche rimaste hanno maggiore probabilità di essere
pescate per il semplice fatto che ce ne sono di più. Penso che a questo
punto solo l'amico Maurizio può chiarirci le idee.
EMG


All'università di Bologna, facoltà di Informatica, I° anno, i compiti di
programmazione e laboratorio sono mooooooooolto più semplici eppure i
promossi al primo appello sono circa un 20%, via via calando con l'avanzare
degli appelli. Oserei dire che qualcuno deve avere sbagliato qualcosa.
Oppure siamo tutti dei grandi ignoranti (io si, ma non lo ammetto spesso...)


Prima di tutto ringrazio tutti quelli che hanno risposto, sia che abbiano
opinioni concordi alle mie o meno (anche se non ritengo che sia questione di
opinioni).
Non vorrei sembrare presuntuoso, ma ritengo di avere la certezza deterministica
del fatto che il mio ragionamento iniziale sia corretto e, sinceramente, in
tutte queste valutazioni mi sembra che l'osservazione piu` corretta sia quella
di Maurizio Loreti : "Se uno ha soldi infiniti, perche` gioca ?".
Cerchero` di spiegarmi meglio:
Il fatto che la probabilita` di vincita sia del 100% avendo soldi infiniti e`
inconfutabile, in quanto non scaturisce da una mia opininone personale, ma da
un ben preciso calcolo matematico derivante dalla teoria della probabilita`
accettata comunemente in cui si definisce un esperimento casuale (l'estrazione
di un estratto su ruota singola in una estrazione del lotto) per mezzo di uno
spazio campione (un insieme di risultati possibili dell'esperimento) e una
funzione "massa di probabilita`" che associa a ciascun elemento dello
spazio campione una probabilita`. Se scegliamo la funzione di probabilita`
in modo che p(X) = 5/90 = 1/18 dovrebbero essere rispettati tutti gli assiomi
che sono richiesti ad una funzione massa di probabilita` per esssere
considerata tale (cioe` che 0 <= p <= 1,
p(e` estratto almeno uno degli elementi dello spazio campione) =1
ed altre che ora non mi ricordo. Magari Maurizio Loreti potrebbe essere piu`
preciso in proposito. Comunque a Pisa viene utilizzato un testo scritto
da un docente della facolta` : Verrazzani-Ciampi: Teoria dei segnali volume 2:
"Variabili aleatorie e processi stocastici" che introduce abbastanza bene
 questi concetti).
Ora quando si dice che il Lotto e` "senza memoria", bisognerebbe specificare
in termini di probabilita` cosa significa che e` "senza memoria".
Se si intende che ad ogni estrazione la probabilita` di un singlo numero
di essere estratto e` sempre pari a 1/18, indipendentemente dal ritardo
siamo perfettamente d'accordo. Se invece si intende dire che la probabilita`
che un numero non venga estratto per 2.000.000.000 di volte consecutive e`
uguale alla probabilita` che esso non venga estratto in una singola estrazione
allora non siamo assolutamente d'accordo.
Il ragionamento secondo cui
probabilita` di estrazione di un numero alla prima estrazione = p
probabilita` di non estrazione di quel numero alla prima estrazione = 1-p
probabilita` di estrazione di un numero alla seconda estrazione =
 probabilita` che il numero non sia stato estratto alla prima *
 probabilita` che il numero sia estratto alla seconda = (1-p)*p
...
probabilita` di estrazione di un numero alla k-esima volta = (1-p)^(k-1)*p
e quindi
probabilita` che un numero prima o poi esca =
   p*somme(per k da 1 a infinito)(1-p)^(k-1) = p/(1-(1-p)) = 1
e` SICURAMENTE corretto (ammesso che le varie estrazioni si ritengano
esperimenti casuali indipendenti. E anche il fatto  che siano indipendenti
non so quanto e` dimostrabile) secondo la teoria della probabilita`
generalmente accettata.
In ogni caso se fate i calcoli vedrete che e` molto improbabile che un numero
esca in n estrazioni, anche con n piuttosto elevato, in modo che se
anche vincete ogni tanto, quello che avete speso e` sicuramente
maggiore di quello che guadagnate con una vincita (non conosco
testi specifici, ma ne esistono su un argomento chiamato "teoria dei giochi",
che volendo puo` essere applicato anche al lotto, ma puo` anche non averci
niente a che fare. Per quanto ne so la "teoria dei giochi" era nata in ambienti
militari per valutare la convenienza o meno a prendere certe decisioni
strategiche)
Dire che il lotto NON HA MEMORIA non contrasta con quanto sopra in quanto
il lotto avrebbe memoria se fosse:
  p(X) = funzione di cio` che si e` verificato nelle estrazioni precedenti.
Cioe` se io dicessi ad esempio che la probabilita` di etrarre un numero in
questa estrazione = ritardo_attuale del numero ^0.00000000001
significherebbe che la probabilita` di estrarre un numero in QUESTA estrazione
dipende dal ritardo di quel numero ed in questo modo considererei il lotto "con
memoria".
Ma nel mio modello p(X) = 1/18
indipendentemente dal ritardo di X (e quindi nel mio modello considero il lotto
senza memoria). La valutazione poi della probabilita` di n insuccessi
consecutivi non ha molto a che fare con l'avere memoria o meno.
Qualcuno obiettera` che se io dico:
  probabilita` alla k-esima estrazione = (1-p)^(k-1)*p
tengo conto del passato. Il fatto e` che la k-esima estrazione si verifichera`
in futuro e quando arriveremo ad essa il numero X avra` probabilita` p=1/18 di
essere estratto, senza che questo contrasti con l'analisi precedente (pensare
bene a cosa e` p=1/18).
C'e` anche da dire che, anche se l'evento "prima o poi il numero X esce" ha
probabilita` pari a 1 (100%), non e` comunque detto che l'evento si
verifichi!!! Infatti un evento a probabilita` 0 non e` necessariamente
impossibile.
Tra l'altro questa tecnica e` quella da cui si parte per calcolare ad esempio
il numero medio di "pacchetti" in coda nel buffer di un nodo di una rete per
dati, o il suo tempo medio di permanenza in coda o altri tipi di statistiche
(se qualcuno non ci crede  puo` provare a seguire il
corso di reti di calcolatori al 5. anno di ingegneria informatica a Pisa.
Questo e` praticamente un altro esame sulla teoria delle probabilita`, dove
nei compiti ci sono molti di questi calcoli da fare, ma non c'e`
da scrivere codice anche se in realta` durante l'anno viene richiesta
l'implementazione di alcuni protocolli di rete in C).
Naturalmente un trasmettitore non trasmette all'infinito perche`
dopo 10-20 ritrasmissioni di un pacchetto si assume che sia piu` probabile che
un fulmine abbia tranciato la linea (e quindi
p(trasmissione corretta) condizionata dall'evento "un fulmine ha tranciato la
linea" = 0) che non che il pacchetto sia andato perso per 10-20 volte nei
meandri di internet (anche se questo non e` impossibile)).
Forse a qualcuno potra` sembrare strano ma le reti per dati funzionano cosi`.
Ed ecco quindi perche` e` abbastanza assurdo utilizzare internet per
realizzare sistemi real-time (in quanto non e` possibile avere stime precise
del worst-case non sapendo quante ritrasmissioni vengono fatte. Infatti
le ritrasmissioni sono in genere trasparenti al programmatore e sono
eseguite dal protocollo, ad esempio dal TCP) anche se io ci devo provare per
contratto!!
Comunque: non giocate al lotto se volete evitare di perdere soldi.
Marco Guidi.

Qui la situazione è diversa. E' come nella tombola. Man mano che peschi
No no scusami ho sbagliato l'esempio.
Intendevo che la palla una volta pescata io la rimetto dentro.
Quindi la domanda si trasforma in "capitera' un' estrazione infinita di palle
nere ?"
Io credo che la risposta piu' plausibile sia : *probabilmente* no.
Voi che ne dite ?
Andrea Laforgia
---------------

Oppure siamo tutti dei grandi ignoranti (io si, ma non lo ammetto spesso...)
Quando io ad ingegneria elettronica diedi l'esame di fondamenti di informatica
lo passammo in 14 su 250.
Opterei per quel qualcuno che deve aver sbagliato qualcosa ! ;)
Andrea Laforgia
---------------

 Comunque: non giocate al lotto se volete evitare di perdere soldi.
Questo è sicuro. :-)
EMG

 


 Io credo che la risposta piu' plausibile sia : *probabilmente* no.
Ma forse la struttura che si forma mettendo insieme tutte le estrazioni
è artificiosa, magari è solo un modo sbagliato di osservare il caos.
EMG

A riguardo dei giochi tipo Lotto, Enalotto e via dicendo.
1)Sicuramente gli scommettitori presi nel loro insieme perdono sempre nei
confronti dell'ente che organizza il gioco. Se quest'ultimo infatti non
vincesse sempre non sarebbe (il gioco) una fonte di introiti. Naturalmente
tra gli scommettitori ci sarà chi vince e chi perde.
La scommessa infatti non è "corretta": se le possibile sestine del
Superenalotto sono 600 milioni e rotti allora io scommettendo 1 Lira su una
sestina dovrei avere, in caso di vincita, 600 milioni e rotti.
2)Faccio un esempio quando si parla di probabilità che funziona (quasi)
sempre. Consideriamo una monetina: sia X croce e + testa.
Lanciando tre volte la monetina, le configurazioni possibili alla fine dei 3
lanci sono 8
1) XXX
2) XX+
3) X+X
4) X++
5) +XX
6) +X+
7) ++X
8) +++
    2.A) Se voglio che tutti e tre i lanci siano croce, a me interessa il
verificarsi della configurazione 1. 1 caso favorevole / 8 casi possibili:
1/8 è la mia probabilità. Da notare che se invece avessi voluto prima due
teste e poi una croce (configurazione 7) avrei avuto la stessa probabilità,
uguale ancora all'evento prima una testa, poi una croce e poi una testa
(conf. 6).
    2.B) Abbiamo visto che la probabilità della configurazione 1 (tre teste)
è 1/8. Se attendessi il verificarsi dell'evento "uscita di una sola croce
nei tre lanci" la probabilità aumenta: infatti le configurazioni che
soddisfano le richiesta sono la 2,3 e 5. La probabilità diventa 3/8. Se
invece attendessi l'evento "uscita di almeno una croce" avrei una
probabilità pari a 7/8 (sola la configurazione 8 non mi interessa).
    2.C) Consideriamo invece il caso dell'equiprobabilità della testa o
croce a qualsiasi lancio.
Poniamo di aver fatto già due lanci e di aver ottenuto la combinazione XX:
ci interessa avere ancora un'altra croce. Le due configurazioni possibili
per il prossimo lancio sono XX+ e XXX. Di nuovo 1 caso favorevole su 2
possibili. la probabilità è di 1/2.
Estendendo il ragionamento, se avessi fatto 99 lanci ottenendo sempre croce
le due configurazioni possibili per il prossimo lancio sono
XX ... X+ (99 croci e una testa)
XX ... XX (100 croci)
Quindi la probabilità continua ad essere ancora 1/2.
Considerare tutti lanci dalla prima volta in cui la monetina è stata
lanciata o considerarne ognuno singolarmente mi porta, utilizzando la
corretta interpretazione, alla medesima conclusione.
3) Se le combinazioni del Superenalotto non fossero tutte equiprobabili ad
ogni settimana, le modalità di scommessa dovrebbero variare ad ogni
settimana, poiché per chi gestisce il gioco non sarebbe conveniente pagare
nella stessa maniera una combinazione meno probabile e una più probabile.
Ora soffermiamoci un attimo a pensare se la pubblicità del Superenalotto
dicesse: "Gioca qualsiasi combinazione tanto sono tutte equiprobabili"...
Ecco perché continuano a guardare i ritardi e stupidaggini varie.


 assegnata probabilita` 0.
Va beh, ma questo è solo un caso di erronea stima delle percentuali. O
comunque di stima convenzionale. In questo caso dire 'probabilità 0%' è
solo un'approssimazione di un valore molto basso.
EMG
PS. Ho tolto il follow-up su it.comp.lang.c++. Almeno non occupiamo due
newsgroups con dei messaggi OT...

 A riguardo dei giochi tipo Lotto, Enalotto e via dicendo. [...]
Tutto quello che hai scritto mi trova perfettamente d'accordo. Non c'è
bisogno, come farneticavo io, di scomodare la meccanica quantistica.
EMG

 solo un'approssimazione di un valore molto basso.
Ti garantisco che con questa affermazione l'esame di Teoria dei Segnali
 qui a Pisa sarebbe difficile da superare.
 Se tu dai una probabilita` != 0, all'evento "la moneta resta in piedi" e`
 probabile che poi il "valor medio atteso" del "numero di croci" in 50000000
 lanci
 sia diverso dal 50%. Pero` se poi fai una statistica (cioe` fai effettivamente
 50.000.000 lanci) forse la previsione si avvicinerebbe di piu` alla realta`
 nel caso in cui l'evento "moneta in piedi" ha probabilita` 0 che non
 nel caso in cui ha probabilita` != 0. Anche se magari in 50.000.000 volte, una
 volta in piedi potrebbe restarci per davvero.
 Forse un esmpio meno banale e` il seguente. Supponi di avere un quadrato e di
 tracciare una diagonale. Supponi poi di avere a tua disposizione una matita
 acuminatissima (punta puntiforme). Supponi di lasciar cadere la matita in un
 punto qualsiasi del quadrato (magari aiutandoti con delle guide che
 impediscano alla matita di uscire fuori dal quadrato). La probabilita`
 di centrare la diagonale e` NULLA anche se centrarla e` POSSIBILE.
 Questo dipende dal fatto che la parte di piano coperta dalla retta
 ha area pari a 0, mentre il quadrato ha area maggiore di 0 per cui
 probabilita` di centrare la diagonale =
    area della diagonale / Area del quadrato = 0!!
 invece se dentro al quadrato disegno un triangolo con area > 0
 probabilita` di centrare il triangolo = area triangolo / area quadrato
 (compresa tra 0 e 1 se il triangolo e` tutto contenuto nel quadrato)
Marco Guidi


  terno).
Ciao a tutti.
Mi attacco al thread per discutere, dal punto di vista "algoritmico", un
altro problema legato al superenalotto e giochi simili.
La classica riduzione n-qualcosa funziona cosě: si gioca un sottoinsieme del
sistema integrale e, nel caso si fa 6, viene garantita matematicamente una
vincita di categoria inferiore. Ad es. giocando a n-2 devo fare 6 nel
sistema integrale per esser sicuro di avere almeno un 6-2 = 4 nelle mie
colonne giocate.
Fin qui non ci piove. Adesso vorrei fare una cosa diversa.
Supponiamo di avere N numeri in gioco. Per fare un esempio pratico
supponiamo N=25.
Ora: io voglio garantiti i 3 punti se faccio 3 punti nel sistema integrale
di 25 numeri, e naturalmente voglio giocare il minor numero di colonne
possibili.
Da questi 25 numeri mi genero tutte le combinazioni di 25 elementi presi a 6
a 6, con degli opportuni cicli for innestati.
Quindi C(25,6) =177.100 colonne (integrale).
Poi mi genero tutte le possibili terzine estraibili dai 25 numeri.
C(25,3) = 2.300 gruppi da 3.
Per avere garantiti i 3 punti facendone 3 sull'integrale, devo giocare tutte
le 2300 terzine. Ma al Superenalotto si giocano 6 numeri, quindi dovrei
raggruppare opportunamente queste terzine in gruppi da 6.
Una sestina puň rappresentare al massimo 20 terzine: C(6,3) = 20.
Quindi, io mi aspetterei di poter raggruppare le terzine, sostituendo ogni
gruppo da 20 con una sestina che lo rappresenta, ottenendo: 2300 / 20 = 115
colonne da giocare.
Ricapitolando:
Prendo 25 numeri, genero tutti i gruppi da 3 possibili, li raggruppo in
sestine (1 sestina = 20 terzine) e mi gioco 115 colonne per aver garantito
il 3 con 3 punti su 25.
La DOMANDA č questa: dall'integrale di 177.100 colonne, quali sono queste
115 ortogonali che mi rappresentano il "sistema minimo" per fare 3 con 3
punti?
Ho provato diversi metodi, con poco sucesso, ad es.: prendo e metto da parte
una sestina dalle 177.100 integrale, mi elimino le 20 terzine generabili da
questa colonna, poi prendo la successiva colonna che copre altre 20 terzine
tra quelle rimaste (che sono 2300 - 20 = 2280), e continuo cosě fino alla
copertura totale delle terzine in gioco... perň arrivo ad un punto in cui
rimangono terzine non raggruppabili in gruppi da 20, quindi non riesco ad
avere il sistema minimo di 115 colonne.
Idee?
--
Ciao, AntoGal
*************************************************
Home Page (area programmatori di VolFtp)
http://volftp.tin.it/italiani/galletta/
per scaricare un gioco di DAMA ITALIANA
*************************************************

  (compresa tra 0 e 1 se il triangolo e` tutto contenuto nel quadrato)
Probabilmente sono io che non ho abbastanza conoscenze al riguardo ma il
ragionamento non mi suona del tutto corretto. Qualcun'altro lo può
confermare o confutare?
EMG

 confermare o confutare?
è un classico problema di calcolo delle probabilità, e lo puoi trovare
(trattato magari con esempi diversi) su ogni buon testo al riguardo.
rientra nel vasto campo di eventi "logicamente possibili ma 
fisicamente impossibili".
giulio
-- 
Boycott Microsoft: 
http://www.boycott-ms.org/

 fisicamente impossibili".
Ma il punto è questo: ad un evento fisicamente impossibile io mi aspetto
che venga assegnata probabilità 0%.
EMG

 che venga assegnata probabilità 0%.
no.. quello e' un evento CERTAMENTE impossibile, non FISICAMENTE...
ciaoz
Ho sentito urla di sudore... che schifo...
--
Michel <ZioBudda> Morelli		  
mic...@michel.enter.it
 
http://ziobudda.enter.it
Problemi con Linux ?    mailto:
li...@saturn.media.dsi.unimi.it

 no.. quello e' un evento CERTAMENTE impossibile, non FISICAMENTE...
C'è qualche differenza?
EMG

On Fri, 26 Mar 1999, Enrico Maria Giordano wrote:

Secondo me un evento FISICAMENTE possibile non e' possibile al 100%
perche' c'e' sempre il NON_FISICAMENTE che interferisce.. Il CERTAMENTE
e' possibile al 100% e basta...
La morte e' FISICAMENTE possibile, non CERTAMENTE...


 che venga assegnata probabilità 0%.
ed infatti quella (0) è esattamente la probabilità che trovi applicando 
gli schemi probabilistici ad una qualsiasi infinità continua di casi 
possibili, come nella diagonale, o ad esempio nella posizione finale 
di un ago rotante intorno ad un centro.
da un punto di vista fisico, è impossibile che l'ago si fermi in una
posizione prestabilita, anzi non è nemmeno possibile rendersi
conto, a causa dell'errore che *comunque* si commette nel misurare
la posizione dell'ago, se tale evento si verifichi o meno.
ma dal punto di vista logico non si può escludere la possibilità 
teorica che esso si verifichi: esso, cioè è solo "fisicamente" impossibile.
(un evento "logicamente impossibile" sarebbe invece quello che ad esempio
l'ago si fermasse contemporaneamente in due posizioni distinte).
questo è ciò che dice il calcolo delle probabilità al riguardo.
giulio
p.s. mi sa che stiamo andando clamorosamente o.t.


 La morte e' FISICAMENTE possibile, non CERTAMENTE...
Francamente non ho capito niente. La morte è un evento possibile sia in
teoria che in pratica e ad essa si può associare una probabilità
dipendente, ad esempio, dagli stili di vita di una persona (e questo è
quello che normalmente fanno in campo sanitario per stimare la mortalità
delle popolazioni). Un evento fisicamente impossibile, invece, non è
possibile e basta. Che senso ha dire che una cosa potrebbe succedere in
teoria ma in pratica non può mai verificarsi?
EMG

 p.s. mi sa che stiamo andando clamorosamente o.t.
Hai ragione.
EMG

 dicevo io?
sì, sono eventi che pur avendo probabilità nulla (nel senso strettamente 
matematico del termine) possono comunque teoricamente verificarsi.
giulio



Non è affatto probabile. Al contrario usando la tua logica dovresti
giocarti i numeri che NON ritardano, quelli sono numeri che escono!!.
:-)
Vorrei fare una osservazione:
L'equiprobabilita` è una ASTRAZIONE MATEMATICA e non si puo` ottenere
nella realta`, ho sentito parlare molto di palline in precedenza, ma quelle
sono
solo palle matematiche...ehm... volevo dire palline astratte, infatti uno
dei requisiti
per ottenere l'equiprobabilita` e` che le palline siano identiche per
dimensioni
e peso poiche`, innegabilmente, l'estrazione essendo un processo fisico, e`
legata a tali parametri.
Quindi posso affermare che, sicuramente, nel caso del lotto dobbiamo parlare
di 'quasi-equiprobabilita`'.
Quanto cio` possa influire sull'estrazione solo Dio lo sa (non gioca a
dadi).
Un saluto a tutti, Enzo.
P.S. non potro` inoltrare messaggi prima del 8/4/'99
Buona Pasqua!

Ho dimenticato di dire che non esistono due palline uguali
e scusatemi volgarita` eventuali.
Vi saluto con la mia testa sotto i vostri piedi.
Enzo.
squa...@sirius.pisa.it

 legata a tali parametri.
Questo fatto era già stato notato ma con la tua puntualizzazione mi hai
dato da pensare. Forse i numeri più ritardanti sono proprio quelli che
il processo fisico dell'estrazione non favorisce vuoi perché le palline
sono diverse o altre differenze inevitabili. Vogliamo provare a giocare
i numeri che escono più frequentemente? :-)
EMG

>
ES> 
ES> Non è affatto probabile. Al contrario usando la tua logica dovresti
ES> giocarti i numeri che NON ritardano, quelli sono numeri che escono!!.
ES> :-)
ES> 
tanto per fare il pignolo, direi che e' probabile: la sua probabilita'
e' di 1/18... semmai non e' _piu'_ probabile :-)
ES> Vorrei fare una osservazione:
ES> L'equiprobabilita` è una ASTRAZIONE MATEMATICA e non si puo` ottenere
ES> nella realta`, ho sentito parlare molto di palline in precedenza, ma quelle
ES> sono
ES> solo palle matematiche...ehm... volevo dire palline astratte, infatti uno
ES> dei requisiti
ES> per ottenere l'equiprobabilita` e` che le palline siano identiche per
ES> dimensioni
ES> e peso poiche`, innegabilmente, l'estrazione essendo un processo fisico, e`
ES> legata a tali parametri.
ES>
pero' aggiungerei che e' un evento caotico, in quanto molto
sensibile alle condizioni iniziali.
Anche se conoscessi peso e dimensioni e tutto quello che vuoi delle palline,
non riusciresti mai a conoscere in anticipo i numeri che usciranno.
Pertanto l'equiprobabilita' sembra confermata... quanto meno fino ad ora
nessuno ha mai dimostrato il contrario :-)
ES> Buona Pasqua!
ES> 
altrettanto :)
Ciao!
-- 
Emanuele Cesena		
http://www.geocities.com/SiliconValley/Grid/8879
ami...@iol.it
 :)			 Occhio all'antispammer NOSPAZ!!
Scaricate ora Bubble 2000, ver. beta 1 :-)
http://gpi.eden.it/italianware/games/b2000b1.exe
 (900kb, ma il server e' buono!)
"Piu' e' urgente il motivo per cui si fa una cosa, piu' lento sara'
l'impiegato allo sportello", regola di Flugg

Un bel di' Enrico Maria Giordano scrisse:
EMG> Questo fatto era già stato notato ma con la tua puntualizzazione mi hai
EMG> dato da pensare. Forse i numeri più ritardanti sono proprio quelli che
EMG> il processo fisico dell'estrazione non favorisce vuoi perché le palline
EMG> 
Purtroppo quello che dici non sta molto in piedi...
Infatti le palline NON coincidono con il numero... voglio dire, il numero
e' su un pezzo di carta, che viene imbussolato, ma non necessariamente
sempre nella stessa pallina, anzi!
Quindi, a meno che le palline siano identiche ed i pezzi di carta
differenti, direi che i numeri non possono essere sfavoriti :-)
EMG> sono diverse o altre differenze inevitabili. Vogliamo provare a giocare
EMG> i numeri che escono più frequentemente? :-)
EMG>
Tranquillo che ci giocano gia' in molti!! :-))
-- 
Emanuele Cesena		
http://www.geocities.com/SiliconValley/Grid/8879
ami...@iol.it
 :)			 Occhio all'antispammer NOSPAZ!!
Scaricate ora Bubble 2000, ver. beta 1 :-)
http://gpi.eden.it/italianware/games/b2000b1.exe
 (900kb, ma il server e' buono!)
"Quando il vostro gatto vi si e' addormentato in grembo e ha l'aria
perfettamente felice e adorabile, dovrete improvvisamente andare in bagno",
legge della frustrazione da felino

 sensibile alle condizioni iniziali.
Altra osservazione che trovo giusta ed interessante...
EMG

 Tranquillo che ci giocano gia' in molti!! :-))
Su questo non avevo dubbi... :-)
EMG

Un bel di' Enrico Maria Giordano scrisse:
EMG> assolutamente inutile uno studio statistico delle estrazioni. Vogliamo
EMG> quindi parlare di 'aprobabilità' invece che di 'equiprobabilità', come
EMG> suggerisce l'amico Marco?
EMG> 
Mah... secondo me parlare di aprobabilita' non porta a nessun risultato...
finche' non si trova qualcosa di meglio, l'"assioma" dell'equiprobabilita' 
delle palline ci permette di calcolarci la probabilita' delle nostre
combinazioni, e questo, secondo me, e' piu' che sufficiente :-)
Ciao!
-- 
Emanuele Cesena		
http://www.geocities.com/SiliconValley/Grid/8879
ami...@iol.it
 :)			 Occhio all'antispammer NOSPAZ!!
Scaricate ora Bubble 2000, ver. beta 1 :-)
http://gpi.eden.it/italianware/games/b2000b1.exe
 (900kb, ma il server e' buono!)
"Non replicare mai un esperimento riuscito", legge di Fett

 combinazioni, e questo, secondo me, e' piu' che sufficiente :-)
Sufficiente a far che? A vincere? Se si allora sono d'accordo. Ma
siccome temo che non sia così devo per forza pensare che l'"assioma" sia
errato. Tra parentesi, ho finalmente fatto una semplicissima statistica
su tutte le estrazioni passate e ho visto due cose:
1. Tutti i numeri sono usciti più o meno lo stesso numero di volte (da
3200 a 3600 circa, abbastanza costante considerando il numero limitato
di campioni).
2. Sapere questo non aiuta a conoscere le uscite della prossima
estrazione (o almeno io non ci sono riuscito).
EMG

 [...]
Scusa, mi spieghi l'utilità dei sistemi ridotti nel superenalotto?
-----------------------------------------------------------
Christian Salvaneschi
Casarza Ligure, Genova, Italy
e.mail: 
crj...@geocities.com
 (remove 214 for email reply)
web: 
http://www.geocities.com/SiliconValley/Lakes/5139

> combinazioni, e questo, secondo me, e' piu' che sufficiente :-)
EMG> 
EMG> Sufficiente a far che? A vincere? Se si allora sono d'accordo. 
EMG>
no: a capire che, in teoria, non si puo' vincere... se vinci e' di c**o :-)
EMG> Ma
EMG> siccome temo che non sia cosě devo per forza pensare che l'"assioma" sia
EMG> errato. Tra parentesi, ho finalmente fatto una semplicissima statistica
EMG> su tutte le estrazioni passate e ho visto due cose:
EMG> 
EMG> 1. Tutti i numeri sono usciti piů o meno lo stesso numero di volte (da
EMG> 3200 a 3600 circa, abbastanza costante considerando il numero limitato
EMG> di campioni).
EMG>
si', c'e' chi dice che i numeri alti sortiscano piu' frequentemente,
ma, dopo una discussione, e' risultato che i dati non supportano
questa tesi.
Comunque, visto che siamo OT, se vuoi continuare la discussione, passa
in it.hobby.lotto :-)
 
EMG> 2. Sapere questo non aiuta a conoscere le uscite della prossima
EMG> estrazione (o almeno io non ci sono riuscito).
EMG> 
nemmeno io ci riesco, 'azz :-))
Ciao!
-- 
Emanuele Cesena		
http://www.geocities.com/SiliconValley/Grid/8879
ami...@iol.it
 :)			 Occhio all'antispammer NOSPAZ!!
Scaricate ora Bubble 2000, ver. beta 1 :-)
http://gpi.eden.it/italianware/games/b2000b1.exe
 (900kb, ma il server e' buono!)
"The difference between theory and practice is that in theory, there is no
difference, but in practice there is"

-----------------------------------------------------------
Le riduzioni di sistemi nel superenalotto si basano sul fatto di azzeccare K
numeri fra N in gioco.
Praticamente si scelgono N numeri su 90. Supponiamo siano 15. Poi decido che
voglio fare un sistema che mi consenta di fare almeno un 4. La riduzione
assicura che se fra i 15 numeri in gioco c'erano i 6 della colonna vincente,
nella mia riduzione c'e' almeno un 4.
E' ovviamente palese il fatto che giocando un numero di colonne casuali
uguale a quelle del sistema ridotto, la probabilita' che abbiamo di fare 6
e' la stessa, ma non quella di fare un (e sottolineo UN) 4, xche' nelle
colonne casuali ci possono essere delle ripetizioni di serie di 4 che nella
riduzione controllata non c'e'.
Ciao,
Stefano

 scrisse nei seguenti NG: it.comp.lang.c:
C> Scusa, mi spieghi l'utilità dei sistemi ridotti nel superenalotto?
C>
spendi meno :-)
-- 
Emanuele Cesena		
http://www.geocities.com/SiliconValley/Grid/8879
ami...@iol.it
 :)			 Occhio all'antispammer NOSPAZ!!
Scaricate ora Bubble 2000, ver. beta 1 :-)
http://gpi.eden.it/italianware/games/b2000b1.exe
 (900kb, ma il server e' buono!)
"L'esperienza e' direttamente proporzionale all'attrezzatura rotta",
postulato di Horner