Share
Uneori aveți un set de elemente - ar putea fi șiruri, ar putea fi numere, ar putea fi obiecte, orice - ale căror ordini doriți să le faceți aleatoriu. Acest lucru este deosebit de util pentru quiz-uri și jocuri de noroc, dar vine la îndemână în tot felul de alte aplicații. Cea mai ușoară metodă pe care am găsit-o pentru a face acest lucru este de a lipi toate elementele dintr-o matrice și apoi de ao amesteca ca un pachet de cărți. Dar cum putem face asta?? ?
Ca un exemplu simplu, vom folosi literele alfabetului:
literele var: Array = ["A", "B", "C", "D", "E", "F", "G", "H", "I", "J" "L", "M", "N", "O", "P", "Q", "R", "S", "T", " "," Y "," Z "];
Există diferite abordări pe care le putem lua pentru a sorta această matrice.
Am putea crea o a doua matrice și să copiem fiecare element al primei într-o poziție aleatorie în al doilea:
Codul pentru care ar putea arăta astfel (consultați acest sfat rapid pentru a obține un număr întreg aleatoriu într-o anumită gamă pentru mai multe detalii):
literele var: Array = ["A", "B", "C", "D", "E", "F", "G", "H", "I", "J" "L", "M", "N", "O", "P", "Q", "R", "S", "T", " "," Y "," Z "]; var shuffledLetters: Array = Array nou (letters.length); var randomPos: int = 0; pentru (var i: int = 0; i < letters.length; i++) randomPos = int(Math.random() * letters.length); shuffledLetters[randomPos] = letters[i];
Dar există o mare problemă. Ce se întâmplă dacă poziția aleatoare a fost aleasă? C este de 6, de asemenea?
Aici, A va fi suprascris și, prin urmare, nu va fi în matricea amestecată. Nu este ceea ce dorim, deci trebuie să verificăm dacă slotul este gol înainte de a copia scrisoarea și să alegeți un slot diferit dacă nu este:
literele var: Array = ["A", "B", "C", "D", "E", "F", "G", "H", "I", "J" "L", "M", "N", "O", "P", "Q", "R", "S", "T", " "," Y "," Z "]; var shuffledLetters: Array = Array nou (letters.length); var randomPos: int = 0; pentru (var i: int = 0; i < letters.length; i++) randomPos = int(Math.random() * letters.length); while (shuffledLetters[randomPos] != null) //repeat as long as the slot is not empty randomPos = int(Math.random() * letters.length); //pick a different slot shuffledLetters[randomPos] = letters[i];
Asta merge. Problema este că este ineficientă. Vezi, scrisoarea A este garantat să se încadreze în slotul ales, deoarece este prima literă aleasă, astfel încât toate sloturile vor fi goale. Cu B, există o șansă de 25 la 26, că primul slot ales va fi gol. Când suntem la jumătatea drumului prin alfabet, această șansă scade la 50/50. Când ajungem V, există o șansă de 50/50 că nu vom găsi un slot gol până la Al patrulea atentat, încercare.
Asta înseamnă că suntem foarte probabil să sunăm Math.random () wayyyyy mai mult de 26 de ori. Și Math.random () este o funcție relativ lentă. Care este o altă abordare pe care o putem lua?
Dacă am stocat o listă a tuturor sloturilor goale într-un al treilea array, care s-ar micsora când am trecut prin ele?
? și așa mai departe, repetând până când gama de sloturi goale nu conține elemente. Codul pentru care ar arăta astfel:
literele var: Array = ["A", "B", "C", "D", "E", "F", "G", "H", "I", "J" "L", "M", "N", "O", "P", "Q", "R", "S", "T", " "," Y "," Z "]; var shuffledLetters: Array = Array nou (letters.length); var emptySloturi: Array = Array nou (); pentru (var n: int = 0; n < letters.length; n++) emptySlots.push(n); var randomPos:Number = 0; var actualSlot:Number = 0; for (var i:int = 0; i < letters.length; i++) randomPos = int(Math.random() * emptySlots.length); //note emptySlots.length not letters.length actualSlot = emptySlots[randomPos]; shuffledLetters[actualSlot] = letters[i]; emptySlots.splice(randomPos, 1);
Aici folosim metoda Array.splice () pentru a elimina un singur element din lista de sloturi goale. Acest lucru elimină de fapt elementul, mai degrabă decât să-i setați valoarea nul; astfel încât, după splicarea primului slot, emptySlots.length va fi 25 Decat 26.
Acest lipitură() funcția este mare; îl putem folosi pentru oa treia abordare a amestecării care elimină această gamă de mijloc.
În loc să eliminăm elemente din gama de sloturi goale atunci când le-am terminat cu ele, le-am putea elimina din matricea originală, nesimpusă.
Acest lucru nu pare foarte util la început - dar dacă am ales elemente din original array la întâmplare, în loc de a le alege destinații la intamplare?
? și așa mai departe, până când prima matrice nu conține elemente.
Spre deosebire de celelalte două abordări, ajungem fără matricea originală. Indiferent dacă aceasta este o problemă sau nu, depinde de acest proiect.
Codul ar putea arăta astfel:
literele var: Array = ["A", "B", "C", "D", "E", "F", "G", "H", "I", "J" "L", "M", "N", "O", "P", "Q", "R", "S", "T", " "," Y "," Z "]; var shuffledLetters: Array = Array nou (letters.length); var randomPos: Număr = 0; pentru (var i: int = 0; i < shuffledLetters.length; i++) //use shuffledLetters.length because splice() will change letters.length randomPos = int(Math.random() * letters.length); shuffledLetters[i] = letters[randomPos]; //note this the other way around to the naive approach letters.splice(randomPos, 1);
De fapt, din moment ce lipitură() returnează un mulțime din toate elementele pe care le îmbinați, am putea simplifica puțin codul:<
literele var: Array = ["A", "B", "C", "D", "E", "F", "G", "H", "I", "J" "L", "M", "N", "O", "P", "Q", "R", "S", "T", " "," Y "," Z "]; var shuffledLetters: Array = Array nou (letters.length); var randomPos: Număr = 0; pentru (var i: int = 0; i < shuffledLetters.length; i++) randomPos = int(Math.random() * letters.length); shuffledLetters[i] = letters.splice(randomPos, 1)[0]; //since splice() returns an Array, we have to specify that we want the first (only) element
E mai bine. Am o altă abordare de împărțit; aceasta este foarte diferită de celelalte pe care le-am folosit până acum.
Arrays are o metodă, sort (), care în mod prestabilit rearanjează toate elementele matricei într-o ordine alfanumerică ascendentă, după cum urmează:
var amestecatLetre: Array = ["G", "B", "P", "M", "F"]; mixedLetters.sort (); // MixedLetters este acum ["B", "F", "G", "M", "P"]
Puteți trece opțiuni la această metodă, cum ar fi Array.DESCENDING, care inversează ordinea de genul:
var amestecatLetre: Array = ["G", "B", "P", "M", "F"]; mixedLetters.sort (Array.DESCENDING); // MixedLetters este acum ["P", "M", "G", "F", "B"]
(Există și alte opțiuni și puteți trece cât de multe dintre ele doriți.)
De asemenea, puteți trece o referință la o funcţie, care spune Flash cum să decidă în ce ordine apar două elemente. De exemplu, această funcție ar putea fi utilizată pentru sortarea numerică:
funcția numericăSort (a: Număr, b: Număr): Număr if (a < b) return -1; if (a == b) return 0; if (a > b) retur 1;
Flash examinează fiecare pereche de elemente adiacente din matrice și le rearanjează în funcție de această funcție: le schimbă dacă valoarea 1 este returnat și le lasă în pace altfel. (Dacă nu treceți Array.DESCENDING precum și funcția, caz în care le schimbă dacă valoarea -1 este returnat și le lasă în pace altfel.) Flash-ul repetă acest lucru în întreaga matrice de peste și peste până când toate perechile se întorc 0 sau -1 (0 sau 1 dacă utilizați Array.DESCENDING).
Putem să ne grăbim cu asta. În loc să-i oferim un motiv real pentru înlocuirea oricăror două elemente, putem să-i spunem să le schimbe la întâmplare, folosind o funcție de sortare similară:
Funcția randomSort (a: *, b: *): Număr // * înseamnă orice tip de intrare if (Math.random () < 0.5) return -1; else return 1;
Uşor! Acum îl putem folosi în codul nostru, astfel:
funcția randomSort (a: *, b: *): Număr if (Math.random () < 0.5) return -1; else return 1; var letters:Array = ["A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K", "L", "M", "N", "O", "P", "Q", "R", "S", "T", "U", "V", "W", "X", "Y", "Z"]; letters.sort(randomSort); //(no need for the shuffledLetters[] Array)
Rețineți că matricea rezultată nu va fi la fel de aleatoriu ca celelalte abordări pe care le-am utilizat - în această abordare, nu există o șansă egală de 1/26 care să orice scrisoarea dată se va termina în orice slot dat. Acest lucru se datorează faptului că schimbăm doar perechi de elemente adiacente și nu facem mai mult decât atât. Totuși, este o metodă îngrijită :)
Există o mulțime de alte metode, știu. Aveți orice vă place mai bine decât acestea?
Editați | ×: Iată un post minunat, cu niște vizualizări foarte interesante, care explică amestecul Fisher-Yates, care funcționează la locul lui. Îmi recomand foarte mult!
Accentsconagua