random numere

Vezi edit-ul de la postul unde am bagat cele 20 de generari.
Ce ai bolduit tu era evident, si doar uitandu-te pe cod iti dadeai seama ca exista posibilitatea ca niste elemente sa "ramana pe loc" (sau sa fie aduse la locul lor).
Niciodata n-am afirmat ca algoritmul meu va scoate "permutari perfecte", ci doar permutari! Am respectat definitia permutarii din matematica. Am afirmat ca algoritmul postat de mine returneaza niste rezultate suficient de bune. Nu-i mare branza sa faci un algoritm care sa genereze "permutari perfecte" aleatorii...

Nu exista "permutari perfecte", doar permutari.

Ia un pachet de carti, initial puse in ordine crescatoare, dupa tip (trefla, etc). Amesteca-le jumate de zi. Vei obtine intotdeauna o "permutare perfecta"? Eu n-as baga mana in foc...

Edited by Africanul, 29 September 2005 - 09:58.

exemplu (cu programul facut de mine ) :

8 6 7 1 9 3 2 5 0 4
5 1 9 3 0 8 6 4 7 2
1 4 0 6 2 5 9 7 3 8
7 3 5 1 0 8 9 6 4 2
3 8 6 4 1 0 2 9 5 7
0 2 8 5 3 6 4 1 9 7
6 4 9 7 2 8 3 1 0 5
3 9 0 7 4 2 1 8 6 5
0 3 4 9 6 7 2 8 1 5
6 7 3 0 4 1 8 2 9 5
3 1 6 2 8 0 9 4 5 7
9 3 6 2 5 4 0 7 8 1
6 8 7 3 9 5 1 2 0 4
2 1 9 6 7 3 5 8 4 0
9 5 0 7 1 6 8 4 2 3
5 0 3 9 8 1 2 4 7 6
2 3 5 9 0 6 4 1 7 8
9 6 4 1 0 8 7 3 5 2
5 1 7 3 2 4 0 8 6 9
2 5 8 3 1 7 4 9 6 0

cu ocazia astra am descoperit inca o problema la algoritmul tau: (pt n = 10) e foarte greu sa obtii permutari care au mai mult de 2 elemente in comun cu cea initiala.

sapho, on Sep 29 2005, 11:02, said:

Posibil! Si care-i problema? "Demonstratia" am facut-o mai sus cu cateva posturi.
Nu a fost vorba niciodata in thread-ul asta sa se genereze "permutari perfecte", doar permutari. Omul ala vroia sa stie cum se "amesteca" o multime...
Iar citatele pe care mi le dai, n-au nici o valoare pentru mine. Serios! Am scos "niste" permutari cu algoritmul meu, intr-un mod foarte simplu si nepretentios.

Ai verificat algoritmul lui Knuth? Poti baga un listing cu 20 de generari?

Edited by Africanul, 29 September 2005 - 10:29.

Africanul, on Sep 29 2005, 09:53, said:

ia fa unu-doua, dar nu implementari ale algoritmului lui Knuth, si nici celalalt descris de mine mai sus (ala care porneste de la un singur element, la care tot adaugi cate inca unul, in pozitii aleatoare), sa vedem . si sa respecte cerinta aia cu probabilitatea de 1/ N!.

Quote

eu ma gandeam ca de vreo 20 posturi (de cand omul a zis ca si-a rezolvat problema) tot despre asta discutam... am si recunoscut la un moment dat, ca pentru ce are el nevoie e suficient algoritmul tau. da cred ca tu ai zis ceva de NASA si cu ce ar fi algoritmii alora mai buni decat al tau .

Africanul, on Sep 29 2005, 10:12, said:

pai ti-am zis ca programul meu respeta intocmai algoritmul lui Knuth. numai ca e implementat aiurea (adica prea costisitor din punct de vedere al resurselor) . in rest (pasii si ce se intampla in fiecare pas) sunt exact la fel.

Edited by sapho, 29 September 2005 - 10:38.

    

Imagineaza-ti ca daca vroiam sa postez un algoritm care genereaza "permutari perfecte", nu veneam cu jucaria pe care am postat-o! Oricine care stie minimul de C si minimul de matematica si-ar fi dat instantaneu seama ca jucaria nu are cum sa scoata la fiecare executie o "permutare perfecta" (doar intamplator!). El asigura in schimb "o permutare corecta" a multimii initiale, doar atat.
Ce m-a "ofticat" a fost ca ai sarit repede cu gura ca "nu e bun": este de-a dreptul infiorator de bun! Tu ai fost cel care ai introdus ideea de "permutare perfecta"...

Oricum, te felicit sincer ca te-ai implicat cu atata ardoare in acest subiect (fara nici un misto!), si ai pastrat un limbaj civilizat (nu ca "altii")... Intr-adevar este bun pentru "exercitiu" din cand in cand sa-ti mai bati capul cu probleme de genul asta. Pacat ca in ceea ce ma priveste, nu prea mai am timp disponibil Inainte acceptam mai usor "dueluri" de genul asta...

Pace!

Edited by Africanul, 29 September 2005 - 10:55.

ok. (desi imi pare ca te eschivezi de la a da un algoritm de-asta de permutari perfecte ).

vezi ca mai dadusem unul (asta citit pe undeva pe net):

sapho, on Sep 29 2005, 00:06, said:

putem continua eventual discutia despre faptul ca cei care au implementat STL pt gcc au gresit. m-am uitat si in <algorithm> din implementarea VisualC++, si e tot asa aiurea facuta.

sapho, on Sep 29 2005, 11:54, said:

Nu ma eschivez, serios. Chiar am in cap niste "posibile" solutii (trebuie verificate, iti dai seama). Dar nu prea am timp disponibil sa ma apuc de o chestie de genul asta acum...
Poti s-o consideri eschivare, nu ma deranjeaza!  
Poate "preia" altcineva continuarea discutiei pe tema asta: este ceva interesant.

Iar despre STL nu stiu o boaba! N-am folosit in viata mea. Stilul meu de programare este unul mai "antic", mai aproape de assembler (de exemplu). Mai masochist! Si intamplator (sau nu) si la firmele unde am lucrat/lucrez tot asa am continuat sa lucrez. Am lucrat si pe PC dar si pe alte deviceuri foarte limitate in resurse, unde a trebuit sa fac tot felul de optimizari de ce vrei tu, iar existenta unui STL ar fi fost mana cereasca! Prefer C-ul batranesc, bun la toate.
Sunt "batran" si inapoiat, stiu.

Edited by Africanul, 29 September 2005 - 11:07.

mama ce discutie. Dupa parerea mea va certati de pomana. E clar ca algoritmul scris de Africanul e mai rapid cum e clar ca si cel scris de sapho e mai bun. De ce nu incercati sa ajungeti la o intelgere, oricum toata discutia e off topic

Riper, on Sep 29 2005, 11:15, said:

la fel cum e clar ca algoritmul lui Knuth e cel mai rapid si cel mai bun

iata implementarea lui ca sa fie si mai clar:

#include <cstdlib>
#include <iostream>
#include <cstdio>
#include <ctime>

using namespace std;

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

    const int sz = 10;             // numarul de elemente
    const int repetari = 10;       // nr de repetari ele generarii
    
    int v[sz];                     // solutia
    int temp1, temp2;              // numere ajutatoare
     
    for (int j = 0; j < repetari; j++) {
        for (int i = 0; i < sz; ++i) v[i] = i; 

        for (int i = 0; i < sz; ++i) { 
            temp2 = i + rand() % (sz - i);   // alegem un element la intamplare din cele ramase
            
            temp1 = v[i];                    // swapping
            v[i] = v[temp2];
            v[temp2] = temp1;
            
            cout << v[i] << "\t";            // afisare
            if ((i + 1) % 10 == 0) cout << endl;
        }
        cout << endl;
    }
    
    system("PAUSE");
    return EXIT_SUCCESS;
}

sapho, on Sep 29 2005, 14:53, said:

N-as fi asa de sigur...
Am copiat EXACT codul de mai sus, asta al lui Knuth, si i-am dat pt. 20 de generari.
Acum, ori Knuth este si el om, ori ai implementat tu gresit algoritmul, ori nu sunt  eu in stare de un copy-paste... Tu l-ai verificat?
Uite ce a iesit:

0 1 2 3 4 5 6 7 8 9 - Multimea initiala

1 9 8 2 0 4 3 7 6 5
5 3 1 9 0 6 2 4 7 8
1 7 8 9 2 0 5 3 4 6
7 1 5 2 0 4 9 8 6 3
3 7 4 5 1 9 2 8 0 6
7 6 8 0 3 9 5 4 1 2
6 3 8 4 1 0 5 9 2 7
6 1 4 5 8 3 2 7 9 0
9 6 1 7 4 5 8 0 3 2
4 0 1 7 9 8 5 3 2 6
3 0 9 2 4 5 7 1 6 8
1 9 6 7 4 0 3 2 5 8
6 7 3 5 9 1 4 8 0 2
0 8 7 6 1 5 9 3 2 4
7 3 1 5 9 4 0 2 6 8
2 8 4 6 7 1 3 9 5 0
0 6 2 9 1 8 3 7 5 4
1 3 8 5 4 6 0 7 2 9    <-- wow, tare Knuth asta...
1 0 7 2 4 8 6 9 3 5
8 0 2 9 3 6 1 4 7 5

Probabil ca mai sunt si alte numere, oricum nu mai conteaza.
Oare difera asta cu ceva fata de al meu?

Edited by Africanul, 29 September 2005 - 14:58.

din pacate ma pricep prea putin la probabilitati ca sa iti demonstrez ca aparitia unei permutari in care 3 elemente (oarecare) apar pe aceleasi pozitii ca in permutarea initiala, aceasta probabilitate deci este destul de mare. ti-am spus si mai sus ca una din hibele algoritmului tau este ca nu genereaza decat foarte rar astfel de permutari.

sigur pot sa-ti zic numai atat: ca probabilitatea ca un element sa apara pe aceeasi pozitie este de 1/n (adica, de exemplu, din cele n! permutari posibile, primul element apare de (n-1)! pe prima pozitie). ca sa te convingi de chestia asta ruleaza asa:

#include <cstdlib>
#include <iostream>
#include <cstdio>
#include <ctime>

using namespace std;

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

    const int sz = 10;             // numarul de elemente
    const int repetari = 50000;       // nr de repetari ele generarii
    
    int v[repetari][sz];                     // solutiile
    int temp1, temp2;              // nr ajutatoare
    
    srand (time(0));
     
    for (int j = 0; j < repetari; j++) {
        for (int i = 0; i < sz; ++i) v[j][i] = i; 

        for (int i = 0; i < sz; ++i) { 
            temp2 = i + rand() % (sz - i);   // alegem un element la intamplare din cele ramase
            
            temp1 = v[j][i];                    //swapping
            v[j][i] = v[j][temp2];
            v[j][temp2] = temp1;
            
            //cout << v[j][i] << " ";            // afisare
            //if ((i + 1) % 10 == 0) cout << endl;
        }
        //cout << endl;
    }
    
    
    cout << endl;
    int a[sz];                        // masoara de cate ori un element apare tot pe pozitia sa initiala
    int suma = 0;                 // suma tuturor aparitiilor pe aceeasi pozitie, pentru toate elementele
    for (int i = 0; i < sz; ++i) a[i] = 0;
    for (int j = 0; j < repetari; ++j) {
        for (int i = 0; i < sz; ++i) 
            if (v[j][i] == i) ++a[i];
    }
    for (int i = 0; i < sz; ++i) {
        cout << i << " = " << a[i] << "\n";
        suma += a[i];
    }
    cout << "suma = " << suma << "\n";
   
    system("PAUSE");
    return EXIT_SUCCESS;
}

vei vedea ca algoritmul genereaza, in mare, cam asa ceva (rulare de 50.000 ori):

0 = 5050
1 = 5016
2 = 5032
3 = 4964
4 = 5043
5 = 4988
6 = 5043
7 = 5060
8 = 4998
9 = 4956
suma = 50150

dupa parerea mea, distributia nu e nici asa suficient de uniforma, insa mai mult nu cred ca se poate cere de la functia rand() (ea e de vina, nu algoritmul).

aplicat la algoritmul tau, ca sa vezi cam care e diferenta (tot rulare de 50.000 ori):

cu MAX_SWAP = NR_MAX = 10:

0 = 8683
1 = 8757
2 = 8695
3 = 8669
4 = 8771
5 = 8640
6 = 8770
7 = 8710
8 = 8500
9 = 8643
suma = 86838

cu MAX_SWAP = 2*NR_MAX = 20:

0 = 5278
1 = 5435
2 = 5345
3 = 5239
4 = 5290
5 = 5310
6 = 5368
7 = 5342
8 = 5310
9 = 5349
suma = 53266

cu MAX_SWAP = 3*NR_MAX = 30:

0 = 5160
1 = 4948
2 = 4958
3 = 4903
4 = 5066
5 = 5039
6 = 5058
7 = 4993
8 = 5087
9 = 5025
suma = 50237

dupa cum vezi, cand NR_MAX = 10 si MAX_SWAP = 30, algoritmul tau se apropie de ceea ce ar trebui sa fie. la numar mai mare de elemente, trebuie sa ai MAX_SWAP si mai mare.

Da, probabil ca ai dreptate, nu stau sa verific. Algoritmul care l-am dat eu este o jucarie, nu-ti bate capul cu el!
Oricum, nu uita ca functia rand() este limitata pe intervalul [0..n) (chestia cu %), ea returneaza numere "suficient de aleatorii" pe un interval "suficient de mare", doar ca este gatuita de acel modulo, iar pe un interval mic (cum era asta 0..9) incepe sa se simta "gatuirea"...

mi-am modificat programul ca sa masoare de cate ori apare o permutare in care k numere se gasesc pe pozitiile lor initiale. outputul se citeste cam asa:
0 (nici un element nu se regaseste pe pozitia sa initiala) = nr de astfel de permutari
1 (un singur element pe pozitia sa) = ......
10 (toate elementele se gasesc pe pozitiile initiale - permutarea identica cred ca se numea in matematica)

rezultatul (rulare de 10.000 ori):

b[0] = 3705
b[1] = 3724
b[2] = 1802
b[3] = 574
b[4] = 161
b[5] = 30
b[6] = 4
b[7] = 0
b[8] = 0
b[9] = 0
b[10] = 0

concluzii:
1. numarul de permutari in care niciunul din numere nu e pe pozita initiala am impresia ca e egal cu, sau mai mic decat numarul de permutari in care se "repeta" un singur element.

2. numarul de permutari cu 3 "repetari" reprezinta cam 6% din numarul total de permutari. deci din cele 20 de permutari (cat avea listingul tau) e foarte probabil una sa fie de acest tip.

Edited by sapho, 29 September 2005 - 18:50.

am si eu o problema..iar  
vreau sa fac un program in care eu sa introduc niste nume(in textbox) si care sa imi repartizeze pe acestia in mai multe grupe
Si sa arate asa
Nume1 =TEXTBOX -------------Grupa A, TEXTBOX(in text box sa-mi afiseze 4 nume la nimereala diferite)
Nume2 =Textbox --------------Grupa B, TextBOX(4 nume din cele ramase,diferite)
...  ------------------------------- Grupa C-etc
Nume16=TEXTBOX -------------Grupa D-etc

si altul Care din 16 ekipe participante sa aleaga una pt fiecare grupa
ekipa1=(TEXTBOX ----------------Grupa A, TextBOX(Una din cele 16 ekipe)
ekipa2= TExtBox  ----------------- Grupa B, TExtBox(una din cele 15 ramase)
...  ----------------------------------- Grupa C,TextBox(una din 14 ramase)
ekipa16=TExtBox -------------------Grupa D, TextBox(una din cele 13)-si restul sa ramana neafisate
Ma poate ajuta cineva?

Edited by mosu16, 14 April 2006 - 16:03.