You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
{"payload":{"allShortcutsEnabled":false,"path":"Shuffle","repo":{"id":658452883,"defaultBranch":"master","name":"swift-algorithm-club","ownerLogin":"kkpan11","currentUserCanPush":false,"isFork":true,"isEmpty":false,"createdAt":"2023-06-25T19:31:47.000Z","ownerAvatar":"https://avatars.githubusercontent.com/u/3894279?v=4","public":true,"private":false,"isOrgOwned":false},"currentUser":null,"refInfo":{"name":"master","listCacheKey":"v0:1687721516.029016","canEdit":false,"refType":"branch","currentOid":"05c6d0bc5fa9484dd29eb324603b3452f4f44f39"},"tree":{"items":[{"name":"Shuffle.playground","path":"Shuffle/Shuffle.playground","contentType":"directory"},{"name":"README.markdown","path":"Shuffle/README.markdown","contentType":"file"},{"name":"Shuffle.swift","path":"Shuffle/Shuffle.swift","contentType":"file"}],"templateDirectorySuggestionUrl":null,"readme":{"displayName":"README.markdown","richText":"\u003carticle class=\"markdown-body entry-content container-lg\" itemprop=\"text\"\u003e\u003cdiv class=\"markdown-heading\" dir=\"auto\"\u003e\u003ch1 tabindex=\"-1\" class=\"heading-element\" dir=\"auto\"\u003eShuffle\u003c/h1\u003e\u003ca id=\"user-content-shuffle\" class=\"anchor\" aria-label=\"Permalink: Shuffle\" href=\"#shuffle\"\u003e\u003csvg class=\"octicon octicon-link\" viewBox=\"0 0 16 16\" version=\"1.1\" width=\"16\" height=\"16\" aria-hidden=\"true\"\u003e\u003cpath d=\"m7.775 3.275 1.25-1.25a3.5 3.5 0 1 1 4.95 4.95l-2.5 2.5a3.5 3.5 0 0 1-4.95 0 .751.751 0 0 1 .018-1.042.751.751 0 0 1 1.042-.018 1.998 1.998 0 0 0 2.83 0l2.5-2.5a2.002 2.002 0 0 0-2.83-2.83l-1.25 1.25a.751.751 0 0 1-1.042-.018.751.751 0 0 1-.018-1.042Zm-4.69 9.64a1.998 1.998 0 0 0 2.83 0l1.25-1.25a.751.751 0 0 1 1.042.018.751.751 0 0 1 .018 1.042l-1.25 1.25a3.5 3.5 0 1 1-4.95-4.95l2.5-2.5a3.5 3.5 0 0 1 4.95 0 .751.751 0 0 1-.018 1.042.751.751 0 0 1-1.042.018 1.998 1.998 0 0 0-2.83 0l-2.5 2.5a1.998 1.998 0 0 0 0 2.83Z\"\u003e\u003c/path\u003e\u003c/svg\u003e\u003c/a\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eGoal: Rearrange the contents of an array.\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eImagine you're making a card game and you need to shuffle a deck of cards. You can represent the deck by an array of \u003ccode\u003eCard\u003c/code\u003e objects and shuffling the deck means to change the order of those objects in the array. (It's like the opposite of sorting.)\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eHere is a naive way to approach this in Swift:\u003c/p\u003e\n\u003cdiv class=\"highlight highlight-source-swift notranslate position-relative overflow-auto\" dir=\"auto\" data-snippet-clipboard-copy-content=\"extension Array {\n public mutating func shuffle() {\n var temp = [Element]()\n while !isEmpty {\n let i = random(count)\n let obj = remove(at: i)\n temp.append(obj)\n }\n self = temp\n }\n}\"\u003e\u003cpre\u003e\u003cspan class=\"pl-k\"\u003eextension\u003c/span\u003e \u003cspan class=\"pl-smi\"\u003eArray\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e{\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003epublic\u003c/span\u003e \u003cspan class=\"pl-k\"\u003emutating\u003c/span\u003e \u003cspan class=\"pl-en\"\u003efunc\u003c/span\u003e shuffle\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e{\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003evar\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003etemp\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e[\u003c/span\u003eElement\u003cspan class=\"pl-kos\"\u003e]\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003ewhile\u003c/span\u003e !isEmpty \u003cspan class=\"pl-kos\"\u003e{\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003elet\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003ei\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-en\"\u003erandom\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003ecount\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003elet\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003eobj\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-en\"\u003eremove\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003eat\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e i\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e\n temp\u003cspan class=\"pl-kos\"\u003e.\u003c/span\u003e\u003cspan class=\"pl-en\"\u003eappend\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003eobj\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e\n \u003cspan class=\"pl-kos\"\u003e}\u003c/span\u003e\n \u003cspan class=\"pl-smi\"\u003eself\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e temp\n \u003cspan class=\"pl-kos\"\u003e}\u003c/span\u003e\n\u003cspan class=\"pl-kos\"\u003e}\u003c/span\u003e\u003c/pre\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eTo try it out, copy the code into a playground and then do:\u003c/p\u003e\n\u003cdiv class=\"highlight highlight-source-swift notranslate position-relative overflow-auto\" dir=\"auto\" data-snippet-clipboard-copy-content=\"var list = [ \u0026quot;a\u0026quot;, \u0026quot;b\u0026quot;, \u0026quot;c\u0026quot;, \u0026quot;d\u0026quot;, \u0026quot;e\u0026quot;, \u0026quot;f\u0026quot;, \u0026quot;g\u0026quot; ]\nlist.shuffle()\nlist.shuffle()\nlist.shuffle()\"\u003e\u003cpre\u003e\u003cspan class=\"pl-k\"\u003evar\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003elist\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e[\u003c/span\u003e \u003cspan class=\"pl-s\"\u003e\"\u003c/span\u003e\u003cspan class=\"pl-s\"\u003ea\u003c/span\u003e\u003cspan class=\"pl-s\"\u003e\"\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e \u003cspan class=\"pl-s\"\u003e\"\u003c/span\u003e\u003cspan class=\"pl-s\"\u003eb\u003c/span\u003e\u003cspan class=\"pl-s\"\u003e\"\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e \u003cspan class=\"pl-s\"\u003e\"\u003c/span\u003e\u003cspan class=\"pl-s\"\u003ec\u003c/span\u003e\u003cspan class=\"pl-s\"\u003e\"\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e \u003cspan class=\"pl-s\"\u003e\"\u003c/span\u003e\u003cspan class=\"pl-s\"\u003ed\u003c/span\u003e\u003cspan class=\"pl-s\"\u003e\"\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e \u003cspan class=\"pl-s\"\u003e\"\u003c/span\u003e\u003cspan class=\"pl-s\"\u003ee\u003c/span\u003e\u003cspan class=\"pl-s\"\u003e\"\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e \u003cspan class=\"pl-s\"\u003e\"\u003c/span\u003e\u003cspan class=\"pl-s\"\u003ef\u003c/span\u003e\u003cspan class=\"pl-s\"\u003e\"\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e \u003cspan class=\"pl-s\"\u003e\"\u003c/span\u003e\u003cspan class=\"pl-s\"\u003eg\u003c/span\u003e\u003cspan class=\"pl-s\"\u003e\"\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e]\u003c/span\u003e\nlist\u003cspan class=\"pl-kos\"\u003e.\u003c/span\u003e\u003cspan class=\"pl-en\"\u003eshuffle\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e\nlist\u003cspan class=\"pl-kos\"\u003e.\u003c/span\u003e\u003cspan class=\"pl-en\"\u003eshuffle\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e\nlist\u003cspan class=\"pl-kos\"\u003e.\u003c/span\u003e\u003cspan class=\"pl-en\"\u003eshuffle\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e\u003c/pre\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eYou should see three different arrangements -- or \u003ca href=\"/kkpan11/swift-algorithm-club/blob/master/Combinatorics\"\u003epermutations\u003c/a\u003e to use math-speak -- of the objects in the array.\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eThis shuffle works \u003cem\u003ein place\u003c/em\u003e, it modifies the contents of the original array. The algorithm works by creating a new array, \u003ccode\u003etemp\u003c/code\u003e, that is initially empty. Then we randomly choose an element from the original array and append it to \u003ccode\u003etemp\u003c/code\u003e, until the original array is empty. Finally, the temporary array is copied back into the original one.\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eThis code works just fine but it's not very efficient. Removing an element from an array is an \u003cstrong\u003eO(n)\u003c/strong\u003e operation and we perform this \u003cstrong\u003en\u003c/strong\u003e times, making the total algorithm \u003cstrong\u003eO(n^2)\u003c/strong\u003e. We can do better!\u003c/p\u003e\n\u003cdiv class=\"markdown-heading\" dir=\"auto\"\u003e\u003ch2 tabindex=\"-1\" class=\"heading-element\" dir=\"auto\"\u003eThe Fisher-Yates / Knuth shuffle\u003c/h2\u003e\u003ca id=\"user-content-the-fisher-yates--knuth-shuffle\" class=\"anchor\" aria-label=\"Permalink: The Fisher-Yates / Knuth shuffle\" href=\"#the-fisher-yates--knuth-shuffle\"\u003e\u003csvg class=\"octicon octicon-link\" viewBox=\"0 0 16 16\" version=\"1.1\" width=\"16\" height=\"16\" aria-hidden=\"true\"\u003e\u003cpath d=\"m7.775 3.275 1.25-1.25a3.5 3.5 0 1 1 4.95 4.95l-2.5 2.5a3.5 3.5 0 0 1-4.95 0 .751.751 0 0 1 .018-1.042.751.751 0 0 1 1.042-.018 1.998 1.998 0 0 0 2.83 0l2.5-2.5a2.002 2.002 0 0 0-2.83-2.83l-1.25 1.25a.751.751 0 0 1-1.042-.018.751.751 0 0 1-.018-1.042Zm-4.69 9.64a1.998 1.998 0 0 0 2.83 0l1.25-1.25a.751.751 0 0 1 1.042.018.751.751 0 0 1 .018 1.042l-1.25 1.25a3.5 3.5 0 1 1-4.95-4.95l2.5-2.5a3.5 3.5 0 0 1 4.95 0 .751.751 0 0 1-.018 1.042.751.751 0 0 1-1.042.018 1.998 1.998 0 0 0-2.83 0l-2.5 2.5a1.998 1.998 0 0 0 0 2.83Z\"\u003e\u003c/path\u003e\u003c/svg\u003e\u003c/a\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eHere is a much-improved version of the shuffle algorithm:\u003c/p\u003e\n\u003cdiv class=\"highlight highlight-source-swift notranslate position-relative overflow-auto\" dir=\"auto\" data-snippet-clipboard-copy-content=\"extension Array {\n public mutating func shuffle() {\n for i in stride(from: count - 1, through: 1, by: -1) {\n let j = Int.random(in: 0...i)\n if i != j {\n swap(\u0026amp;self[i], \u0026amp;self[j])\n }\n }\n }\n}\"\u003e\u003cpre\u003e\u003cspan class=\"pl-k\"\u003eextension\u003c/span\u003e \u003cspan class=\"pl-smi\"\u003eArray\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e{\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003epublic\u003c/span\u003e \u003cspan class=\"pl-k\"\u003emutating\u003c/span\u003e \u003cspan class=\"pl-en\"\u003efunc\u003c/span\u003e shuffle\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e{\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003efor\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003ei\u003c/span\u003e \u003cspan class=\"pl-k\"\u003ein\u003c/span\u003e \u003cspan class=\"pl-en\"\u003estride\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003efrom\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e count \u003cspan class=\"pl-c1\"\u003e-\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e1\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e through\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e1\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e by\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e-\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e1\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e{\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003elet\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003ej\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-smi\"\u003eInt\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e.\u003c/span\u003e\u003cspan class=\"pl-en\"\u003erandom\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003ein\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e0\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e...\u003c/span\u003ei\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003eif\u003c/span\u003e i \u003cspan class=\"pl-c1\"\u003e!=\u003c/span\u003e j \u003cspan class=\"pl-kos\"\u003e{\u003c/span\u003e\n \u003cspan class=\"pl-en\"\u003eswap\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e\u0026amp;\u003c/span\u003e\u003cspan class=\"pl-smi\"\u003eself\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e[\u003c/span\u003ei\u003cspan class=\"pl-kos\"\u003e]\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e\u0026amp;\u003c/span\u003e\u003cspan class=\"pl-smi\"\u003eself\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e[\u003c/span\u003ej\u003cspan class=\"pl-kos\"\u003e]\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e\n \u003cspan class=\"pl-kos\"\u003e}\u003c/span\u003e\n \u003cspan class=\"pl-kos\"\u003e}\u003c/span\u003e\n \u003cspan class=\"pl-kos\"\u003e}\u003c/span\u003e\n\u003cspan class=\"pl-kos\"\u003e}\u003c/span\u003e\u003c/pre\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eAgain, this picks objects at random. In the naive version, we placed those objects into a new temporary array so we could keep track of which objects were already shuffled and which still remained to be done. In this improved algorithm, however, we'll move the shuffled objects to the end of the original array.\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eLet's walk through the example. We have the array:\u003c/p\u003e\n\u003cdiv class=\"snippet-clipboard-content notranslate position-relative overflow-auto\" data-snippet-clipboard-copy-content=\"[ \u0026quot;a\u0026quot;, \u0026quot;b\u0026quot;, \u0026quot;c\u0026quot;, \u0026quot;d\u0026quot;, \u0026quot;e\u0026quot;, \u0026quot;f\u0026quot;, \u0026quot;g\u0026quot; ]\"\u003e\u003cpre class=\"notranslate\"\u003e\u003ccode\u003e[ \"a\", \"b\", \"c\", \"d\", \"e\", \"f\", \"g\" ]\n\u003c/code\u003e\u003c/pre\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eThe loop starts at the end of the array and works its way back to the beginning. The very first random number can be any element from the entire array. Let's say it returns 2, the index of \u003ccode\u003e\"c\"\u003c/code\u003e. We swap \u003ccode\u003e\"c\"\u003c/code\u003e with \u003ccode\u003e\"g\"\u003c/code\u003e to move it to the end:\u003c/p\u003e\n\u003cdiv class=\"snippet-clipboard-content notranslate position-relative overflow-auto\" data-snippet-clipboard-copy-content=\"[ \u0026quot;a\u0026quot;, \u0026quot;b\u0026quot;, \u0026quot;g\u0026quot;, \u0026quot;d\u0026quot;, \u0026quot;e\u0026quot;, \u0026quot;f\u0026quot; | \u0026quot;c\u0026quot; ]\n * *\"\u003e\u003cpre class=\"notranslate\"\u003e\u003ccode\u003e[ \"a\", \"b\", \"g\", \"d\", \"e\", \"f\" | \"c\" ]\n * *\n\u003c/code\u003e\u003c/pre\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eThe array now consists of two regions, indicated by the \u003ccode\u003e|\u003c/code\u003e bar. Everything to the right of the bar is shuffled already.\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eThe next random number is chosen from the range 0...6, so only from the region \u003ccode\u003e[ \"a\", \"b\", \"g\", \"d\", \"e\", \"f\" ]\u003c/code\u003e. It will never choose \u003ccode\u003e\"c\"\u003c/code\u003e since that object is done and we'll no longer touch it.\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eLet's say the random number generator picks 0, the index of \u003ccode\u003e\"a\"\u003c/code\u003e. Then we swap \u003ccode\u003e\"a\"\u003c/code\u003e with \u003ccode\u003e\"f\"\u003c/code\u003e, which is the last element in the unshuffled portion, and the array looks like this:\u003c/p\u003e\n\u003cdiv class=\"snippet-clipboard-content notranslate position-relative overflow-auto\" data-snippet-clipboard-copy-content=\"[ \u0026quot;f\u0026quot;, \u0026quot;b\u0026quot;, \u0026quot;g\u0026quot;, \u0026quot;d\u0026quot;, \u0026quot;e\u0026quot; | \u0026quot;a\u0026quot;, \u0026quot;c\u0026quot; ]\n * *\"\u003e\u003cpre class=\"notranslate\"\u003e\u003ccode\u003e[ \"f\", \"b\", \"g\", \"d\", \"e\" | \"a\", \"c\" ]\n * *\n\u003c/code\u003e\u003c/pre\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eThe next random number is somewhere in \u003ccode\u003e[ \"f\", \"b\", \"g\", \"d\", \"e\" ]\u003c/code\u003e, so let's say it is 3. We swap \u003ccode\u003e\"d\"\u003c/code\u003e with \u003ccode\u003e\"e\"\u003c/code\u003e:\u003c/p\u003e\n\u003cdiv class=\"snippet-clipboard-content notranslate position-relative overflow-auto\" data-snippet-clipboard-copy-content=\"[ \u0026quot;f\u0026quot;, \u0026quot;b\u0026quot;, \u0026quot;g\u0026quot;, \u0026quot;e\u0026quot; | \u0026quot;d\u0026quot;, \u0026quot;a\u0026quot;, \u0026quot;c\u0026quot; ]\n * *\"\u003e\u003cpre class=\"notranslate\"\u003e\u003ccode\u003e[ \"f\", \"b\", \"g\", \"e\" | \"d\", \"a\", \"c\" ]\n * *\n\u003c/code\u003e\u003c/pre\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eAnd so on... This continues until there is only one element remaining in the left portion. For example:\u003c/p\u003e\n\u003cdiv class=\"snippet-clipboard-content notranslate position-relative overflow-auto\" data-snippet-clipboard-copy-content=\"[ \u0026quot;b\u0026quot; | \u0026quot;e\u0026quot;, \u0026quot;f\u0026quot;, \u0026quot;g\u0026quot;, \u0026quot;d\u0026quot;, \u0026quot;a\u0026quot;, \u0026quot;c\u0026quot; ]\"\u003e\u003cpre class=\"notranslate\"\u003e\u003ccode\u003e[ \"b\" | \"e\", \"f\", \"g\", \"d\", \"a\", \"c\" ]\n\u003c/code\u003e\u003c/pre\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eThere's nothing left to swap that \u003ccode\u003e\"b\"\u003c/code\u003e with, so we're done.\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eBecause we only look at each array element once, this algorithm has a guaranteed running time of \u003cstrong\u003eO(n)\u003c/strong\u003e. It's as fast as you could hope to get!\u003c/p\u003e\n\u003cdiv class=\"markdown-heading\" dir=\"auto\"\u003e\u003ch2 tabindex=\"-1\" class=\"heading-element\" dir=\"auto\"\u003eCreating a new array that is shuffled\u003c/h2\u003e\u003ca id=\"user-content-creating-a-new-array-that-is-shuffled\" class=\"anchor\" aria-label=\"Permalink: Creating a new array that is shuffled\" href=\"#creating-a-new-array-that-is-shuffled\"\u003e\u003csvg class=\"octicon octicon-link\" viewBox=\"0 0 16 16\" version=\"1.1\" width=\"16\" height=\"16\" aria-hidden=\"true\"\u003e\u003cpath d=\"m7.775 3.275 1.25-1.25a3.5 3.5 0 1 1 4.95 4.95l-2.5 2.5a3.5 3.5 0 0 1-4.95 0 .751.751 0 0 1 .018-1.042.751.751 0 0 1 1.042-.018 1.998 1.998 0 0 0 2.83 0l2.5-2.5a2.002 2.002 0 0 0-2.83-2.83l-1.25 1.25a.751.751 0 0 1-1.042-.018.751.751 0 0 1-.018-1.042Zm-4.69 9.64a1.998 1.998 0 0 0 2.83 0l1.25-1.25a.751.751 0 0 1 1.042.018.751.751 0 0 1 .018 1.042l-1.25 1.25a3.5 3.5 0 1 1-4.95-4.95l2.5-2.5a3.5 3.5 0 0 1 4.95 0 .751.751 0 0 1-.018 1.042.751.751 0 0 1-1.042.018 1.998 1.998 0 0 0-2.83 0l-2.5 2.5a1.998 1.998 0 0 0 0 2.83Z\"\u003e\u003c/path\u003e\u003c/svg\u003e\u003c/a\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eThere is a slight variation on this algorithm that is useful for when you want to create a new array instance that contains the values \u003ccode\u003e0\u003c/code\u003e to \u003ccode\u003en-1\u003c/code\u003e in random order.\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eHere is the code:\u003c/p\u003e\n\u003cdiv class=\"highlight highlight-source-swift notranslate position-relative overflow-auto\" dir=\"auto\" data-snippet-clipboard-copy-content=\"public func shuffledArray(_ n: Int) -\u0026gt; [Int] {\n var a = [Int](repeating: 0, count: n)\n for i in 0..\u0026lt;n {\n let j = Int.random(in: 0...i)\n // for the Fisher–Yates_shuffle's pseudo code implement in wiki, it will check if i != j\n a[i] = a[j]\n a[j] = i\n }\n return a\n}\"\u003e\u003cpre\u003e\u003cspan class=\"pl-k\"\u003epublic\u003c/span\u003e \u003cspan class=\"pl-en\"\u003efunc\u003c/span\u003e shuffledArray\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003e_ n\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e \u003cspan class=\"pl-smi\"\u003eInt\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e-\u0026gt;\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e[\u003c/span\u003e\u003cspan class=\"pl-smi\"\u003eInt\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e]\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e{\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003evar\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003ea\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e[\u003c/span\u003eInt\u003cspan class=\"pl-kos\"\u003e]\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003erepeating\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e0\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e count\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e n\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003efor\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003ei\u003c/span\u003e \u003cspan class=\"pl-k\"\u003ein\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e0\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e..\u0026lt;\u003c/span\u003en \u003cspan class=\"pl-kos\"\u003e{\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003elet\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003ej\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-smi\"\u003eInt\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e.\u003c/span\u003e\u003cspan class=\"pl-en\"\u003erandom\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003ein\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e0\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e...\u003c/span\u003ei\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e\n // for the Fisher–Yates_shuffle's pseudo code implement in wiki, it will check if i != j\n \u003cspan class=\"pl-en\"\u003ea\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e[\u003c/span\u003ei\u003cspan class=\"pl-kos\"\u003e]\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-en\"\u003ea\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e[\u003c/span\u003ej\u003cspan class=\"pl-kos\"\u003e]\u003c/span\u003e\n \u003cspan class=\"pl-en\"\u003ea\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e[\u003c/span\u003ej\u003cspan class=\"pl-kos\"\u003e]\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e i\n \u003cspan class=\"pl-kos\"\u003e}\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003ereturn\u003c/span\u003e a\n\u003cspan class=\"pl-kos\"\u003e}\u003c/span\u003e\u003c/pre\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eTo use it:\u003c/p\u003e\n\u003cdiv class=\"highlight highlight-source-swift notranslate position-relative overflow-auto\" dir=\"auto\" data-snippet-clipboard-copy-content=\"let numbers = shuffledArray(10)\"\u003e\u003cpre\u003e\u003cspan class=\"pl-k\"\u003elet\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003enumbers\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-en\"\u003eshuffledArray\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e10\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e\u003c/pre\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eThis returns something like \u003ccode\u003e[3, 0, 9, 1, 8, 5, 2, 6, 7, 4]\u003c/code\u003e. As you can see, every number between 0 and 10 is in that list, but shuffled around. Of course, when you try it for yourself the order of the numbers will be different.\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eThe \u003ccode\u003eshuffledArray()\u003c/code\u003e function first creates a new array with \u003ccode\u003en\u003c/code\u003e zeros. Then it loops \u003ccode\u003en\u003c/code\u003e times and in each step adds the next number from the sequence to a random position in the array. The trick is to make sure that none of these numbers gets overwritten with the next one, so it moves the previous number out of the way first!\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eFor this function, \u003ccode\u003eThe condition that checks if j ≠ i may be omitted in languages that have no problems accessing uninitialized array values, and for which assigning is cheaper than comparing.\u003c/code\u003e, you can check it in wiki. And also remove checking logic will optimise performance.\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eThe algorithm is quite clever and I suggest you walk through an example yourself, either on paper or in the playground. (Hint: Again it splits the array into two regions.)\u003c/p\u003e\n\u003cdiv class=\"markdown-heading\" dir=\"auto\"\u003e\u003ch2 tabindex=\"-1\" class=\"heading-element\" dir=\"auto\"\u003eSee also\u003c/h2\u003e\u003ca id=\"user-content-see-also\" class=\"anchor\" aria-label=\"Permalink: See also\" href=\"#see-also\"\u003e\u003csvg class=\"octicon octicon-link\" viewBox=\"0 0 16 16\" version=\"1.1\" width=\"16\" height=\"16\" aria-hidden=\"true\"\u003e\u003cpath d=\"m7.775 3.275 1.25-1.25a3.5 3.5 0 1 1 4.95 4.95l-2.5 2.5a3.5 3.5 0 0 1-4.95 0 .751.751 0 0 1 .018-1.042.751.751 0 0 1 1.042-.018 1.998 1.998 0 0 0 2.83 0l2.5-2.5a2.002 2.002 0 0 0-2.83-2.83l-1.25 1.25a.751.751 0 0 1-1.042-.018.751.751 0 0 1-.018-1.042Zm-4.69 9.64a1.998 1.998 0 0 0 2.83 0l1.25-1.25a.751.751 0 0 1 1.042.018.751.751 0 0 1 .018 1.042l-1.25 1.25a3.5 3.5 0 1 1-4.95-4.95l2.5-2.5a3.5 3.5 0 0 1 4.95 0 .751.751 0 0 1-.018 1.042.751.751 0 0 1-1.042.018 1.998 1.998 0 0 0-2.83 0l-2.5 2.5a1.998 1.998 0 0 0 0 2.83Z\"\u003e\u003c/path\u003e\u003c/svg\u003e\u003c/a\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eThese Swift implementations are based on pseudocode from the \u003ca href=\"https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle\" rel=\"nofollow\"\u003eWikipedia article\u003c/a\u003e.\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eMike Bostock has a \u003ca href=\"http://bost.ocks.org/mike/shuffle/\" rel=\"nofollow\"\u003egreat visualization\u003c/a\u003e of the shuffle algorithm.\u003c/p\u003e\n\u003cp dir=\"auto\"\u003e\u003cem\u003eWritten for Swift Algorithm Club by Matthijs Hollemans\u003c/em\u003e\u003c/p\u003e\n\u003c/article\u003e","errorMessage":null,"headerInfo":{"toc":[{"level":1,"text":"Shuffle","anchor":"shuffle","htmlText":"Shuffle"},{"level":2,"text":"The Fisher-Yates / Knuth shuffle","anchor":"the-fisher-yates--knuth-shuffle","htmlText":"The Fisher-Yates / Knuth shuffle"},{"level":2,"text":"Creating a new array that is shuffled","anchor":"creating-a-new-array-that-is-shuffled","htmlText":"Creating a new array that is shuffled"},{"level":2,"text":"See also","anchor":"see-also","htmlText":"See also"}],"siteNavLoginPath":"/login?return_to=https%3A%2F%2Fgithub.com%2Fkkpan11%2Fswift-algorithm-club%2Ftree%2Fmaster%2FShuffle"}},"totalCount":3,"showBranchInfobar":true},"fileTree":{"":{"items":[{"name":".github","path":".github","contentType":"directory"},{"name":"3Sum and 4Sum","path":"3Sum and 4Sum","contentType":"directory"},{"name":"A-Star","path":"A-Star","contentType":"directory"},{"name":"AVL Tree","path":"AVL Tree","contentType":"directory"},{"name":"All-Pairs Shortest Paths","path":"All-Pairs Shortest Paths","contentType":"directory"},{"name":"Array2D","path":"Array2D","contentType":"directory"},{"name":"B-Tree","path":"B-Tree","contentType":"directory"},{"name":"Binary Search Tree","path":"Binary Search Tree","contentType":"directory"},{"name":"Binary Search","path":"Binary Search","contentType":"directory"},{"name":"Binary Tree","path":"Binary Tree","contentType":"directory"},{"name":"Bit Set","path":"Bit Set","contentType":"directory"},{"name":"Bloom Filter","path":"Bloom Filter","contentType":"directory"},{"name":"Bounded Priority Queue","path":"Bounded Priority Queue","contentType":"directory"},{"name":"Boyer-Moore-Horspool","path":"Boyer-Moore-Horspool","contentType":"directory"},{"name":"Breadth-First Search","path":"Breadth-First Search","contentType":"directory"},{"name":"Brute-Force String Search","path":"Brute-Force String Search","contentType":"directory"},{"name":"Bubble Sort","path":"Bubble Sort","contentType":"directory"},{"name":"Bucket Sort","path":"Bucket Sort","contentType":"directory"},{"name":"Closest Pair","path":"Closest Pair","contentType":"directory"},{"name":"Comb Sort","path":"Comb Sort","contentType":"directory"},{"name":"Combinatorics","path":"Combinatorics","contentType":"directory"},{"name":"Convex Hull","path":"Convex Hull","contentType":"directory"},{"name":"Count Occurrences","path":"Count Occurrences","contentType":"directory"},{"name":"CounterClockWise","path":"CounterClockWise","contentType":"directory"},{"name":"Counting Sort","path":"Counting Sort","contentType":"directory"},{"name":"Depth-First Search","path":"Depth-First Search","contentType":"directory"},{"name":"Deque","path":"Deque","contentType":"directory"},{"name":"Dijkstra Algorithm","path":"Dijkstra Algorithm","contentType":"directory"},{"name":"DiningPhilosophers","path":"DiningPhilosophers","contentType":"directory"},{"name":"Egg Drop Problem","path":"Egg Drop Problem","contentType":"directory"},{"name":"Encode and Decode Tree","path":"Encode and Decode Tree","contentType":"directory"},{"name":"Fixed Size Array","path":"Fixed Size Array","contentType":"directory"},{"name":"Fizz Buzz","path":"Fizz Buzz","contentType":"directory"},{"name":"GCD","path":"GCD","contentType":"directory"},{"name":"Genetic","path":"Genetic","contentType":"directory"},{"name":"Graph","path":"Graph","contentType":"directory"},{"name":"Hash Set","path":"Hash Set","contentType":"directory"},{"name":"Hash Table","path":"Hash Table","contentType":"directory"},{"name":"Hashed Heap","path":"Hashed Heap","contentType":"directory"},{"name":"HaversineDistance","path":"HaversineDistance","contentType":"directory"},{"name":"Heap Sort","path":"Heap Sort","contentType":"directory"},{"name":"Heap","path":"Heap","contentType":"directory"},{"name":"Huffman Coding","path":"Huffman Coding","contentType":"directory"},{"name":"Images","path":"Images","contentType":"directory"},{"name":"Insertion Sort","path":"Insertion Sort","contentType":"directory"},{"name":"Introsort","path":"Introsort","contentType":"directory"},{"name":"K-Means","path":"K-Means","contentType":"directory"},{"name":"Karatsuba Multiplication","path":"Karatsuba Multiplication","contentType":"directory"},{"name":"Knuth-Morris-Pratt","path":"Knuth-Morris-Pratt","contentType":"directory"},{"name":"Kth Largest Element","path":"Kth Largest Element","contentType":"directory"},{"name":"LRU Cache","path":"LRU Cache","contentType":"directory"},{"name":"Linear Regression","path":"Linear Regression","contentType":"directory"},{"name":"Linear Search","path":"Linear Search","contentType":"directory"},{"name":"Linked List","path":"Linked List","contentType":"directory"},{"name":"Longest Common Subsequence","path":"Longest Common Subsequence","contentType":"directory"},{"name":"Merge Sort","path":"Merge Sort","contentType":"directory"},{"name":"Miller-Rabin Primality Test","path":"Miller-Rabin Primality Test","contentType":"directory"},{"name":"Minimum Edit Distance","path":"Minimum Edit Distance","contentType":"directory"},{"name":"Minimum Spanning Tree (Unweighted)","path":"Minimum Spanning Tree (Unweighted)","contentType":"directory"},{"name":"Minimum Spanning Tree","path":"Minimum Spanning Tree","contentType":"directory"},{"name":"MinimumCoinChange","path":"MinimumCoinChange","contentType":"directory"},{"name":"Monty Hall Problem","path":"Monty Hall Problem","contentType":"directory"},{"name":"Multiset","path":"Multiset","contentType":"directory"},{"name":"Myers Difference Algorithm","path":"Myers Difference Algorithm","contentType":"directory"},{"name":"Naive Bayes Classifier","path":"Naive Bayes Classifier","contentType":"directory"},{"name":"Octree","
3DF5
path":"Octree","contentType":"directory"},{"name":"Ordered Array","path":"Ordered Array","contentType":"directory"},{"name":"Ordered Set","path":"Ordered Set","contentType":"directory"},{"name":"Palindromes","path":"Palindromes","contentType":"directory"},{"name":"Points Lines Planes","path":"Points Lines Planes","contentType":"directory"},{"name":"Priority Queue","path":"Priority Queue","contentType":"directory"},{"name":"QuadTree","path":"QuadTree","contentType":"directory"},{"name":"Queue","path":"Queue","contentType":"directory"},{"name":"Quicksort","path":"Quicksort","contentType":"directory"},{"name":"Rabin-Karp","path":"Rabin-Karp","contentType":"directory"},{"name":"Radix Sort","path":"Radix Sort","contentType":"directory"},{"name":"Radix Tree","path":"Radix Tree","contentType":"directory"},{"name":"Red-Black Tree","path":"Red-Black Tree","contentType":"directory"},{"name":"Ring Buffer","path":"Ring Buffer","contentType":"directory"},{"name":"Rootish Array Stack","path":"Rootish Array Stack","contentType":"directory"},{"name":"Run-Length Encoding","path":"Run-Length Encoding","contentType":"directory"},{"name":"Segment Tree","path":"Segment Tree","contentType":"directory"},{"name":"Select Minimum Maximum","path":"Select Minimum Maximum","contentType":"directory"},{"name":"Selection Sampling","path":"Selection Sampling","contentType":"directory"},{"name":"Selection Sort","path":"Selection Sort","contentType":"directory"},{"name":"Set Cover (Unweighted)","path":"Set Cover (Unweighted)","contentType":"directory"},{"name":"Shell Sort","path":"Shell Sort","contentType":"directory"},{"name":"Shortest Path (Unweighted)","path":"Shortest Path (Unweighted)","contentType":"directory"},{"name":"Shuffle","path":"Shuffle","contentType":"directory"},{"name":"Shunting Yard","path":"Shunting Yard","contentType":"directory"},{"name":"Simulated annealing","path":"Simulated annealing","contentType":"directory"},{"name":"Single-Source Shortest Paths (Weighted)","path":"Single-Source Shortest Paths (Weighted)","contentType":"directory"},{"name":"Singly Linked List","path":"Singly Linked List","contentType":"directory"},{"name":"Skip-List","path":"Skip-List","contentType":"directory"},{"name":"Slow Sort","path":"Slow Sort","contentType":"directory"},{"name":"Sorted Set","path":"Sorted Set","contentType":"directory"},{"name":"Sparse Table","path":"Sparse Table","contentType":"directory"},{"name":"Splay Tree","path":"Splay Tree","contentType":"directory"},{"name":"Stack","path":"Stack","contentType":"directory"},{"name":"Strassen Matrix Multiplication","path":"Strassen Matrix Multiplication","contentType":"directory"},{"name":"Ternary Search Tree","path":"Ternary Search Tree","contentType":"directory"},{"name":"Threaded Binary Tree","path":"Threaded Binary Tree","contentType":"directory"},{"name":"Topological Sort","path":"Topological Sort","contentType":"directory"},{"name":"Treap","path":"Treap","contentType":"directory"},{"name":"Tree","path":"Tree","contentType":"directory"},{"name":"Trie","path":"Trie","contentType":"directory"},{"name":"Two-Sum Problem","path":"Two-Sum Problem","contentType":"directory"},{"name":"Union-Find","path":"Union-Find","contentType":"directory"},{"name":"Z-Algorithm","path":"Z-Algorithm","contentType":"directory"},{"name":".gitignore","path":".gitignore","contentType":"file"},{"name":".swiftlint.yml","path":".swiftlint.yml","contentType":"file"},{"name":"Algorithm Design.markdown","path":"Algorithm Design.markdown","contentType":"file"},{"name":"Big-O Notation.markdown","path":"Big-O Notation.markdown","contentType":"file"},{"name":"LICENSE.txt","path":"LICENSE.txt","contentType":"file"},{"name":"README.markdown","path":"README.markdown","contentType":"file"},{"name":"Under Construction.markdown","path":"Under Construction.markdown","contentType":"file"},{"name":"What are Algorithms.markdown","path":"What are Algorithms.markdown","contentType":"file"},{"name":"Why Algorithms.markdown","path":"Why Algorithms.markdown","contentType":"file"},{"name":"gfm-render.sh","path":"gfm-render.sh","contentType":"file"},{"name":"install_swiftlint.sh","path":"install_swiftlint.sh","contentType":"file"}],"totalCount":120}},"fileTreeProcessingTime":3.721273,"foldersToFetch":[],"treeExpanded":true,"symbolsExpanded":false,"csrf_tokens":{"/kkpan11/swift-algorithm-club/branches":{"post":"A_Z85ZC38siQFsqDK3hnk6b1Luy6_0vjp0qbvo1M4NUYGg_w-1fUWPH1ZI9UMbuT3CPEACdAoIfI-rhMvqi1vw"},"/kkpan11/swift-algorithm-club/branches/fetch_and_merge/master":{"post":"4lYzHzMVHyI3iPogeuibwacINiVUVERt21qQAECB9uSO3sO3t_MF73jDdpnLgY9uRJG0-DguO6FVnG0c02aGTg"},"/kkpan11/swift-algorithm-club/branches/fetch_and_merge/master?discard_changes=true":{"post":"P5wTCSUJTJS632qbMe31lU-g7OG9O5D1unt5kx7uaJ5TFOOhoe9WWfWU5iKAhOE6rDluPNFB7zk0vYSPjQkYNA"}}},"title":"swift-algorithm-club/Shuffle at master · kkpan11/swift-algorithm-club","appPayload":{"helpUrl":"https://docs.github.com","findFileWorkerPath":"/assets-cdn/worker/find-file-worker-263cab1760dd.js","findInFileWorkerPath":"/assets-cdn/worker/find-in-file-worker-b84e9496fc59.js","githubDevUrl":null,"enabled_features":{"code_nav_ui_events":false,"react_blob_overlay":false,"accessible_code_button":true}}}