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":"Selection Sampling","repo":{"id":260177806,"defaultBranch":"master","name":"swift-algorithm-club","ownerLogin":"lighter","currentUserCanPush":false,"isFork":true,"isEmpty":false,"createdAt":"2020-04-30T10:10:33.000Z","ownerAvatar":"https://avatars.githubusercontent.com/u/480133?v=4","public":true,"private":false,"isOrgOwned":false},"currentUser":null,"refInfo":{"name":"master","listCacheKey":"v0:1617949025.579224","canEdit":false,"refType":"branch","currentOid":"2c47dc32a30006e4e4ecfe6662699106ac44b008"},"tree":{"items":[{"name":"SelectionSampling.playground","path":"Selection Sampling/SelectionSampling.playground","contentType":"directory"},{"name":"README.markdown","path":"Selection Sampling/README.markdown","contentType":"file"},{"name":"SelectionSampling.swift","path":"Selection Sampling/SelectionSampling.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\"\u003eSelection Sampling\u003c/h1\u003e\u003ca id=\"user-content-selection-sampling\" class=\"anchor\" aria-label=\"Permalink: Selection Sampling\" href=\"#selection-sampling\"\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: Select \u003cem\u003ek\u003c/em\u003e items at random from a collection of \u003cem\u003en\u003c/em\u003e items.\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eLet's say you have a deck of 52 playing cards and you need to draw 10 cards at random. This algorithm lets you do that.\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eHere's a very fast version:\u003c/p\u003e\n\u003cdiv class=\"highlight highlight-source-swift notranslate position-relative overflow-auto\" dir=\"auto\" data-snippet-clipboard-copy-content=\"func select\u0026lt;T\u0026gt;(from a: [T], count k: Int) -\u0026gt; [T] {\n var a = a\n for i in 0..\u0026lt;k {\n let r = random(min: i, max: a.count - 1)\n if i != r {\n swap(\u0026amp;a[i], \u0026amp;a[r])\n }\n }\n return Array(a[0..\u0026lt;k])\n}\"\u003e\u003cpre\u003e\u003cspan class=\"pl-en\"\u003efunc\u003c/span\u003e select\u003cspan class=\"pl-c1\"\u003e\u0026lt;\u003c/span\u003eT\u003cspan class=\"pl-c1\"\u003e\u0026gt;\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003efrom a\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e[\u003c/span\u003e\u003cspan class=\"pl-smi\"\u003eT\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e]\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e count k\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\"\u003eT\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 a\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\u003ek \u003cspan class=\"pl-kos\"\u003e{\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003elet\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003er\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\u003emin\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e i\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e max\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e a\u003cspan class=\"pl-kos\"\u003e.\u003c/span\u003ecount \u003cspan class=\"pl-c1\"\u003e-\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e1\u003c/span\u003e\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 r \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\u003ea\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\u003ea\u003cspan class=\"pl-kos\"\u003e[\u003c/span\u003er\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-k\"\u003ereturn\u003c/span\u003e \u003cspan class=\"pl-en\"\u003eArray\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003e\u003cspan class=\"pl-en\"\u003ea\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e[\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e0\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e..\u0026lt;\u003c/span\u003ek\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\u003c/pre\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eAs often happens with these \u003ca href=\"/lighter/swift-algorithm-club/blob/master/Shuffle\"\u003ekinds of algorithms\u003c/a\u003e, it divides the array into two regions. The first region contains the selected items; the second region is all the remaining items.\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eHere's an example. Let's say the array is:\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\"\u003eWe want to select 3 items, so \u003ccode\u003ek = 3\u003c/code\u003e. In the loop, \u003ccode\u003ei\u003c/code\u003e is initially 0, so it points at \u003ccode\u003e\"a\"\u003c/code\u003e.\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; ]\n i\"\u003e\u003cpre class=\"notranslate\"\u003e\u003ccode\u003e[ \"a\", \"b\", \"c\", \"d\", \"e\", \"f\", \"g\" ]\n i\n\u003c/code\u003e\u003c/pre\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eWe calculate a random number between \u003ccode\u003ei\u003c/code\u003e and \u003ccode\u003ea.count\u003c/code\u003e, the size of the array. Let's say this is 4. Now we swap \u003ccode\u003e\"a\"\u003c/code\u003e with \u003ccode\u003e\"e\"\u003c/code\u003e, the element at index 4, and move \u003ccode\u003ei\u003c/code\u003e forward:\u003c/p\u003e\n\u003cdiv class=\"snippet-clipboard-content notranslate position-relative overflow-auto\" data-snippet-clipboard-copy-content=\"[ \u0026quot;e\u0026quot; | \u0026quot;b\u0026quot;, \u0026quot;c\u0026quot;, \u0026quot;d\u0026quot;, \u0026quot;a\u0026quot;, \u0026quot;f\u0026quot;, \u0026quot;g\u0026quot; ]\n i\"\u003e\u003cpre class=\"notranslate\"\u003e\u003ccode\u003e[ \"e\" | \"b\", \"c\", \"d\", \"a\", \"f\", \"g\" ]\n i\n\u003c/code\u003e\u003c/pre\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eThe \u003ccode\u003e|\u003c/code\u003e bar shows the split between the two regions. \u003ccode\u003e\"e\"\u003c/code\u003e is the first element we've selected. Everything to the right of the bar we still need to look at.\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eAgain, we ask for a random number between \u003ccode\u003ei\u003c/code\u003e and \u003ccode\u003ea.count\u003c/code\u003e, but because \u003ccode\u003ei\u003c/code\u003e has shifted, the random number can never be less than 1. So we'll never again swap \u003ccode\u003e\"e\"\u003c/code\u003e with anything.\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eLet's say the random number is 6 and we swap \u003ccode\u003e\"b\"\u003c/code\u003e with \u003ccode\u003e\"g\"\u003c/code\u003e:\u003c/p\u003e\n\u003cdiv class=\"snippet-clipboard-content notranslate position-relative overflow-auto\" data-snippet-clipboard-copy-content=\"[ \u0026quot;e\u0026quot; , \u0026quot;g\u0026quot; | \u0026quot;c\u0026quot;, \u0026quot;d\u0026quot;, \u0026quot;a\u0026quot;, \u0026quot;f\u0026quot;, \u0026quot;b\u0026quot; ]\n i\"\u003e\u003cpre class=\"notranslate\"\u003e\u003ccode\u003e[ \"e\" , \"g\" | \"c\", \"d\", \"a\", \"f\", \"b\" ]\n i\n\u003c/code\u003e\u003c/pre\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eOne more random number to pick, let's say it is 4 again. We swap \u003ccode\u003e\"c\"\u003c/code\u003e with \u003ccode\u003e\"a\"\u003c/code\u003e to get the final selection on the left:\u003c/p\u003e\n\u003cdiv class=\"snippet-clipboard-content notranslate position-relative overflow-auto\" data-snippet-clipboard-copy-content=\"[ \u0026quot;e\u0026quot;, \u0026quot;g\u0026quot;, \u0026quot;a\u0026quot; | \u0026quot;d\u0026quot;, \u0026quot;c\u0026quot;, \u0026quot;f\u0026quot;, \u0026quot;b\u0026quot; ]\"\u003e\u003cpre class=\"notranslate\"\u003e\u003ccode\u003e[ \"e\", \"g\", \"a\" | \"d\", \"c\", \"f\", \"b\" ]\n\u003c/code\u003e\u003c/pre\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eAnd that's it. Easy peasy. The performance of this function is \u003cstrong\u003eO(k)\u003c/strong\u003e because as soon as we've selected \u003cem\u003ek\u003c/em\u003e elements, we're done.\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eHere is an alternative algorithm, called \"reservoir sampling\":\u003c/p\u003e\n\u003cdiv class=\"highlight highlight-source-swift notranslate position-relative overflow-auto\" dir=\"auto\" data-snippet-clipboard-copy-content=\"func reservoirSample\u0026lt;T\u0026gt;(from a: [T], count k: Int) -\u0026gt; [T] {\n precondition(a.count \u0026gt;= k)\n\n var result = [T]() // 1\n for i in 0..\u0026lt;k {\n result.append(a[i])\n }\n\n for i in k..\u0026lt;a.count { // 2\n let j = random(min: 0, max: i)\n if j \u0026lt; k {\n result[j] = a[i]\n }\n }\n return result\n}\"\u003e\u003cpre\u003e\u003cspan class=\"pl-en\"\u003efunc\u003c/span\u003e reservoirSample\u003cspan class=\"pl-c1\"\u003e\u0026lt;\u003c/span\u003eT\u003cspan class=\"pl-c1\"\u003e\u0026gt;\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003efrom a\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e[\u003c/span\u003e\u003cspan class=\"pl-smi\"\u003eT\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e]\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e count k\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\"\u003eT\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e]\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e{\u003c/span\u003e\n \u003cspan class=\"pl-en\"\u003eprecondition\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003ea\u003cspan class=\"pl-kos\"\u003e.\u003c/span\u003ecount \u003cspan class=\"pl-c1\"\u003e\u0026gt;=\u003c/span\u003e k\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e\n\n \u003cspan class=\"pl-k\"\u003evar\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003eresult\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e[\u003c/span\u003eT\u003cspan class=\"pl-kos\"\u003e]\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e // 1\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\u003ek \u003cspan class=\"pl-kos\"\u003e{\u003c/span\u003e\n result\u003cspan class=\"pl-kos\"\u003e.\u003c/span\u003e\u003cspan class=\"pl-en\"\u003eappend\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003e\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-kos\"\u003e)\u003c/span\u003e\n \u003cspan class=\"pl-kos\"\u003e}\u003c/span\u003e\n\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 k\u003cspan class=\"pl-c1\"\u003e..\u0026lt;\u003c/span\u003ea\u003cspan class=\"pl-kos\"\u003e.\u003c/span\u003ecount \u003cspan class=\"pl-kos\"\u003e{\u003c/span\u003e // 2\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-en\"\u003erandom\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003emin\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e0\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e max\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e i\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003eif\u003c/span\u003e j \u003cspan class=\"pl-c1\"\u003e\u0026lt;\u003c/span\u003e k \u003cspan class=\"pl-kos\"\u003e{\u003c/span\u003e\n \u003cspan class=\"pl-en\"\u003eresult\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 \u003cspan class=\"pl-en\"\u003ea\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e[\u003c/span\u003ei\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-k\"\u003ereturn\u003c/span\u003e result\n\u003cspan class=\"pl-kos\"\u003e}\u003c/span\u003e\u003c/pre\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eThis works in two steps:\u003c/p\u003e\n\u003col dir=\"auto\"\u003e\n\u003cli\u003eFill the \u003ccode\u003eresult\u003c/code\u003e array with the first \u003ccode\u003ek\u003c/code\u003e elements from the original array. This is called the \"reservoir\".\u003c/li\u003e\n\u003cli\u003eRandomly replace elements in the reservoir with elements from the remaining pool.\u003c/li\u003e\n\u003c/ol\u003e\n\u003cp dir=\"auto\"\u003eThe performance of this algorithm is \u003cstrong\u003eO(n)\u003c/strong\u003e, so it's a little bit slower than the first algorithm. However, its big advantage is that it can be used for arrays that are too large to fit in memory, even if you don't know what the size of the array is (in Swift this might be something like a lazy generator that reads the elements from a file).\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eThere is one downside to the previous two algorithms: they do not keep the elements in the original order. In the input array \u003ccode\u003e\"a\"\u003c/code\u003e came before \u003ccode\u003e\"e\"\u003c/code\u003e but now it's the other way around. If that is an issue for your app, you can't use this particular method.\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eHere is an alternative approach that does keep the original order intact, but is a little more involved:\u003c/p\u003e\n\u003cdiv class=\"highlight highlight-source-swift notranslate position-relative overflow-auto\" dir=\"auto\" data-snippet-clipboard-copy-content=\"func select\u0026lt;T\u0026gt;(from a: [T], count requested: Int) -\u0026gt; [T] {\n var examined = 0\n var selected = 0\n var b = [T]()\n \n while selected \u0026lt; requested { // 1\n let r = Double(arc4random()) / 0x100000000 // 2\n \n let leftToExamine = a.count - examined // 3\n let leftToAdd = requested - selected\n\n if Double(leftToExamine) * r \u0026lt; Double(leftToAdd) { // 4\n selected += 1\n b.append(a[examined])\n }\n\n examined += 1\n }\n return b\n}\"\u003e\u003cpre\u003e\u003cspan class=\"pl-en\"\u003efunc\u003c/span\u003e select\u003cspan class=\"pl-c1\"\u003e\u0026lt;\u003c/span\u003eT\u003cspan class=\"pl-c1\"\u003e\u0026gt;\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003efrom a\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e[\u003c/span\u003e\u003cspan class=\"pl-smi\"\u003eT\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e]\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e count requested\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\"\u003eT\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\"\u003eexamined\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e0\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003evar\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003eselected\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e0\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003evar\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003eb\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e[\u003c/span\u003eT\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 \n \u003cspan class=\"pl-k\"\u003ewhile\u003c/span\u003e selected \u003cspan class=\"pl-c1\"\u003e\u0026lt;\u003c/span\u003e requested \u003cspan class=\"pl-kos\"\u003e{\u003c/span\u003e // 1\n \u003cspan class=\"pl-k\"\u003elet\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003er\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-en\"\u003eDouble\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003e\u003cspan class=\"pl-en\"\u003earc4random\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e/\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e0x100000000\u003c/span\u003e // 2\n \n \u003cspan class=\"pl-k\"\u003elet\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003eleftToExamine\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e a\u003cspan class=\"pl-kos\"\u003e.\u003c/span\u003ecount \u003cspan class=\"pl-c1\"\u003e-\u003c/span\u003e examined // 3\n \u003cspan class=\"pl-k\"\u003elet\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003eleftToAdd\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e requested \u003cspan class=\"pl-c1\"\u003e-\u003c/span\u003e selected\n\n \u003cspan class=\"pl-k\"\u003eif\u003c/span\u003e \u003cspan class=\"pl-en\"\u003eDouble\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003eleftToExamine\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e*\u003c/span\u003e r \u003cspan class=\"pl-c1\"\u003e\u0026lt;\u003c/span\u003e \u003cspan class=\"pl-en\"\u003eDouble\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003eleftToAdd\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e{\u003c/span\u003e // 4\n selected \u003cspan class=\"pl-c1\"\u003e+=\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e1\u003c/span\u003e\n b\u003cspan class=\"pl-kos\"\u003e.\u003c/span\u003e\u003cspan class=\"pl-en\"\u003eappend\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003e\u003cspan class=\"pl-en\"\u003ea\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e[\u003c/span\u003eexamined\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\n examined \u003cspan class=\"pl-c1\"\u003e+=\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e1\u003c/span\u003e\n \u003cspan class=\"pl-kos\"\u003e}\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003ereturn\u003c/span\u003e b\n\u003cspan class=\"pl-kos\"\u003e}\u003c/span\u003e\u003c/pre\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eThis algorithm uses probability to decide whether to include a number in the selection or not.\u003c/p\u003e\n\u003col dir=\"auto\"\u003e\n\u003cli\u003e\n\u003cp dir=\"auto\"\u003eThe loop steps through the array from beginning to end. It keeps going until we've selected \u003cem\u003ek\u003c/em\u003e items from our set of \u003cem\u003en\u003c/em\u003e. Here, \u003cem\u003ek\u003c/em\u003e is called \u003ccode\u003erequested\u003c/code\u003e and \u003cem\u003en\u003c/em\u003e is \u003ccode\u003ea.count\u003c/code\u003e.\u003c/p\u003e\n\u003c/li\u003e\n\u003cli\u003e\n\u003cp dir=\"auto\"\u003eCalculate a random number between 0 and 1. We want \u003ccode\u003e0.0 \u0026lt;= r \u0026lt; 1.0\u003c/code\u003e. The higher bound is exclusive; we never want it to be exactly 1. That's why we divide the result from \u003ccode\u003earc4random()\u003c/code\u003e by \u003ccode\u003e0x100000000\u003c/code\u003e instead of the more usual \u003ccode\u003e0xffffffff\u003c/code\u003e.\u003c/p\u003e\n\u003c/li\u003e\n\u003cli\u003e\n\u003cp dir=\"auto\"\u003e\u003ccode\u003eleftToExamine\u003c/code\u003e is how many items we still haven't looked at. \u003ccode\u003eleftToAdd\u003c/code\u003e is how many items we still need to select before we're done.\u003c/p\u003e\n\u003c/li\u003e\n\u003cli\u003e\n\u003cp dir=\"auto\"\u003eThis is where the magic happens. Basically, we're flipping a coin. If it was heads, we add the current array element to the selection; if it was tails, we skip it.\u003c/p\u003e\n\u003c/li\u003e\n\u003c/ol\u003e\n\u003cp dir=\"auto\"\u003eInterestingly enough, even though we use probability, this approach always guarantees that we end up with exactly \u003cem\u003ek\u003c/em\u003e items in the output array.\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eLet's walk through the same example again. The input array is:\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 looks at each element in turn, so we start at \u003ccode\u003e\"a\"\u003c/code\u003e. We get a random number between 0 and 1, let's say it is 0.841. The formula at \u003ccode\u003e// 4\u003c/code\u003e multiplies the number of items left to examine with this random number. There are still 7 elements left to examine, so the result is:\u003c/p\u003e\n\u003cdiv class=\"snippet-clipboard-content notranslate position-relative overflow-auto\" data-snippet-clipboard-copy-content=\"7 * 0.841 = 5.887\"\u003e\u003cpre class=\"notranslate\"\u003e\u003ccode\u003e7 * 0.841 = 5.887\n\u003c/code\u003e\u003c/pre\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eWe compare this to 3 because we wanted to select 3 items. Since 5.887 is greater than 3, we skip \u003ccode\u003e\"a\"\u003c/code\u003e and move on to \u003ccode\u003e\"b\"\u003c/code\u003e.\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eAgain, we get a random number, let's say 0.212. Now there are only 6 elements left to examine, so the formula gives:\u003c/p\u003e\n\u003cdiv class=\"snippet-clipboard-content notranslate position-relative overflow-auto\" data-snippet-clipboard-copy-content=\"6 * 0.212 = 1.272\"\u003e\u003cpre class=\"notranslate\"\u003e\u003ccode\u003e6 * 0.212 = 1.272\n\u003c/code\u003e\u003c/pre\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eThis \u003cem\u003eis\u003c/em\u003e less than 3 and we add \u003ccode\u003e\"b\"\u003c/code\u003e to the selection. This is the first item we've selected, so two left to go.\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eOn to the next element, \u003ccode\u003e\"c\"\u003c/code\u003e. The random number is 0.264, giving the result:\u003c/p\u003e\n\u003cdiv class=\"snippet-clipboard-content notranslate position-relative overflow-auto\" data-snippet-clipboard-copy-content=\"5 * 0.264 = 1.32\"\u003e\u003cpre class=\"notranslate\"\u003e\u003ccode\u003e5 * 0.264 = 1.32\n\u003c/code\u003e\u003c/pre\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eThere are only 2 elements left to select, so this number must be less than 2. It is, and we also add \u003ccode\u003e\"c\"\u003c/code\u003e to the selection. The total selection is \u003ccode\u003e[ \"b\", \"c\" ]\u003c/code\u003e.\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eOnly one item left to select but there are still 4 candidates to look at. Suppose the next random number is 0.718. The formula now gives:\u003c/p\u003e\n\u003cdiv class=\"snippet-clipboard-content notranslate position-relative overflow-auto\" data-snippet-clipboard-copy-content=\"4 * 0.718 = 2.872\"\u003e\u003cpre class=\"notranslate\"\u003e\u003ccode\u003e4 * 0.718 = 2.872\n\u003c/code\u003e\u003c/pre\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eFor this element to be selected the number has to be less than 1, as there is only 1 element left to be picked. It isn't, so we skip \u003ccode\u003e\"d\"\u003c/code\u003e. Only three possibilities left -- will we make it before we run out of elements?\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eThe random number is 0.346. The formula gives:\u003c/p\u003e\n\u003cdiv class=\"snippet-clipboard-content notranslate position-relative overflow-auto\" data-snippet-clipboard-copy-content=\"3 * 0.346 = 1.038\"\u003e\u003cpre class=\"notranslate\"\u003e\u003ccode\u003e3 * 0.346 = 1.038\n\u003c/code\u003e\u003c/pre\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eJust a tiny bit too high. We skip \u003ccode\u003e\"e\"\u003c/code\u003e. Only two candidates left...\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eNote that now literally we're dealing with a coin toss: if the random number is less than 0.5 we select \u003ccode\u003e\"f\"\u003c/code\u003e and we're done. If it's greater than 0.5, we go on to the final element. Let's say we get 0.583:\u003c/p\u003e\n\u003cdiv class=\"snippet-clipboard-content notranslate position-relative overflow-auto\" data-snippet-clipboard-copy-content=\"2 * 0.583 = 1.166\"\u003e\u003cpre class=\"notranslate\"\u003e\u003ccode\u003e2 * 0.583 = 1.166\n\u003c/code\u003e\u003c/pre\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eWe skip \u003ccode\u003e\"f\"\u003c/code\u003e and look at the very last element. Whatever random number we get here, it should always select \u003ccode\u003e\"g\"\u003c/code\u003e or we won't have selected enough elements and the algorithm doesn't work!\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eLet's say our final random number is 0.999 (remember, it can never be 1.0 or higher). Actually, no matter what we choose here, the formula will always give a value less than 1:\u003c/p\u003e\n\u003cdiv class=\"snippet-clipboard-content notranslate position-relative overflow-auto\" data-snippet-clipboard-copy-content=\"1 * 0.999 = 0.999\"\u003e\u003cpre class=\"notranslate\"\u003e\u003ccode\u003e1 * 0.999 = 0.999\n\u003c/code\u003e\u003c/pre\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eAnd so the last element will always be chosen if we didn't have a big enough selection yet. The final selection is \u003ccode\u003e[ \"b\", \"c\", \"g\" ]\u003c/code\u003e. Notice that the elements are still in their original order, because we examined the array from left to right.\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eMaybe you're not convinced yet... What if we always got 0.999 as the random value (the maximum possible), would that still select 3 items? Well, let's do the math:\u003c/p\u003e\n\u003cdiv class=\"snippet-clipboard-content notranslate position-relative overflow-auto\" data-snippet-clipboard-copy-content=\"7 * 0.999 = 6.993 is this less than 3? no\n6 * 0.999 = 5.994 is this less than 3? no\n5 * 0.999 = 4.995 is this less than 3? no\n4 * 0.999 = 3.996 is this less than 3? no\n3 * 0.999 = 2.997 is this less than 3? YES\n2 * 0.999 = 1.998 is this less than 2? YES\n1 * 0.999 = 0.999 is this less than 1? YES\"\u003e\u003cpre class=\"notranslate\"\u003e\u003ccode\u003e7 * 0.999 = 6.993 is this less than 3? no\n6 * 0.999 = 5.994 is this less than 3? no\n5 * 0.999 = 4.995 is this less than 3? no\n4 * 0.999 = 3.996 is this less than 3? no\n3 * 0.999 = 2.997 is this less than 3? YES\n2 * 0.999 = 1.998 is this less than 2? YES\n1 * 0.999 = 0.999 is this less than 1? YES\n\u003c/code\u003e\u003c/pre\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eIt always works! But does this mean that elements closer to the end of the array have a higher probability of being chosen than those in the beginning? Nope, all elements are equally likely to be selected. (Don't take my word for it: see the playground for a quick test that shows this in practice.)\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eHere's an example of how to test this algorithm:\u003c/p\u003e\n\u003cdiv class=\"highlight highlight-source-swift notranslate position-relative overflow-auto\" dir=\"auto\" data-snippet-clipboard-copy-content=\"let input = [\n \u0026quot;there\u0026quot;, \u0026quot;once\u0026quot;, \u0026quot;was\u0026quot;, \u0026quot;a\u0026quot;, \u0026quot;man\u0026quot;, \u0026quot;from\u0026quot;, \u0026quot;nantucket\u0026quot;,\n \u0026quot;who\u0026quot;, \u0026quot;kept\u0026quot;, \u0026quot;all\u0026quot;, \u0026quot;of\u0026quot;, \u0026quot;his\u0026quot;, \u0026quot;cash\u0026quot;, \u0026quot;in\u0026quot;, \u0026quot;a\u0026quot;, \u0026quot;bucket\u0026quot;,\n \u0026quot;his\u0026quot;, \u0026quot;daughter\u0026quot;, \u0026quot;named\u0026quot;, \u0026quot;nan\u0026quot;,\n \u0026quot;ran\u0026quot;, \u0026quot;off\u0026quot;, \u0026quot;with\u0026quot;, \u0026quot;a\u0026quot;, \u0026quot;man\u0026quot;,\n \u0026quot;and\u0026quot;, \u0026quot;as\u0026quot;, \u0026quot;for\u0026quot;, \u0026quot;the\u0026quot;, \u0026quot;bucket\u0026quot;, \u0026quot;nan\u0026quot;, \u0026quot;took\u0026quot;, \u0026quot;it\u0026quot;,\n]\n\nlet output = select(from: input, count: 10)\nprint(output)\nprint(output.count)\"\u003e\u003cpre\u003e\u003cspan class=\"pl-k\"\u003elet\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003einput\u003c/span\u003e \u003cspan cla
73D7
ss=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e[\u003c/span\u003e\n \u003cspan class=\"pl-s\"\u003e\"\u003c/span\u003e\u003cspan class=\"pl-s\"\u003ethere\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\"\u003eonce\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\"\u003ewas\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\"\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\"\u003eman\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\"\u003efrom\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\"\u003enantucket\u003c/span\u003e\u003cspan class=\"pl-s\"\u003e\"\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e\n \u003cspan class=\"pl-s\"\u003e\"\u003c/span\u003e\u003cspan class=\"pl-s\"\u003ewho\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\"\u003ekept\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\"\u003eall\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\"\u003eof\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\"\u003ehis\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\"\u003ecash\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\"\u003ein\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\"\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\"\u003ebucket\u003c/span\u003e\u003cspan class=\"pl-s\"\u003e\"\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e\n \u003cspan class=\"pl-s\"\u003e\"\u003c/span\u003e\u003cspan class=\"pl-s\"\u003ehis\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\"\u003edaughter\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\"\u003enamed\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\"\u003enan\u003c/span\u003e\u003cspan class=\"pl-s\"\u003e\"\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e\n \u003cspan class=\"pl-s\"\u003e\"\u003c/span\u003e\u003cspan class=\"pl-s\"\u003eran\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\"\u003eoff\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\"\u003ewith\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\"\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\"\u003eman\u003c/span\u003e\u003cspan class=\"pl-s\"\u003e\"\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e\n \u003cspan class=\"pl-s\"\u003e\"\u003c/span\u003e\u003cspan class=\"pl-s\"\u003eand\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\"\u003eas\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\"\u003efor\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\"\u003ethe\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\"\u003ebucket\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\"\u003enan\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\"\u003etook\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\"\u003eit\u003c/span\u003e\u003cspan class=\"pl-s\"\u003e\"\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e\n\u003cspan class=\"pl-kos\"\u003e]\u003c/span\u003e\n\n\u003cspan class=\"pl-k\"\u003elet\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003eoutput\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-en\"\u003eselect\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003efrom\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e input\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e count\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e10\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e\n\u003cspan class=\"pl-en\"\u003eprint\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003eoutput\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e\n\u003cspan class=\"pl-en\"\u003eprint\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003eoutput\u003cspan class=\"pl-kos\"\u003e.\u003c/span\u003ecount\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e\u003c/pre\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eThe performance of this second algorithm is \u003cstrong\u003eO(n)\u003c/strong\u003e as it may require a pass through the entire input array.\u003c/p\u003e\n\u003cblockquote\u003e\n\u003cp dir=\"auto\"\u003e\u003cstrong\u003eNote:\u003c/strong\u003e If \u003ccode\u003ek \u0026gt; n/2\u003c/code\u003e, then it's more efficient to do it the other way around and choose \u003ccode\u003ea.count - k\u003c/code\u003e items to remove.\u003c/p\u003e\n\u003c/blockquote\u003e\n\u003cp dir=\"auto\"\u003eBased on code from Algorithm Alley, Dr. Dobb's Magazine, October 1993.\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":"Selection Sampling","anchor":"selection-sampling","htmlText":"Selection Sampling"}],"siteNavLoginPath":"/login?return_to=https%3A%2F%2Fgithub.com%2Flighter%2Fswift-algorithm-club%2Ftree%2Fmaster%2FSelection%2520Sampling"}},"totalCount":3,"showBranchInfobar":true},"fileTree":{"":{"items":[{"name":".github","path":".github","contentType":"directory"},{"name":"3Sum and 4Sum","path":"3Sum and 4Sum","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":"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","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":118}},"fileTreeProcessingTime":3.9137160000000004,"foldersToFetch":[],"treeExpanded":true,"symbolsExpanded":false,"csrf_tokens":{"/lighter/swift-algorithm-club/branches":{"post":"oz6MWm5s5R1m0yvMPbnZtGz33-KJkk7stkH9b-5G4HmyALnSWCeiGtYTAO26h9OXk8zfvDK75K07jlK8fRSfPw"},"/lighter/swift-algorithm-club/branches/fetch_and_merge/master":{"post":"7jnpFNyabZOiUfL4RvOWGT3I5QRDP_08BuYyasKNdkNXGCdAzDtPy_-MBrdBYRSmt3xG2jWKyBQWXGUoa4g_UQ"},"/lighter/swift-algorithm-club/branches/fetch_and_merge/master?discard_changes=true":{"post":"12S_aSL5zhKbaz58qb-znLRMGb_MRoJ3Us6-mcZgzHZuRXE9MljsSsa2yjOuLTEjPvi6Ybrzt19CdOnbb2WFZA"}}},"title":"swift-algorithm-club/Selection Sampling at master · lighter/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-1b17b3e7786a.js","githubDevUrl":null,"enabled_features":{"code_nav_ui_events":false,"react_blob_overlay":false,"accessible_code_button":true}}}