Share
Soms heb je een aantal items - dit kunnen snaren zijn, getallen zijn, objecten zijn, wat dan ook - waarvan je de volgorde wilt randomiseren. Dit is vooral handig voor quizzen en kansspelen, maar is handig in allerlei andere toepassingen. De eenvoudigste methode die ik hiervoor heb gevonden, is om alle items in een array te plakken en deze vervolgens als een stapel kaarten te schudden. Maar hoe kunnen we dat doen? ?
Als een eenvoudig voorbeeld gebruiken we de letters van het alfabet:
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 "];
Er zijn verschillende benaderingen die we kunnen gebruiken om deze array daadwerkelijk te sorteren.
We zouden een tweede array kunnen maken en elk element van de eerste in een willekeurige positie in de tweede kunnen kopiëren:
De code hiervoor kan er als volgt uitzien (zie deze Snelle tip voor het verkrijgen van een willekeurig geheel getal binnen een specifiek bereik voor meer details):
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 "]; var shuffledLetters: Array = new Array (letters.length); var randomPos: int = 0; for (var i: int = 0; i < letters.length; i++) randomPos = int(Math.random() * letters.length); shuffledLetters[randomPos] = letters[i];
Maar er is een enorm probleem. Wat als de willekeurige positie wordt gekozen voor C is ook 6?
Hier, EEN wordt overschreven en zal daarom niet in de geschudde array staan. Dat is niet wat we willen, dus we moeten controleren of de sleuf leeg is voordat de brief wordt gekopieerd en kies een andere sleuf als dit niet het geval is:
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 "]; var shuffledLetters: Array = new Array (letters.length); var randomPos: int = 0; for (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];
Dat werkt. Het probleem is dat het inefficiënt is. Kijk, de brief EEN past gegarandeerd in de gekozen sleuf, omdat het de eerste gekozen letter is, dus alle slots zijn leeg. Met B, er is een kans van 25 in 26 dat het eerste gekozen slot leeg zal zijn. Als we halverwege het alfabet zijn, daalt deze kans naar 50/50. Tegen de tijd dat we het bereiken V, er is een 50/50 kans dat we geen lege slot vinden tot de vierde poging.
Dit betekent dat we waarschijnlijk bellen Math.random () wayyyyy meer dan 26 keer. En Math.random () is een relatief trage functie. Wat is een andere benadering die we kunnen volgen??
Wat als we een lijst met alle lege slots in a hebben opgeslagen? derde array, die zou krimpen als we door ze gingen?
? en zo verder, herhalen totdat de reeks lege slots geen elementen bevat. De code daarvoor zou er als volgt uitzien:
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 "]; var shuffledLetters: Array = new Array (letters.length); var emptySlots: Array = new Array (); voor (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);
Hier gebruiken we de methode Array.splice () om een enkel element uit de lijst met lege slots te verwijderen. Hiermee wordt het element verwijderd, in plaats van alleen de waarde ervan in te stellen nul; dus, na het splitsen van de eerste gleuf, emptySlots.length zal zijn 25 liever dan 26.
Deze splice () de functie is geweldig; we kunnen het gebruiken voor een derde benadering van schuifelen waardoor deze middelhoge matrix wordt uitgeschakeld.
In plaats van elementen uit de reeks lege slots te verwijderen wanneer we klaar zijn met deze, kunnen we ze uit de oorspronkelijke, niet-gekoppelde array verwijderen.
Dit klinkt in eerste instantie niet erg handig, maar wat als we elementen uit de origineel array willekeurig, in plaats van het kiezen van hun bestemmingen willekeurig?
? en zo verder, totdat de eerste array geen elementen bevat.
In tegenstelling tot de andere twee benaderingen, eindigen we zonder de oorspronkelijke array. Of dit een probleem is of niet hangt af van dit project.
De code kan er als volgt uitzien:
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 "]; var shuffledLetters: Array = new Array (letters.length); var randomPos: Number = 0; for (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);
In feite sindsdien splice () retourneert een reeks van alle elementen die u aan het splitsen bent, kunnen we de code een beetje vereenvoudigen:<
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 "]; var shuffledLetters: Array = new Array (letters.length); var randomPos: Number = 0; for (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
Dat is netter. Ik heb nog een benadering om te delen; deze is heel anders dan de andere die we tot nu toe hebben gebruikt.
Arrays hebben een methode, sort (), die standaard alle elementen van de array in oplopende alfanumerieke volgorde rangschikt, zoals:
var mixedLetters: Array = ["G", "B", "P", "M", "F"]; mixedLetters.sort (); // mixedLetters is nu ["B", "F", "G", "M", "P"]
U kunt opties doorgeven aan deze methode, zoals Array.DESCENDING, die de volgorde van het soort omkeert:
var mixedLetters: Array = ["G", "B", "P", "M", "F"]; mixedLetters.sort (Array.DESCENDING); // mixedLetters is nu ["P", "M", "G", "F", "B"]
(Er zijn andere opties, en je kunt er zoveel als je wilt geven.)
U kunt ook een verwijzing naar een doorgeven functie, die Flash vertelt hoe te beslissen in welke volgorde twee items horen. Deze functie kan bijvoorbeeld worden gebruikt voor numerieke sortering:
function numericalSort (a: Number, b: Number): Number if (a < b) return -1; if (a == b) return 0; if (a > b) terugkeer 1;
Flash kijkt naar elk paar aangrenzende items in de array en rangschikt ze volgens deze functie: het wisselt ze in als de waarde 1 wordt teruggestuurd en laat ze anders alleen. (Tenzij je slaagt Array.DESCENDING evenals de functie, in welk geval het ze uitwisselt als de waarde -1 wordt geretourneerd en laat ze anders alleen.) Flash herhaalt dit over de hele array, steeds opnieuw totdat alle paren terugkeren 0 of -1 (0 of 1 bij gebruik Array.DESCENDING).
We kunnen hiermee rotzooien. In plaats van het een echte reden te geven waarom twee elementen moeten worden geruild, kunnen we het gewoon vertellen om ze willekeurig te verwisselen met behulp van een sorteerfunctie als deze:
functie randomSort (a: *, b: *): Number // * betekent elke soort input if (Math.random () < 0.5) return -1; else return 1;
Gemakkelijk! Nu kunnen we het in onze code gebruiken zoals:
functie randomSort (a: *, b: *): Number 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)
Houd er rekening mee dat de resulterende array niet zo willekeurig zal worden geschud als de andere benaderingen die we hebben gebruikt - in deze benadering is er geen kans op een 1/26 kans dat ieder een gegeven letter komt binnen ieder gegeven slot. Dit komt omdat we alleen aangrenzende paren elementen verwisselen en niet meer doen dan dat. Toch is het een leuke methode :)
Er zijn tal van andere methoden, ik weet het. Ik heb er een die je leuker vindt dan deze?
Bewerk: Hier is een geweldige post met een aantal zeer coole visualisaties, die de Fisher-Yates shuffle uitleggen, die op zijn plaats werkt. ik raad het ten sterkste aan!
Accentsconagua