random numere

se poate face un random de numere, de la 1 la 5,de exemplu, da fara sa se repete?
exemplu: 1,5,3,4,2

Daca nu vrei sa se repete cam ce ar trebui sa faci, avand in vedere ca functia respectiva poate returna acelasi numar? Aflandu-te la pasul "k" (a "k"-a generare de numar aleator), vrei sa nu se genereze un numar care s-a generat anterior ("k-1"), asa-i? Cum poti sti ce numere s-au generat anterior ca sa verifici la pasul "k" conditia de unicitate? Cum poti face asta? Gandeste putin!
Cum simulezi amestecarea unui pachet de carti? Nu poti avea 2 sau mai multe "aceleasi carti" intr-un pachet! Doar daca trisezi, dar nu-i frumos!
Nu vorbim aici de VB, C, etc. Vorbim de un algoritm.

Edited by Africanul, 27 September 2005 - 14:11.

fabby, on Sep 27 2005, 13:26, said:

Da, in principiu faci un array in care bagi valorile ce vrei sa le extragi, ii dai un random dupa care stergi din array valoarea extrasa pentru a nu o mai putea extrage.

Uite un exemplu in php:

<?php
$numere_de_ales =range(1,5);//creeaza un array cu valori de la 1-5

//afiseaza structura array
echo '<pre>';
print_r($numere_de_ales);
echo '</pre>';


$nr_valori_posibile=count($numere_de_ales);//numarul de elemente din array-ul initial

for($i=0;$i<$nr_valori_posibile;$i++){
     $nr_extras = array_rand($numere_de_ales, 1);//extrage random o cheie din array

     echo $numere_de_ales[$nr_extras];//afiseaza valoarea corespunzatoare cheii extrase
     echo "<br>";//linie noua
     unset($numere_de_ales[$nr_extras]);//sterge din array valoarea extrasa anterior

     }

?>

Care afiseaza:

Array
(
    [0] => 1
    [1] => 2
    [2] => 3
    [3] => 4
    [4] => 5
)

2
4
3
5
1

am gasit pan la urma ceva de genu:

Label1.Caption = ""
Randomize
n = 10
Label1.Caption = ""
For i = 1 To 10
    k = Int(1 + Rnd * n)
    If i = 1 Then
        a(i) = k
    Else
        For j = 1 To i - 1
            If k <> a(j) Then
                ok = True
            End If
            If k = a(j) Then
                j = 1
                k = Int(1 + Rnd * n)
            End If
        Next j
        If ok = True Then
            a(i) = k
        End If
    End If
Next i
Label1.Caption = ""
For i = 1 To 10
    Label1.Caption = Label1.Caption & " " & a(i)
Next i

insa nu stiu ca t de bun e..contine numai foruri, si ma gandesc ca la un numar mai mare...sta mult pana sa le parcurga pe toate...

unul incearca sa il forteze sa gandeasca, altul ii da rezolvarea pe tabla ... dar macar hotarati-va

sorry de off-topic

P.S. - eu sunt pe idea lu africanul, de aia n-am zis nimic la subiect: s-a zis suficient pina la urmatoarele intrebari ale omului

Revin!
Ai "gasit" o solutie. Era bine daca ai fi gasit-o tu, si nu un copy-paste amarat de pe internet...
Algoritmul care l-ai gasit tu, probabil ca merge. Teoria spune ca memorezi toate numerele generate anterior, si verifici, cand il generezi pe urmatorul, daca se afla printre cele generate anterior (si memorate fara nici o problema in vectorul ala). Daca noul numar generat mai exista in vector, atunci nu-i bine!, si trebuie sa se mai genereze inca o data un numar aleator, si iar sa se verifice daca mai exista in vectorul ala... Iti spun ca spre finalul gasirii tuturor numerelor, algoritmul de mai sus va merge din ce in ce mai greu (scade probabilitatea generarii unui numar aleator care sa nu mai fi fost generat anterior pentru un numar suficient de mare de generari). Daca vrei sa generezi 50 de numere, s-ar putea sa dai de "un fel" de bucla infinita chiar si pe un P4 la 3GHz! Complexitatea acelui algoritm este foarte mare.

Dar mai exista o solutie MULT mai simpla, de complexitate liniara, cu rezultate exceptionale! Trebuie sa te gandesti la o solutie mai simpla!

Hint: Ai 5 bile colorate, de diferite culori. Le ai deja in fata ta! Cum faci sa le amesteci in alta ordine, in cel mai simplu mod cu putinta?

Ce a scris ada80ro nu reprezinta un algoritm, este o facilitate a PHP-ului.

Edited by Africanul, 27 September 2005 - 15:50.

le pun intr-o caciula, si le agit

din moment ce am postat pe forum, inseamna ca nu stiu. nu am nici 1 idee!iar codu de mai sus e prea tampit, iar alta solutie nu gasesc. se pare ca trebuia sa acord mai multa atentie orelor de informatica din liceu...

#include <stdlib.h>
#include <time.h>

#define	NR_MAX  10   // cate numere vrei sa generezi
#define	MAX_SWAP	10  // de cate ori amesteci numerele alea. Este suficient ca MAX_SWAP<=NR_MAX

int _tmain(int argc, _TCHAR* argv[])
{
  long  v[NR_MAX], i, index1, index2, temp;

  srand(time(NULL));	// nu te speria de linia asta! (optionala)

  // initializam vectorul cu numerele (precum vezi sunt unice)...
  for (i=0; i<NR_MAX; i++) v[i] = i;
  // ... si le amestecam putin! Adica:
  for (i=0; i<MAX_SWAP; i++) {
    // alegem la intamplare doua elemente din vector...
    index1 = rand()%NR_MAX;
    index2 = rand()%NR_MAX;
    if (index1 == index2) index1 = (index1 + 1) % NR_MAX;	// sa nu amestecam acelasi numar cu el insusi - n-are rost! (optionala)

    // ... si schimbam intre ele valorile celor doua elemente
    temp = v[index1];  
    v[index1] = v[index2];
    v[index2] = temp;
  }

  // Asta-i tot! Rezultatul amestecarii il gasesti tot in vectorul v, evident!
  for (i=0; i<NR_MAX; i++) printf("%ld ", v[i]);

  return 0;
}

Meserie, nu?
De fapt, chestia este sa schimbi valorile a doua elemente alese aleator din vector, de cateva ori (MAX_SWAP)! Asta-i tot!
Precum vezi, totul decurge liniar, curat, rapid. Pentru generarea unui carnat de numere aleatoare unice, ce ti-am dat eu este arhi-suficient! Vorbim de numere aleatoare, doar!

Edited by Africanul, 27 September 2005 - 17:41.

hmmm, nu pare foarte aleatorie metoda ta de generare de permutari. de exemplu, spune-mi exact cat de mare trebuie sa fie MAX_SWAP ca sa ai o secventa de numere cu adevarat aleatorie??

de exemplu (la o extrema):

daca NR_MAX = 10 si MAX_SAWP = 2, banuiesc ca este evident ca secventa ramane partial ordonata. daca mai ai si ghinionul ca index1  sa fie egal index2, atunci doar vei schimba locul a doua numere adiacente, ceea ce iar nu e foarte aleator.

se poate considera ca daca ai facut din {1, 2, 3, 4, 5, 6} -> {1, 2, 4, 3, 6, 5} ai obtinut o permutare aleatorie?

bineinteles, vei spune, "pai atuncea sa ia un MAX_SAWP suficient de mare si nu o sa mai fie probleme". intrebarea asta e: cat de MARE? si nu numai "cat de mare", ci "cat de mare in functie de NR_MAX"!

daca raspunzi si la chestia asta (cu tot cu demonstratie), atuncea intradevar s-ar putea zice ca ai obtinut un algoritm de generare aleatorie. pana atunci...

secventa de numere cu adevarat aleatorie??? Ce-i aia?
Este cel mai tare algoritm! Te asigur! Inca o data: vorbim de numere aleatoare!
Primul algoritm, ala "complet", cu ce este mai bun decat asta al meu?

Edited by Africanul, 27 September 2005 - 17:59.

raspunsul pentru shapo cred ca ar fi:
"MAX_SWAP<=NR_MAX"

Va multumesc pentru idei, in special Africanului, ca i-am aplicat metoda...si sincer nu-mi dadea prin minte sa fac treaba asta:
e f buna metoda lui pentru ce vreau sa fac: un stupid joc de puzzle
index1 = rand()%NR_MAX;
index2 = rand()%NR_MAX;

Africanul, on Sep 27 2005, 17:58, said:

teoria obtinerii de numere aleatoare este destul de complexa. sunt o groaza metode unele mai bune, altele mai putin bune. in principiu, din cate stiu (nu stiu mare lucru), e vorba sa rulezi chestiunea respectiva si sa nu obtii repetari decat dupa nu-stiu-cate rulari.

sa folosim exemplul dat de mine: faci NR_MAX = 10 si MAX_SWAP=2. Care este probabilitatea ca ruland de 2-3 ori algoritmul tau nici macar sa nu te atingi de unul din numere, ala sa ramana tot pe loc? eu zic ca e destul de mare, in nici un caz atat cat ar trebui. evident, daca MAX_SWAP e destul de mare, vei obtine pana la urma o permutare pseudo-aleatorie. dar, asa cum am zis, asta e intrebarea: cat de mare sa fie MAX_SWAP?

primul algoritm are avantajul ca practic rearanjeaza toate numerele, si le obtii exact asa cum zice initiatorul thredului: "le pun intr-o caciula, si le agit". evident, se poate putin optimiza (daca intereseaza pun algoritmul gandit de mine in c++, care cred ca se poate optimiza si mai mult), insa ideea ramane cam aceeasi: sa pui toate elementele la un loc, apoi sa le scoti pe rand intr-o ordine aleatorie.

Edited by sapho, 27 September 2005 - 18:22.

fabby, on Sep 27 2005, 18:17, said:

ma rog, asta am vazut-o de la inceput, dar am considerat-o ca greseala de tastare , e vorba mai degraba de
MAX_SWAP >= NR_MAX

Edited by sapho, 27 September 2005 - 18:25.

asta e varianta mea, in C++. nu stiu daca VisualBasic are multimi in librarii, dar banuiesc ca da. programul e foarte rapid chiar si pentru numere foarte mari, practic viteza cred ca e limitata numai de afisarea pe ecran, chiar si la numere foarte mari de elemente (gen 10000). dovada ca sunt foarte bine optimizate set-urile in STL.

spre deosebire de algoritmul lui Africanul nu are acea incertitudine legata de corectitudinea amestecarii elementelor.

oricum, banuiesc ca pentru puzzle-ul lui fabby e suficient si algoritmul de mai sus. eu am luat problema ca pe un exercitiu si am incercat sa pun o solutie care sa respecte cat mai bine "specificatiile".

#include <cstdlib>
#include <iostream>
#include <set>
#include <ctime>

using namespace std;

int main(int argc, char *argv[]) {

    const int sz = 1000;       // numarul de elemente
    
    int v[sz];                 // solutia
    int random;                // nr ajutator
    set<int> iset;             // multimea elementelor de "amestecat"
    set<int>::iterator it;     // iterator pe aceasta multime
      
    srand(clock());                                        // optional :D
    for (int i = 1; i <= sz; ++i) iset.insert(i);          // initializare multime

    for (int i = 0; i < sz; ++i) { 
        random = rand() % iset.size();                     // nr aleator,  < nr de elemente ramase
        it = iset.begin();                                 // iterator catre primul element ramas
        for (int j = 0; j < random; ++j) ++it;             // iteratorul se muta la un element ales random
        v[i] = *it;                                        // punem elementul in solutie
        iset.erase(it);                                    // elementul este scos din multime
    }
    
    for (int i = 0; i < sz; ++i) cout << v[i] << "\t";     // afisare
    cout << endl;
    
    system("PAUSE");
    return EXIT_SUCCESS;
}

Edited by sapho, 27 September 2005 - 22:20.

@sapho: Iti complici viata degeaba! Algoritmul tau este de o complexitate mai mare decat al meu! Pentru MAX_SWAP = NR_MAX, si pentru cateva generari consecutive, imi poti tu garanta ca rezultatele returnate de al meu nu pot fi, la un moment dat, identice cu al tau (sau ala de mai sus, sau cei folositi de NASA)? Sunt numere aleatoare (pseudo)!!! Nu vorbim aici de generarea unui SINGUR numar aleator (da, sunt mai multe metode, etc), vorbim de generarea unei MULTIMI de numere aleatoare unice. Ruleaza de 50 de ori pe al meu, de 50 de ori pe al tau si de 50 de ori pe ala in VB. Crezi ca o sa vezi ceva in neregula? Vei vedea 50 de multimi de numere unice intr-o ordine aleatoare! Al meu este cel mai rapid dintre toate (exceptand faza initializarii), de complexitate n, al tau este de complexitate n^2, ala din VB fiind muuuult mai mare.

Eu am simulat aici un caz real: tiganul din Obor care invarte discurile de cauciuc de la "alba-neagra": ia un disc, si il pune in locul altuia: este o metoda perfecta si suficienta de amestecare!

Evident, algoritmul meu se poate imbunatati, macar in prima faza, la initializarea vectorului V (descrescator, prima jumatate cu numere pare, a doua jumatate cu numere impare, etc, etc), dar n-are nici un sens! Pentru MAX_SWAP = NR_MAX merge de bubuie!

----------------
{1, 2, 3, 4, 5, 6} -> {1, 2, 4, 3, 6, 5} ai obtinut o permutare aleatorie?
Evident! Si {1, 2, 3, 4, 5, 6} reprezinta o permutare aleatorie, nu crezi?
Daca bagi intr-o caciula 5 bile colorate intr-o anumita ordine, le agiti bine, si incepi sa le scoti, bagi tu mana in foc ca intotdeauna le vei extrage intr-o ordine diferita fata de cum le-ai introdus?

Africanul, on Sep 28 2005, 08:27, said:

eu iti garantez ca daca rulezi algoritmul tau pentru 10.000 de elemente, de oricate ori vrei, cu SWAP_MAX = NR_MAX = 10000, vei gasi de fiecare data in ultimele 20 de elemente ale multimii generate cel putin 2-3 care sa fie pe locurile lor fara sa fie deloc swapate. chiar si pentru puzzle-ul lui fabby, unde probabil n = 9 sau ceva de genul asta, vor fi suficiente cazuri cand o sa-i ramana piesele pe loc, ceea ce nu e foarte placut. daca creste SWAP_MAX undeva pe la 3-5xNR_MAX, atuncea pare mai normala permutarea obtinuta.

Elementele sunt intr-o ordine aleatoare, e adevarat, la fel cum si 1,2,3,4.... sunt intr-o ordine aleatoare, insa dupa parerea mea, ideea e nu sa obtii o permutare intre atatea altele (ai putea foarte bine sa iei doua elemente si sa le schimbi intre ele si sa zici: "uite, asta e o permutare aleatoare obtinuta din prima"), ci sa obtii o permutare in care elementele sa fie aleator amestecate/asezate fata de permutarea initiala. din acest punct de vedere, indiferent cum faci tu initializarea vectorului, tot acolo ajungi -  daca elemetele se numesc 1, 2, 3... 10 sau 10, 9, ... 1, nu are nici o importanta. permutarea nu tine de cum se numesc elementele respective, ci de ordinea /dezordinea in care sunt, relativ la permutarea initiala.

Africanul, on Sep 28 2005, 08:27, said:

evident, aici ai dreptate.

Africanul, on Sep 28 2005, 08:27, said:

v. mai sus. incearca cu 10.000 sa vezi cum bubuie . Nu cred ca NASA foloseste astfel de generatoare de pemutari (in caz ca are nevoie).

Africanul, on Sep 28 2005, 08:27, said:

nu. dar probabilitatea sa le scot (macar partial) in aceeasi ordine in care le-am bagat este "infinit" mai mica decat in cazul in algoritmului tau. cu siguranta. cel putin pentru numere mai mari (cam de pe la 20-30 in sus algoritmul tau da rateuri - repet, cand alea doua sunt egale)

@sapho: da-i drumul si testeaza-l pentru cate numere vrei tu! Ca sa dorm eu linistit, pune SWAP_MAX = 2*NR_MAX (creste complexitatea la 2*n care este in continuare mai mica decat n*n, pt. n>2).
Toti cei 3 algoritmi sunt buni, si cel mai bun este primul (ala in VB), dar este cel mai lent.

Apropo, folosind stl-ul, complexitatea la al tau este mult mai mare decat n^2!!! Ia sa-l scrii in C, sa simulezi ce face stl-ul in burta lui... O sa te sperii!
Regula: cand descrii un algoritm, nu folosesti in el STL sau alte "tooluri" sau "facilitati" de limbaj de genul asta, il scrii cat mai "primitiv", in felul asta vezi exact despre ce-i vorba cu el.

Edited by Africanul, 28 September 2005 - 09:44.

Daca ai folosi C++ ai o functie de biblioteca cu complexitate liniara, mai precis :

Quote

din stl shuffle



Poti sa mai citesti pe acolo si eventual sa te uiti intr-o implementare de stl (asta daca stii c++)