{"id":693,"date":"2009-02-09T11:56:35","date_gmt":"2009-02-09T10:56:35","guid":{"rendered":"http:\/\/www.navision-blog.de\/2009\/02\/09\/finding-the-m-smallest-elements-in-a-collection-in-f\/"},"modified":"2009-02-09T12:00:43","modified_gmt":"2009-02-09T11:00:43","slug":"finding-the-m-smallest-elements-in-a-collection-in-fsharp","status":"publish","type":"post","link":"http:\/\/www.navision-blog.de\/blog\/2009\/02\/09\/finding-the-m-smallest-elements-in-a-collection-in-fsharp\/","title":{"rendered":"Finding the m smallest elements in a collection in F#"},"content":{"rendered":"<p>Sometimes we need a function which finds the m smallest elements in a list or array.<\/p>\n<p>We can use the idea of bubble sort to maintain an sorted array of the m smallest elements so far. This idea gives us a O(m*n) algorithm which solves our problem:<\/p>\n<pre class=\"code\"><span style=\"color: blue\">let <\/span>bubble array element =\n  <span style=\"color: blue\">let rec <\/span>bubbleStep i =\n    <span style=\"color: blue\">if <\/span>i &lt; (array |&gt; Array.length) <span style=\"color: blue\">then\n      match <\/span>array.[i] <span style=\"color: blue\">with\n        <\/span>| None <span style=\"color: blue\">-&gt; \n           if <\/span>i = array.Length - 1 || array.[i+1] &lt;&gt; None <span style=\"color: blue\">then\n             <\/span>array.[i] &lt;- Some element\n                          \n           bubbleStep (i+1)\n        | Some x <span style=\"color: blue\">-&gt; \n           if <\/span>element &lt; x <span style=\"color: blue\">then\n             if <\/span>i = 0 <span style=\"color: blue\">then \n               <\/span>array.[i] &lt;- Some element \n             <span style=\"color: blue\">else\n               <\/span>array.[i-1] &lt;- Some x\n               array.[i] &lt;- Some element\n             bubbleStep (i+1)\n  \n  bubbleStep 0\n  array    \n  \n<span style=\"color: blue\">let <\/span>mMin seq m =\n  Seq.fold bubble (Array.create m None) seq<\/pre>\n<p>We can easily generalize this function to compute maximum and minimum:<\/p>\n<pre class=\"code\"><span style=\"color: blue\">let <\/span>bubble <strong>f<\/strong> array element =\n  <span style=\"color: blue\">let rec <\/span>bubbleStep i =\n    <span style=\"color: blue\">if <\/span>i &lt; (array |&gt; Array.length) <span style=\"color: blue\">then\n      match <\/span>array.[i] <span style=\"color: blue\">with\n        <\/span>| None <span style=\"color: blue\">-&gt; \n           if <\/span>i = array.Length - 1 || array.[i+1] &lt;&gt; None <span style=\"color: blue\">then\n             <\/span>array.[i] &lt;- Some element\n                          \n           bubbleStep (i+1)\n        | Some x <span style=\"color: blue\">-&gt; \n           if <\/span><strong>f element x<\/strong> <span style=\"color: blue\">then\n             if <\/span>i = 0 <span style=\"color: blue\">then \n               <\/span>array.[i] &lt;- Some element \n             <span style=\"color: blue\">else\n               <\/span>array.[i-1] &lt;- Some x\n               array.[i] &lt;- Some element\n             bubbleStep (i+1)\n  \n  bubbleStep 0\n  array    \n    \n<span style=\"color: blue\">let <\/span>mBubble f seq m =\n  Seq.fold (bubble f) (Array.create m None) seq\n  \n<span style=\"color: blue\">let <\/span>mMin seq m = mBubble (&lt;) seq m\n<span style=\"color: blue\">let <\/span>mMax seq m = mBubble (&gt;) seq m<\/pre>\n<p>If we don\u2019t want to store Option-Values we can use this simplification:<\/p>\n<pre class=\"code\"><span style=\"color: blue\">let <\/span>bubble f m array element =\n  <span style=\"color: blue\">let rec <\/span>bubbleStep i =\n    <span style=\"color: blue\">if <\/span>i &lt; (array |&gt; Array.length) <span style=\"color: blue\">then\n      let <\/span>x = array.[i]\n      <span style=\"color: blue\">if <\/span>f element x <span style=\"color: blue\">then\n         if <\/span>i = 0 <span style=\"color: blue\">then \n           <\/span>array.[i] &lt;- element \n         <span style=\"color: blue\">else\n           <\/span>array.[i-1] &lt;- x\n           array.[i] &lt;- element\n         bubbleStep (i+1)\n  \n  <span style=\"color: blue\">if <\/span>Array.length array &lt; m <span style=\"color: blue\">then\n    let <\/span>newArray = Array.append [|element|] array \n    newArray \n      |&gt; Array.sort \n          (<span style=\"color: blue\">fun <\/span>a b <span style=\"color: blue\">-&gt; \n            if <\/span>a = b <span style=\"color: blue\">then <\/span>0 \n            <span style=\"color: blue\">elif <\/span>f a b <span style=\"color: blue\">then <\/span>1 <span style=\"color: blue\">else <\/span>-1)\n    newArray\n  <span style=\"color: blue\">else\n    <\/span>bubbleStep 0\n    array    \n    \n<span style=\"color: blue\">let <\/span>mBubble f seq m =    \n  Seq.fold (bubble f m) Array.empty seq\n  \n<span style=\"color: blue\">let <\/span>mMin seq m = mBubble (&lt;) seq m\n<span style=\"color: blue\">let <\/span>mMax seq m = mBubble (&gt;) seq m<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>Sometimes we need a function which finds the m smallest elements in a list or array. We can use the idea of bubble sort to maintain an sorted array of the m smallest elements so far. This idea gives us a O(m*n) algorithm which solves our problem: let bubble array element = let rec bubbleStep [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[23,448,8],"tags":[523],"_links":{"self":[{"href":"http:\/\/www.navision-blog.de\/blog\/wp-json\/wp\/v2\/posts\/693"}],"collection":[{"href":"http:\/\/www.navision-blog.de\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.navision-blog.de\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.navision-blog.de\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/www.navision-blog.de\/blog\/wp-json\/wp\/v2\/comments?post=693"}],"version-history":[{"count":2,"href":"http:\/\/www.navision-blog.de\/blog\/wp-json\/wp\/v2\/posts\/693\/revisions"}],"predecessor-version":[{"id":695,"href":"http:\/\/www.navision-blog.de\/blog\/wp-json\/wp\/v2\/posts\/693\/revisions\/695"}],"wp:attachment":[{"href":"http:\/\/www.navision-blog.de\/blog\/wp-json\/wp\/v2\/media?parent=693"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.navision-blog.de\/blog\/wp-json\/wp\/v2\/categories?post=693"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.navision-blog.de\/blog\/wp-json\/wp\/v2\/tags?post=693"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}