Newsgroup: it.hobby.enigmi
Titolo: Algoritmo Combinazioni

Tempo fa per un discorso sul lotto, mi era stato fornito questo algoritmo
per determinare il numero di combinazioni possibili con N numeri (90) in una
combinazione (ambi, terno, ecc..) L'algoritmo č:
  ' Il numero di combinazioni di k numeri che si possono fare
  ' con n numeri e' uguale a n!/(k! * (n-k)!) dove il ! denota
  ' il fattoriale
Questo č valido per le combinazioni del lotto appunto, e tutte le altre in
cui invertire un valore non conta; ma se dovessi determinare le combinazioni
per cui AB č differente da BA quale algoritmo dovrei utilizzare? Serve
sempre il fattoriale, altro oppure un ciclo non me lo toglie nessuno?
Grazie ^_^
-- 
 _____________________________________________________________
|                                                             |
| Coboldo.Net: 
www.coboldo.net
    ~ ~ ~ ~ ~ Blog Gratuito     |
|-------------------------------------------------------------|
| Ludico.Net: 
www.ludico.net
      ~ ~ ~ ~ ~ Cazzeggio         |
|-------------------------------------------------------------|
| AGATA Quest: 
agata.ludico.net
   ~ ~ ~ ~ ~ Enigmi            |
|-------------------------------------------------------------|
| CineQuest Pro: 
www.ludico.net/cquest.asp
  Film Invisibili)  |
|--------------------------------------------------------------

 sempre il fattoriale, altro oppure un ciclo non me lo toglie nessuno?
In questo caso basta il fattoriale semplice.
Infatti in 1° posizione può andare uno qualunque degli "n" valori, in 2° uno 
qualunque dei
rimanenti (n-1) valori e così via.
Quindi:        n*(n-1)* (n-2)* ......* 2*1 = n!
Ciao
Gianni
--
Avete visto la faccia del Nano Pelato durante l'insediamento di
Napolitano?
Io mi sono divertito un sacco!! ;-))

 sempre il fattoriale, altro oppure un ciclo non me lo toglie nessuno?
Credo che basti:
n! / (n-k)!
Che equivale a questo:
n*(n-1)*(n-2)* .... *(n-k+1)
se n= 90 e k= 6, per esempio: 90*89*88*87*86*85
(infatti hai 90 possibili scelte per il primo numero. Poi ne hai 89 per
il secondo numero. E così via).
se poi è possibile anche AA (cioè se il numero estratto viene
reinserito nell'urna), allora è ancora più semplice:
n^k
Ciao!

 Quindi:        n*(n-1)* (n-2)* ......* 2*1 = n!
Io l'ho interpretata come se tutti gli n valori fossero da disporre.
Nel caso in cui i valori da disporre fossero solo una parte, la formula 
corretta e quella che ti ha segnalato "Il raccattapalle".



non ho idea di cosa significhi :S

 reinserito nell'urna), allora č ancora piů semplice: n^k
esatto č possibile anche AA perň non mi spiego una cosa, non č
che in questo modo mi conta AA due volte? AB e BA sono due non č
che mi calcola in questo modo AA e AA (ribaltato)...

> n^k
però a me non torna :( esempio ho una sola posizione che
può assumere 20 differenti valori, esistono quindi 20
combinazioni mentre 1^20 = 1 come si spiega? Ho detto una
stupidata (scelta consigliata)?

Ludico.Net ha scritto:

Se "estrai" un numero che può andare da 1 a 20, allora n=20 e k=1.
Quindi n^k = 20^1 = 20 e tutto torna! :-)


mannaggia, devo smetterla con la birra :D
per l'altro messaggio sopra a quello a cui hai
risposto cosa mi puoi dire? Si hanno duplicati
AA? Voglio dire se mi conteggia AB e BA allora
non rischia di contare anche AA e AA invertito?

 stupidata (scelta consigliata)?
n sono i valori e k le posizioni quindi
20^1 = 20


 che mi calcola in questo modo AA e AA (ribaltato)...
No, AA lo conta una sola volta.
Te lo dimostra questo esempio semplicissimo.
supponiamo n=3 (A, B, C) e k=2
n^k = 3^2 = 9
E infatti ho 9 combinazioni: AA, BB, CC, AB, AC, BC, BA, CA, CB.
Ciao!

 non ho idea di cosa significhi :S
Significa che se tu avessi le 21 lettere dell'alfabeto e volessi sapere in 
quanti modi sia possibile disporle *tutte quante assieme*, la formula 
sarebbe 21!
Se invece volessi sapere quanti gruppi diversi da 5 lettere si possono 
avere, la formula sarebbe 21!/ (21-5)!, come suggerito da "Il 



Forse è necessaria una chiarificazione, pensavo di rendere il discorso
meno complicato evitando di inserirla inzialmente, ma evidentemente è
una cosa necessaria. Mi serve di calcolare le combinazioni possibili per
un campo password, e successivamente determinare un "indice di sicurezza"
così da avvisare l'utente se è una pwd valida o sciocca. Questo senza
controllare pwd di senso compiuto cui l'utente viene immediatamente
sconsigliato di utilizzare.
In pratica, se la pwd (P) è composta da soli numeri ho 10 [0..9] possibili
combinazioni se la password è composta da 1 carattere, in questo caso un
solo numero appunto. Se utilizzasse anche le lettere avrei esempio 10 + 21
per un minimo di due caratteri 31^2 giusto? Se usa lettere minuscole,
simboli
ecc... le combinazioni aumentano. Mi serve quindi:
- Trovare un algoritmo per determinare le combinazioni possibili passando
C (il numero di caratteri) e L (lunghezza della stringa). Dove C, suppongo,
debba essere il valore possibile del range rispetto al carattere usato,
esempio
se usa nella password A31e dovrò considerare 21 lettere maiuscole + 21
minuscole
e altri + 10 dei numeri, dico bene 52^4 si?
- Determinato in X il valore delle combinazioni, attribuire sulla base di
solo
questo dato una sicurezza determinata dividendo X per il numero di
combinazioni
massime ottenibili con un software che utilizzi il sistema brute force, dico
un
esempio, supponiamo che in condizioni ottimali sia possibile provare 10^5
pwd
al secondo il fattore di sicurezza F sarà F = X / 10^5 dopo questo passaggio
posso attribuire ad F un diversa interpretazione, esempio determinare una
pwd
sicura per lo scopo, in alcuni casi F = 7200 (2 Ore) potrebbe essere
considerato
sicuro (i.e.: la pwd cambia ogni 45 minuti) mentre in altri in cui viene
aggiornata ogni mese, potrebbe considerare 7200 assolutamente insicuro.
- (Opzionale) Stabilire se la sicurezza di una password è maggiormente
determinata
dalla sua lunghezza o invece dal numero di caratteri di cui è composta,
esempio è
più facile indovinarla se è una pwd di sole lettere minuscole a lunghezza 12
oppure una di lettere maiuscole, minuscole e numero di lunghezza 4? Credo
che questo possa però essere determinato con il calcolo di cui sopra. Cosa
interessante sarebbe proporre all'ultente come renderla più sicura, esmepio
"aggiungi 4 caratteri" oppure "aggiungi un tipo di carattere differente" e
così via...
Il sistema non dispone di un dizionario, potrei implementare anche questa
cosa
non la escludo, nel caso però la pwd fosse presente nel dizionario
attribuirebbe
F = 0 sempre a prescindere dallo scopo della stessa. Credo che dare
un'indicazione
basandosi sul sistema brute-force possa essere comunque utile; 1978 non sarà
mai
sicura come A!1g a mio avviso.

Ciao a tutti,
segnalo che il sito con le FAQ del newsgroup ha cambiato veste.
Potete accedervi con questo shortcut: 
http://www.marianotomatis.it/faq
Per retrocompatibilità, i link alle FAQ nei messaggi postati in passato 
continuano a funzionare...
http://www.marianotomatis.it/index.php?id=20&r=1
 ad esempio viene 
automaticamente convertito nel nuovo
http://www.marianotomatis.it/index.php?section=enigmi&enigma=1
Parallelamente troverete anche i problemi scacchistici più bizzarri:
http://www.marianotomatis.it/index.php?section=enigmi&enigma=1
e alcuni software che ho sviluppato su argomenti mysteriosi:
http://www.marianotomatis.it/index.php?section=software&tipo=mystero
Mariano 



Mariano Tomatis

 Potete accedervi con questo shortcut: 
http://www.marianotomatis.it/faq
C'è qualcosa che non mi quadra nell'enigma 1 - Le tre porte,
limitatamente a quanto riportato (ed asserito come conveniente)
nella Nota 1:
"Nota 1: In un recente quiz televisivo, "Chi vuol esser milionario?",
si presenta spesso una situazione simile a quella del problema.
Il concorrente, infatti, sceglie una risposta tra quattro, e chiede
che il computer ne elimini due tra le sbagliate. Restano, dunque,
la risposta scelta più un'altra. Se la prima risposta è stata scelta
a caso, allora conviene cambiare. Dal momento, però, che tale risposta
è spesso meditata, la considerazione probabilistica non è applicabile."
Non c'è alcuna convenienza a cambiare, visto che il computer non sa
cosa sceglie il concorrente, e potrebbe eliminargli la sua risposta
preferita.
Non ha infatti alcuna valenza il fatto che il concorrente fissi la
sua attenzione (in modo del tutto casuale) su una delle 4 risposte,
che ovviamente ha il 25% di probabilità di essere esatta, esattamente
come le altre 3 risposte che non fanno parte della sua scelta.
La situazione è completamente diversa dalle 3 porte, in quanto il
presentatore non può aprire la porta scelta, ma elimina una delle
due restanti (una delle 2 perdenti).
Il concorrente all'inizio è tentato di scegliere la risposta A.
Il computer elimina due tra le tre risposte sbagliate; esaminiamo
tutti i casi possibili:
1) La risposta giusta è A.
Il computer può togliere  B C  oppure  B D  oppure  C D.
In tutti questi 3 casi, se il concorrente tiene A vince, se cambia con
la risposta rimanente perde  ( Tiene = +3  ; Cambia = -3 )
2) La risposta giusta è B.
Il computer toglie  C D  e lascia  A B : se il concorrente tiene perde,
se cambia vince ( Tiene = -1  ; Cambia = +1 )
Però il computer può togliere  A C  o  A D ; in questi casi restano
B D  o  B C  e il concorrente non può scegliere di tenere o cambiare,
perchè A non è più presente
3) Lo stesso di B) si verifica se la risposta giusta è  C  o  D:
infatti, la scelta può essere fatta solo se il computer lascia  A
insieme alla risposta esatta, e il concorrente vince cambiando
( Tiene = -2  ; Cambia = +2 )
Complessivamente, quando il concorrente fa all'inizio la sua scelta
casuale, quindi, ci sono 12 possibilità: in 3 casi gli conviene
cambiare, in 3 casi gli conviene tenere e in 6 casi non può dire
nulla, perchè gli resta da scegliere ( con il 50% di probabilità)
fra 2 risposte diverse dalla sua scelta iniziale.
Ciao, Nino 

tutti i casi possibili:
Si`, e mi sembra che procedendo con le probabilita`,
anziche' con i casi, questa volta sia piu` veloce.
TENGO
Vinco se ho scelto la giusta: 1/4
Perdo se ho scelto la sbagliata: 3/4, e non mi viene
eliminata: 1/3. Totale: 3/4 * 1/3 = 1/4.
CAMBIO
Vinco se ho scelto la sbagliata: 3/4, e non mi viene
eliminata: 1/3. Totale: 3/4 * 1/3 = 1/4.
Perdo se ho scelto la giusta: 1/4
-- 
Ciao, rez	||  -- GNU/Linux 2.4.25 su Slackware 9.1  ||

 si presenta spesso una situazione simile a quella del problema.
A proposito del quiz del milionario.
Tra gli aiuti c'e' pure quello di chiedere al pubblico.
Tale aiuto potrebbe essere alquanto aleatorio se il pubblico venisse 
lasciato libero di scegliere, mentre potrebbe diventare un aiuto molto 
potente applicando una banale strategia, che non credo proprio che sia 
vietata dalle regole, eppure nessuno ci ha mai pensato.
Esempio.
Data la seguente domanda:
Quale dei segueti stati europei ha la maggiore superficie:
Svezia, Norvegia, Finlandia, Svizzera.
Potremmo avere tutti dei dubbi su quale scegliere tra Svezia, Norvegia e 
  Finlandia, mentre la Svizzera evidentemente non e' la risposta esatta.
E' il caso tipico in cui si puo' chiedere l'aiuto al pubblico invitando 
pero' il pubblico a scegliere la risposta esatta, solo se assolutamente 
sicuro, mentre chi ha un dubbio anche piccolo piccolo, scelga la Svizzera.
In questo modo io mi aspetto, se il pubblico mi vuole veramente aiutare, 
la Svizzera col 98%, un 2% su uno degli altri 3 e lo 0% per gli altri due.
Mi aspetto insomma che almeno 1 o 2 tra il pubblico conosca la risposta 
esatta, e che tutti gli altri, nel dubbio scelgano la risposta neutra 
che io so essere sbagliata.
Funziona, a patto che il pubblico voglia veramente aiutare il 
concorrente, e a patto che il regolamento consenta al concorrente di 
suggerire al pubblico tale strategia.

 Funziona, a patto che il pubblico voglia veramente aiutare il concorrente
La tua proposta e' ingegnosa e funzionerebbe a colpo sicuro, ma visto che 
siamo entrati nel tema del gioco di Scotti, avrei comunque un piccolo dubbio 
generale sul gioco: quanti sono i potenziali concorrenti che aspirano a 
giocare, ovvero che rispondono alla domanda eliminatoria per stabilire il 
concorrente? Se tutto il pubblico puo' aspirare a giocare troverei 
conveniente cercare di far sbagliare prma possibile il concorrente
Scusate , stasera mi sento un po ' carognetta... :-)
ciao
fulvio