{"id":726,"date":"2016-09-22T11:26:38","date_gmt":"2016-09-22T09:26:38","guid":{"rendered":"https:\/\/www.bartbarnard.nl\/blog\/?p=726"},"modified":"2016-10-24T11:53:44","modified_gmt":"2016-10-24T09:53:44","slug":"randomizeren-van-arrays-in-javascript","status":"publish","type":"post","link":"https:\/\/www.bartbarnard.nl\/blog\/randomizeren-van-arrays-in-javascript\/","title":{"rendered":"Randomizeren van arrays in JavaScript"},"content":{"rendered":"

Voor een project waar ik mee bezig ben wil ik, zonder gebruik te maken van een framework als jQuery<\/a> of Lodash<\/a>, een array randomiseren en daar vervolgens overheen itereren. Nu zijn er verschillende manieren om dit randomiseren te bewerkstelligen, maar ik vond online al vrij snel een algoritme dat een fatsoenlijke performance had, en daarbij de naam droeg van een oude computerheld<\/a>: dus dat maar gebruikt:<\/p>\n

\r\n\/\/ knuth array shuffle\r\n\/\/ from https:\/\/bost.ocks.org\/mike\/shuffle\/\r\nfunction shuffle(array) {\r\n  var currentIndex = array.length, temporaryValue, randomIndex;\r\n\r\n  \/\/ While there remain elements to shuffle...\r\n  while (0 !== currentIndex) {\r\n    \/\/ Pick a remaining element...\r\n    randomIndex = Math.floor(Math.random() * currentIndex);\r\n    currentIndex -= 1;\r\n\r\n    \/\/ And swap it with the current element.\r\n    temporaryValue = array[currentIndex];\r\n    array[currentIndex] = array[randomIndex];\r\n    array[randomIndex] = temporaryValue;\r\n  }\r\n\r\n  return array;\r\n}\r\n<\/pre>\n
Hoewel een string ook in Javascript feitelijk een array van karakters is, werkte de aanroep naar de bovenstaande functie met een String als actuele parameter niet in \u00e9\u00e9n keer. Dat verbaasde me, want<\/p>\n
\r\n$ node -e 'foo="ABC"; console.log(foo[2]);'\r\nC\r\n$\r\n<\/pre>\n
Maar gelukkig heeft JavaScript een goeie methode om een string om een specifieke array te maken van een array: split()<\/code>. Zo geeft \"A B C\".split(' ')<\/code> de array ['A','B','C']<\/code> terug. Het probleem hiermee was evenwel dat de string in kwestie niet gescheiden zou worden door een specifiek karakter: alle letters stonden eenvoudig achter elkaar. Nu zou je verwachten dan split()<\/code> dan zou werken, maar dat bleek niet het geval te zijn. Uiteindelijk bleek split('')<\/code> (dus met een lege string als parameter) het werk te doen:<\/p>\n
\r\n[test.js]\r\nvar foo = "BSDASCDASDFDAS".split('');\r\nconsole.log(foo)\r\nconsole.log(shuffle(foo));\r\n\r\n$ node test.js\r\n[ 'B', 'S', 'D', 'A', 'S', 'C', 'D', 'A', 'S', 'D', 'F', 'D', 'A', 'S' ]\r\n[ 'D', 'A', 'A', 'F', 'S', 'S', 'B', 'S', 'D', 'D', 'A', 'S', 'D', 'C' ]\r\n$\r\n<\/pre>\n
Met getallen en strings werkte deze methode prima. Maar toen ik het wilde gebruiken om een array van html-elementen door elkaar te gooien, ging het mis. Omdat ik geen JavaScript-framework kon gebruiken, moest terugvallen op de bekende ouderwetse methode van het selecteren van DOM-elementen. In dit specifieke geval had ik een tabel met zesendertig feitelijk identieke td’s: het enige verschil tussen deze elementen was hun positie in de tabel. Hierdoor kon de JavaScript-engine geen onderscheid maken tussen de gewone en de geshuffelde array:<\/p>\n
\r\nvar foo = document.getElementsByTagName('td');\r\nvar bar = shuffle(foo);\r\nconsole.log(foo==bar); \/\/true\r\n<\/pre>\n
Tijd om iets anders te bedenken. Omdat ik een situatie had waarin ik gegarandeerd elk element uit de array exact \u00e9\u00e9n keer moest langslopen, kon ik niet eenvoudig een ‘gerandomizede’ pointer naar de array gebruiken. Een mogelijke oplossing zou zijn om een willekeurige pointer te maken, dat element uit de array te halen en een nieuwe array te maken uit de elementen voor en de elementen na deze pointer \u2013 dus dat de nieuwe array telkens \u00e9\u00e9n element korter is dan de oorspronkelijke. In node leek dit een hoopvolle route, maar de browser bleek de methode slice()<\/code> niet te ondersteunen \u2013 die je nodig hebt om de oorspronkelijke array in stukjes te knippen.<\/p>\n
Wat nu wanneer we het element dat door de gerandomizede pointer wordt aangewezen null<\/code> maken en hierna over de array heen itereren en elk element dat niet null<\/code> is aan een nieuwe array toevoegen? Dit leek in ieder geval wel te werken voor eenvoudige strings:<\/p>\n
\r\nvar b = "BSDASCDASDFDAS";\r\nvar foo = b.split('');\r\n\r\nfoo[4] = null;\r\n\r\nvar bar=[];\r\nvar j=0;\r\n\r\nfor (var i=0; i<foo.length; i++) {\r\n  if (foo[i]!=null) {\r\n    bar[j]=foo[i];\r\n    j++;\r\n  }\r\n}\r\n\r\nconsole.log(foo); \/\/[ 'B', 'S', 'D', 'A', null, 'C', 'D', 'A', 'S', 'D', 'F', 'D', 'A', 'S' ]\r\nconsole.log(bar); \/\/[ 'B', 'S', 'D', 'A', 'C', 'D', 'A', 'S', 'D', 'F', 'D', 'A', 'S' ]\r\n<\/pre>\n
Op basis hiervan maakte ik een functie removeFromArray()<\/code> die een array als parameter krijgt een dezelfde array zonder null-values teruggeeft. Om dit goed te testen maakte ik een tabelletje met zes keer zes cellen die ik in eerste instantie oplopende kleuren gaf:<\/p>\n
\r\nvar colors = ["#f291fb", "#e279eb", "#d064da", "#db50c7", "#a93db3", "#932a9c", "#7a1c83", "#650e6d", "#4f0656", "#37023c", "#c06df4", "#aa56e0", "#9542c9", "#7f2eb2", "#661a96", "#4e0e76"];\r\n\r\nfunction init() {\r\n  var els = document.getElementsByTagName("td");\r\n  var e;\r\n  var j=0;\r\n\r\n  for (var i=0; i<els.length; i++) { e = els[i]; e.classList.value=""; e.bgColor=colors[j]; j>colors.length-1 ? j++ : j=0;\r\n  }\r\n}\r\n<\/pre>\n
\"Eerste<\/a>
Eerste test: opeenlopende kleuren.<\/p><\/div>\n
Nu is de uitdaging om niet lineair over de els-array te itereren, maar om dat te doen met een willekeurige pointer bij elke iteratie, en dat element via de hierboven beschreven methode uit de array te halen.<\/p>\n
\r\nfunction init() {\r\n  var els = document.getElementsByTagName("td");\r\n  var e;\r\n  var j=0;\r\n  var idx;\r\n\r\n  while (els.length) {\r\n    idx = Math.floor(Math.random() * els.length);\r\n\r\n    e = els[idx];\r\n    e.classList.value="";\r\n    e.bgColor=colors[j];\r\n\r\n    els[idx] = null;\r\n    els = removeFromArray(els);\r\n\r\n    j>colors.length-1 ? j++ : j=0;\r\n  }\r\n}\r\n<\/pre>\n
En dat levert inderdaad het gewenste resultaat op:<\/p>\n
\"Het<\/a>
Het gewenste resultaat. Het blijkt dat Javascript random door alle td’s heenloopt.<\/p><\/div>\n
Wat nog wel een beetje gedoe was, was dat document.getElementById()<\/code> geen array, maar een htmlCollection oplevert. Hierdoor werd dit pas na de eerste call naar removeFromArray()<\/code> een echte array. Dus ik moest die htmlCollection even expliciet omzetten naar een Array:<\/p>\n
\r\nvar els = [].slice.call(tdElements);\r\n<\/pre>\n
Wel een beetje raar dat ik daar pas achter kwam toen ik verder met het project ging \u2013 met die kleurtjes ging het goed. Soit.<\/p>\n","protected":false},"excerpt":{"rendered":"
Voor een project waar ik mee bezig ben wil ik, zonder gebruik te maken van een framework als jQuery of Lodash, een array randomiseren en daar vervolgens overheen itereren. Nu zijn er verschillende manieren om dit randomiseren te bewerkstelligen, maar ik vond online al vrij snel een algoritme dat een fatsoenlijke performance had, en daarbij<\/p>\n
Read More<\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[19],"tags":[],"_links":{"self":[{"href":"https:\/\/www.bartbarnard.nl\/blog\/wp-json\/wp\/v2\/posts\/726"}],"collection":[{"href":"https:\/\/www.bartbarnard.nl\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.bartbarnard.nl\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.bartbarnard.nl\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.bartbarnard.nl\/blog\/wp-json\/wp\/v2\/comments?post=726"}],"version-history":[{"count":11,"href":"https:\/\/www.bartbarnard.nl\/blog\/wp-json\/wp\/v2\/posts\/726\/revisions"}],"predecessor-version":[{"id":774,"href":"https:\/\/www.bartbarnard.nl\/blog\/wp-json\/wp\/v2\/posts\/726\/revisions\/774"}],"wp:attachment":[{"href":"https:\/\/www.bartbarnard.nl\/blog\/wp-json\/wp\/v2\/media?parent=726"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.bartbarnard.nl\/blog\/wp-json\/wp\/v2\/categories?post=726"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.bartbarnard.nl\/blog\/wp-json\/wp\/v2\/tags?post=726"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}