Newsgroup: it.comp.lang.visual-basic
Titolo: Algoritmo estrazione valori

Salve a tutti,
ho il seguente problema: avendo un Array di 30 numeri tutti diversi, come č
possibile estrarre 5 valori random in modo da non avere valori doppi tra
quelli estratti?
Faccio un esempio:
MyArray = Array(2,4,10,70,45,1 ...)
i valori estratti devono essere unici, ad esempio
10,70,2,4,1
e non
10,10,2,4,1
dove il numero 10 č stato prescelto 2 volte
Spero di essermi spiegato bene,
grazie e buon lavoro ...

Penso ke puoi fare un ciclo in che si ripete finchè il numero estratto non è
già risultato in precedenza:
es. hai estratto10
all'estrazione successiva esce di nuovo 10, fai il confronto con IF e ti
darà che è già uscito quindi fai un'altra estrazione e quella che hai fatto
non la consideri. Prima o poi esce sicuramente un numero diverso a meno che
non vuoi estrarre da un array di n numeri, n+1 numeri: in tal caso sarà un
ciclo infinito!

 hai fatto non la consideri.
e se esce 10 poi 5 e poi ancora 10? <eg>

a ogni estrazione si confronta con tutti i numeri estratti in precedenza!!!
Mi sembra logico

 precedenza!!! Mi sembra logico
1) Dal post di prima non sembrava così logico
2) E' una soluzione piuttosto masochistica che potrebbe andare bene solo per
array con pochi numeri, altrimenti rischieresti di creare un ciclo "quasi"
infinito
ciaociao

 quelli estratti?
Premettiamo quindi che il tuo array con contenga valori doppi, ok?
Altrimenti al più ti fai un sottoarray dove non compaiono i valori duplicati
(però non sarà più di 30 elementi.
Quindi il problema é scegliere 5 indici diversi...
Direi:
Const DimArray as integer = 30 'Sostituibile con un non altrettanto
efficiente UBound(Array)
Const NumEstrazioni as integer = 4 'Togli uno a questo numero 5-1 = 4
Randomize
Dim IndiciEstratti() as integer
ReDim IndiciEstratti(NumEstrazioni-1)
Dim N as integer
Dim K as integer
For N = 0 to NumEstrazioni
  IndiciEstratti(N) = CInt(rnd * (DimArray - N))
  For K = 0 to N-1
      if IndiciEstratti(K) <= IndiciEstratti(N) then IndiciEstratti(N) =
IndiciEstratti(N) + 1
  Next K
Next N
    Ciao
        Allanon
-- 
- SPAMKILLER
 lasciate il NOSPAM nell'indirizzo: 
itlangv...@michele.sytes.net
 e lasciate la parola SPAMKILLER nel corpo dell'email

Non è vero perchè comunque per fare un confronto non ci mette quasi niente.
Poi non credo che devo mettere tutto in bocca col cucchiaino....
Per esempio io non ho mai usato la funzione per estrarre numeri casuali,
però se qualcuno chiede una cosa ke segue questo argomento uso un po' di
logica e ci arrivo..... non è che per rispondere chiedo prima come si usa la
funzione per l'estrazione casuale!
:-)

Supponiamo che tu abbia un array con 10 elementi: Arr (2, 45, 3, 6, 74, 1,
35, 4, 66, 7)
Indicizzi ogni elementi dell'array creandoti una collection o qualcosa di
simile, ovvero:
2 , index=0
45, index=1
3 , index=2
6 ,index=3
.....
Estrai un numero a caso tra 0 e 9 e recuperi l'elemento associato,
controllando che il numero estratto non si ripeta.
In sostanza cerca di astrarre il problema, così non ha importanza che il tuo
array sia composto da numeri, oggetti, patate, ecc.
Con una collection puoi anche facilmente manipolare array di "lunghezza"
diversa.
Perdona la sinteticità del post (si dice così?).
Ciao, Luca.

Si. L'ho visto in un programma per l'estrazione dei numeri per la tombola
che faceva cosě fino all'ultimo numero e comparivano cmq tutti molto
velocemente....anzi pensa ke il programma era scritto in linguaggio pascal!

 a ogni estrazione si confronta con tutti i numeri estratti in
precedenza!!!
In parole povere "scarti le collisioni"... teoricamente queste sono poche
però non hai un diretto controllo su quanti cicli possono essere necessari
per risolvere il problema... La tua soluzione é ottimale se il numero di
estrazioni é piccolo rispetto al numero di elementi da estrarre (e
soprattutto se la tua sfiga informatica é contenuta)...


 :-)
ciaociao

 doppi tra quelli estratti?
Sia A l'array che contiene i valori:
Randomize
v = UBound(A)
While v <> -1
    r = Int(Rnd * (v + 1))
    MsgBox A(r) ' numero estratto
    A(r) = A(v)
    v = v - 1
Wend
<x:termoPilucco>, facile, veloce.

 <x:termoPilucco>, facile, veloce.
...e sbagliato! :-)
1) Non può ripetere valori (quindi che ne sai che a(v) non sia ancora stato
estratto?).
2) Anche se fossi sicuro che a(v) non venisse mai estratto nel momento in
cui ne crei X copie alzi notevolmente la probabilità che venga estratto...


estratto?).
Leggi meglio l'algoritmo, fidati del termoPilucco.
In particolare osserva l'istruzione "v=v-1"
<x:termoPilucco>, sbagliato? :O

ma l'array iniziale ti serve?
no perchè ci sono varie tecniche...
allora, secondo me la tecnica migliore è quella di mettere i numeri estratti
in un array, effettuando però l'inserimento ordinato, cioè inserisci
l'elemento nel vettore al posto giusto mantenendo l'ordine crescente.
Poi, per la ricerca, utilizza un algoritmo più efficiente tipo quello per la
ricerca dicotomica, che richiede al massimo (log in base 2 di n)-1
confronti, dove n è la dimensione dell'array.
algoritmi:
v: array da cui estrai i numeri
z: array in cui inserisci i numeri
el: elemento estratto
r: riempimento del vettore z, (totale degli elementi finora inseriti)
inserimento ordinato:
pos=1
do while Z(pos)<El
   pos=pos+1
loop
for i=r to pos, -1
  z(i+1)=z(i)
next i
z(pos)=el
r=r+1
ricerca dicotomica:
inf=1
sup=1
c=(inf+sup)/2 (arrotonda per difetto please, non ricordo qual'è l'istruzione
corretta)
do while (inf<=sup) and (Z(c)<>El)
  if (inf<=sup) then
    sup=c-1
   else
     inf=c+1
loop
if inf>sup then <inserimento ordinato di el>
    else
     <nuova estrazione di EL>
credo che questo metodo sia sufficientemente veloce:
fai conto di avere 2048 elementi nel vettore, e di dover estrarre 5
elementi:
per ogni ricerca farai al massimo log2(2048)-1 confronti (che è l'operazione
che fa perdere più tempo alla cpu dopo le operazioni trigonometriche) cioè
19 confronti, supponendo che non si verifichi mai che estrai un numero già
estratto fai 19 x 5 confronti cioè 95.
Tieni conto che il tempo perso per le assegnazioni alle variabili (purchè
dichiarate del tipo giusto) è davvero irrisorio, e supponendo che su 5
numeri 2 sono stati già estratti, andrai ad effettuare, nel caso +
sfortunato 19 x 7...
insomma, un'inezia!

ps: la ricerca dicotomica RICHIEDE un vettore ORDINATO in modo crescente
(modificando un po puoi anche ottenere l'rdinamento decrescente)
un'altra tecnica, ancora più veloce, sarebbe quella di, avendo sempre un
vettore ordinato, di eliminare, di volta in volta che li estrai, i valori
dal vettore, che essendo ordinato, sono tutti contigui... quindi elimini
(virtualmente memorizzandoci un -1 ad esempio, oppure proprio fisicamente
facendo lo shift up di tutti gli elementi sottostanti) tutti gli elementi
pos+1 pos+2 pos+3 ecc finché non risulta pos+i<>el e tutti i pos-1 pos-2
pos-3 finchè non risulta pos-i<>el...
e così via per ogni numero estratto.
Così hai la sicurezza di non poter estrarre un numero già estratto dato che
è stato cancellato :)
se poi il vettore ti serve te ne puoi anche fare un copia...

 .....
Mi è venuta in mente una soluzione che forse è la più semplice di tutte.
Uso una collection per comodità:
1 Creo una collection con tutti i numeri contemplati, quindi in questo caso
da 1 a 30.
2 Con Rdn trovo un numero tra 1 e MyCollection.Count.
3 Il numero estratto è MyCollection(MyRndIndex)
4 Rimuovo l'elemento MyRndIndex dalla collection
(MyCollection.Remove(MyRndIndex))
5 Ripeto per quente volte voglio dal punto 2
Credo si possa trovare anche una soluzione "negativa" in modo che non sia
costretto a inizializzare la collection, metti nel caso di avere qualche
milione di elementi :)
Ciao
--
Math Parser : 
http://www.neodatatype.net
Sito Comune : 
http://www.it-lang-vb.net
--
Math Parser : 
http://www.neodatatype.net
Sito Comune : 
http://www.it-lang-vb.net

Io ti consiglio un metodo che ho usato spesso per simulare l'estrazione 
casuale di carte da un mazzo, ovviamente senza doppioni:
Hai il vettore TuoVett(1,98,45,100,23,33,45,10,54) che è di dimensione 
9, cioè possiede 9 elementi.
Quindi DimVett=9.
Dichiaro un vettore NumeriEstratti della stessa dimensione di DimVett e 
di tipo booleano.
Ogni elemento di questo vettore indica se il corrispettivo elemento del 
tuo vettore numerico è stato già pescato o meno.
Quindi pongo a Falso tutti gli elementi di questo vettore, perchè prima 
dell'estrazione nessun elemento è stato pescato.
L'algoritmo di estrazione è semplicemente questo:
Ripeti
	Ripeti
		Indice = Un numero casuale tra 1 e DimVett
		Elemento = TuoVett(Indice)
	Finchè NumeriEstratti(Indice) = False
	// Cioè ripeto l'estrazione finchè non becco un elemento
	// che risulta FALSO, cioè non pescato.
	NumeriEstratti(Indice) = True
	// Nelle prossime estrazioni risulterà pescato
Finchè non hai estratto quanti numeri ti servono
Più semplice di così si muore. L'unica pecca sta nel fatto che è 
raddoppiata la quantità di dati utilizzati. Se usi un vettore di 10.000 
elementi, dovrai usarne un altro delle stesse dimensioni per "ricordare" 
tutti gli elementi pescati.
Se poi volessi estrarre AL MASSIMO N volte ogni elemento, basterebbe 
applicare qualche piccolissima modifica all'algoritmo:
Ripeti
	Ripeti
		Indice = Un numero casuale tra 1 e DimVett
		Elemento = TuoVett(Indice)
	Finchè NumeriEstratti(Indice) < N
	// Cioè ripeto l'estrazione finchè non becco un elemento
	// che risulta FALSO, cioè non pescato.
	NumeriEstratti(Indice) = NumeriEstratti(Indice) + 1
	// Nelle prossime estrazioni risulterà pescato
Finchè non hai estratto quanti numeri ti servono
Et voilà!!!
-- 
Nella vita una sola cosa è certa: se la storia ci ha insegnato qualcosa, 
è che si può uccidere chiunque.
(Michael Corleone)

 wrote in message

Il Pascal *č* molto veloce.


 MyArray = Array(2,4,10,70,45,1 ...)
D'accordissimo su quello che ha detto Vegeta, provo a tradurre in linguaggio
ciò che lui già ti ha detto:
'-----------------------------------------
Dim flag(5) As Integer 'Ho preferito usare ineteger al posto di boolean, ma
è lo stesso.
Dim a As Integer
Dim i As Integer
Randomize
    For i = 1 To 5
        Do
            a = Int(Rnd * 6)
        Loop Until flag(a) <> 1
        Print MyArray(a)
        flag(a) = 1
    Next i
'------------------------------------------
In questo codice ho usato i valori del tuo array;se volessi generalizzare
basterebbe sostituire:
dim flag(ubound(MyArray))
e
a=int(Rnd*ubound(myarray)+1)
rispettivamente nella prima e nella settima riga del codice sopra.
Spero di esserti stato utile
Ciao, Giuseppe

ottima la soluzione del flag, solo che io li metterei in un array
bidimensionale.
Oppure, se l'array iniziale non serve piů dopo l'estrazione puoi mettere
qualcosa stesso nel vettore di partenza, del tipo
v(i) = - v(i) cosě se il numero č <0 vuol dire che č giŕ estratto.
Se poi vuoi riportare il vettore allo stato iniziale dopo questa tecnica fai
for i = 1 ad R
 v(i) = v(i) -  v(i) + v(i) oppure abs(v(i))
next i

 next i
Scusate tutti... ma la mia soluzione
Randomize
v = UBound(A)
While v <> -1
    r = Int(Rnd * (v + 1))
    MsgBox A(r) ' numero estratto
    A(r) = A(v)
    v = v - 1
Wend
era troppo semplice e veloce?
Sono quattro istruzioni per ogni numero estratto: niente ricerche,
ordinamenti, collection.
<x:termoPilucco> e funziona, perbacco.

 In particolare osserva l'istruzione "v=v-1"
Ops....
E molto giusto! :-(
E anche molto veloce!!!
W termipilucco!!!!!!!!!! :-)


 Wend
allora...
a parte che il ciclo while - wend, scritto in quel modo, mi sembra molto
simile a un
for v = ubound(A) to 0 step -1
per il resto direi che funziona egregiamente...
domanda cattiva... č farina del tuo sacco? :-)
(se sě, sincerissima invidia)
--
Salutoni
Sergio
per rispondere... togli il group dall'indirizzo

 (se sì, sincerissima invidia)
Maddài...
<x:termoPilucco>, ^_^

 E' una tecnica nota, per caso? :0
sicuramente non nota a mč.
mi sembra che sia una egregia soluzione per il problema, ad esempio, del
"mescolamento" del mazzo di carte, ed in questo senso chiedevo se l'avevi
trovata da qualche altra parte.
rinnovo l'invidia, io ci ho messo un quarto d'ora solo a capire come faceva
a funzionare.


Zanna wrote:
: Mi è venuta in mente una soluzione che forse è la più semplice di
: tutte.
:
: Uso una collection per comodità:
:
: 1 Creo una collection con tutti i numeri contemplati, quindi in
: questo caso da 1 a 30.
: 2 Con Rdn trovo un numero tra 1 e MyCollection.Count.
: 3 Il numero estratto è MyCollection(MyRndIndex)
: 4 Rimuovo l'elemento MyRndIndex dalla collection
: (MyCollection.Remove(MyRndIndex))
: 5 Ripeto per quente volte voglio dal punto 2
:
: Credo si possa trovare anche una soluzione "negativa" in modo che non
: sia costretto a inizializzare la collection, metti nel caso di avere
: qualche milione di elementi :)
Esatto, buona soluzione!
Anche nei 3ad più sotto hanno "sfornato" buone cose, ai posteri l'ardua
sentenza...
Ciao, Luca.

 
Attenzione pero' che lavorare con una collection richiede piů tempo al
calcolatore rispetto ad un array.
-- 
Ciao,
        Fabrizio
<=- 
http://www.negusweb.it
 -=>

no, scusami tu, non oso dubitare, solo che ancora non sono riuscito a capire
il funzionamento della tua soluzione, mi credi? Ci sto pensando da un 10 min
:)

 :)
Non è immediato ma comunque semplice:
Hai un vettore di 10 elementi (da 1 a 10).
Scegli un numero 1<=N<=10
Stampi l'elemento Vettore(N)
Questo elemento non ti serve più, perciò Vettore(N)=Vettore(10), ed 
escludiamo Vettore(10) dalle estrazioni. In questo modo evitiamo di 
ripescarlo. Ora ci restano tutti i numeri che non abbiamo ancora estratto.
Quindi Ora torni a estrarre N, ma anzichè essere compresa tra 1 e 10 
sarà compresa tra 1 e 9.
E via via così, finchè non hai pescato quanti numeri ti servono.


 calcolatore rispetto ad un array.
Molto più tempo...
Credimi usa la soluzione di termopilucco che é ottimale! :-)


 Credimi usa la soluzione di termopilucco che é ottimale! :-)
Infatti avevo specificato che indicavo le collection solo per semplicità 
[di comprensione].
Quella di termopilucco è la stessa soluzione trasposta su array.
Ciao