3e:null 3f:["$","title",null,{"children":"Bad Shuffle | Alex Lockwood | Observable"}] 45:T8b2,So you're reviewing some code (someone else's, obviously ;P) and see a function that attempts to randomly shuffle an array. The results appear to be random permutations of the array, but the implementation is incorrect and doesn't select every permutation of the array with equal probability. The implementation is something like this: ```javascript function badShuffle(array) { for (let i = 0; i < array.length; i++) { const randomIndex = Math.floor(Math.random() * array.length); const temp = array[randomIndex]; array[randomIndex] = array[i]; array[i] = temp; } } ``` The problem is with `randomIndex`. For every `i`, we choose a random index *from the entire array* and swap the elements at those positions. We know that for an array of length `n`, there are `n!` permutations of it. Choosing the random index from the entire array for each element of the array will distribute the outputs randomly across `n`^`n` possibilities. Since `n`^`n` is greater than (and not a multiple of) `n!`, this means that some permutations are repeated more than others and are therefore more likely and this won't produce a truly random permutation of the array. So we've learned that you should instead only swap with the *remaining* elements of the array, that way when an element is placed, it can't be chosen again (i.e. choosing `n` items randomly without replacement). This will produce `n!` possible outputs which matches our expectation for the number of permutations of an array. Satisfied, you make the change and move on: ```javascript function shuffle(array) { for (let i = 0; i < array.length; i++) { const randomIndex = Math.floor((Math.random() - i) * array.length + i); const temp = array[randomIndex]; array[randomIndex] = array[i]; array[i] = temp; } } ``` One day I got curious to see what the actual distribution is for the `badShuffle` implementation. At the top of the notebook is a heatmap of the distribution of where each index starts (y-axis) and where it ends up in the array. Below is the same data but using lines to display the distribution for each starting index (the darkest magenta is the `0th` item and the bright green is the last item).46:[] 43:{"id":"d7d4ded09aef9923","slug":null,"title":"Bad Shuffle","thumbnail":"74ac636a837a154228002b126c1938cacfed4085e3e4340bcf4906ea46488403","access_level":"public","create_time":"$D2024-02-10T21:40:18.796Z","update_time":"$D2024-02-10T21:40:24.073Z","view_time":null,"first_public_time":"$D2024-02-10T21:40:18.796Z","has_unpublished_edits":null,"fork":{"id":"20986c1e38ae2f16","slug":"bad-shuffle","title":"Bad Shuffle","owner":{"id":"a94d5c23aa0785ad","login":"duaneatat","name":"Duane Millar Barlow"}},"stars":0,"starred":false,"owner":{"type":"team","id":"6d132976a5d13ae0","login":"alexjlockwood","name":"Alex Lockwood","avatar_url":"https://avatars-next.observableusercontent.com/9202c2d37afa77f4123f2046c8f8db5f34f05f35d361cda0587576ce1b119493","tier":"starter_2024","bio":"","following":false},"version":365,"publish_version":null,"role":null,"authored":false,"authors":[{"type":"individual","id":"c44c7df024fdc0c2","login":"alexjlockwood","name":"Alex Lockwood","avatar_url":"https://avatars-next.observableusercontent.com/9202c2d37afa77f4123f2046c8f8db5f34f05f35d361cda0587576ce1b119493","tier":null,"bio":"","following":false}],"members":[{"type":"individual","id":"c44c7df024fdc0c2","login":"alexjlockwood","name":"Alex Lockwood","avatar_url":"https://avatars-next.observableusercontent.com/9202c2d37afa77f4123f2046c8f8db5f34f05f35d361cda0587576ce1b119493","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"lapsed":null,"subscribed":null,"forks":0,"collection":null,"type":"notebook","body":{"titling":"auto","title":"Bad Shuffle","cells":[{"id":0,"value":"# Bad Shuffle","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":60,"value":"Plot.plot({\n width: Math.min(800, width),\n height: 500,\n marginLeft: 20,\n marginRight: 0,\n marginTop: 0,\n color: {\n // domain: [0, 80000],\n scheme: \"blues\"\n },\n marks: [\n Plot.cell(results, {\n sort: \"original\",\n x: (d) => d.i,\n y: (d) => d.original,\n fill: \"frequency\",\n inset: -3\n })\n ]\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":264,"value":"*Array length is ${length}. The distribution of where each starting index (y-axis) most often ends up after calling `badShuffle(array)`. ${Number(n).toLocaleString()} trials. Darker blue is more frequent.*","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":223,"value":"$45","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":173,"value":"Plot.plot({\n width: Math.min(800, width),\n marginLeft: 60,\n marginRight: 40,\n color: {\n scheme: \"warm\"\n },\n marks: [\n Plot.ruleY([0]),\n Plot.line(results, {\n sort: \"i\",\n x: \"i\",\n y: \"frequency\",\n stroke: \"original\"\n })\n ]\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":6,"value":"viewof n = Inputs.range([1e6, 1e7], {\n value: width < 500 ? 2e6 : 5e6,\n step: 1,\n label: \"Number of trials\"\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":20,"value":"viewof length = Inputs.range([1, 100], {\n value: width < 500 ? 20 : 30,\n step: 1,\n label: \"Array length\"\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":291,"value":"For every position *i* of the array (aside from 0) the most likely position an element ends up in is the position just before it, *i - 1*. The very first element in the array is just as likely to to end up in any position, but the elements after that are significantly more likely to end up just to the left of where they started.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":306,"value":"## What is the intuition behind this behavior?","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":310,"value":"Please fork this notebook and help illuminate any of the following:\n\n- Why is the most likely position just to the left of the starting position?\n- Why does the max of each distribution together trace this nice curve?\n- Any other interesting observations?\n\nThank you!","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":356,"value":"## Related\n\nJust encountered Mike Bostock's similar matrix diagram that shows similar results (you'll need to select \"naïve swap (i ↦ random)\" from the dropdown): https://bost.ocks.org/mike/shuffle/compare.html","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":365,"value":"","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":15,"value":"badShuffle = (array) => {\n const copy = [...array];\n for (let i = 0; i < copy.length; i++) {\n const randomIndex = Math.floor(Math.random() * copy.length);\n const temp = copy[randomIndex];\n copy[randomIndex] = copy[i];\n copy[i] = temp;\n }\n return copy;\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":29,"value":"results = {\n const array = Array.from({ length: length }, (_, i) => i);\n const counts = array.map(() => Object.fromEntries(array.map((i) => [i, 0])));\n for (let i = 0; i < n; i++) {\n badShuffle(array).forEach((d, i) => counts[d][i]++);\n }\n\n return Object.entries(counts).flatMap(([original, counts]) =>\n Object.entries(counts).map(([i, count]) => ({\n i: +i,\n frequency: count,\n original: +original\n }))\n );\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W46","stdlib":"1"}} 44:"$43:body"