combination_algorithms.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "Use a hacked together benchmarking function using System.Diagnostics.Stopwatch to measure the speed of various algorithms to produce combinations of lists (from http://stackoverflow.com/questions/4528355/measure-time-of-execution-in-f) \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "let bench note f =\n",
    "    let sw = System.Diagnostics.Stopwatch.StartNew()\n",
    "    let res = f 2 [1..1000]\n",
    "    sw.Stop()\n",
    "    printfn \"%s: %f ms\" note sw.Elapsed.TotalMilliseconds\n",
    "    res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "collapsed": true,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "// by user \"kvb\"\n",
    "let rec kvb_comb n l =\n",
    "  match (n,l) with\n",
    "  | (0,_) -> [[]]\n",
    "  | (_,[]) -> []\n",
    "  | (n,x::xs) ->\n",
    "      let useX = List.map (fun l -> x::l) (comb_kvb (n-1) xs)\n",
    "      let noX = kvb_comb n xs\n",
    "      useX @ noX\n",
    "\n",
    "// by user \"The_Ghost\"\n",
    "let rec ghost_comb n l = \n",
    "    match n, l with\n",
    "    | 0, _ -> [[]]\n",
    "    | _, [] -> []\n",
    "    | k, (x::xs) -> List.map ((@) [x]) (ghost_comb (k-1) xs) @ ghost_comb k xs\n",
    "\n",
    "// by user \"Ray\" (first attempt)\n",
    "let ray_1_comb _ lst =\n",
    "    let combHelper el lst =\n",
    "        lst |> List.map (fun lstEl -> el::[lstEl])\n",
    "    let filterOut el lst =\n",
    "        lst |> List.filter (fun lstEl -> lstEl <> el)\n",
    "    lst |> List.map (fun lstEl -> combHelper lstEl (filterOut lstEl lst)) |> List.concat\n",
    "\n",
    "// by user \"Ray\" (second attempt)\n",
    "let rec ray_2_comb n lst =\n",
    "    let rec findChoices = function\n",
    "      | h::t -> (h,t) :: [ for (x,l) in findChoices t -> (x,l) ]\n",
    "      | []   -> []\n",
    "    [ if n=0 then yield [] else\n",
    "            for (e,r) in findChoices lst do\n",
    "                for o in ray_2_comb (n-1) r do yield e::o  ]\n",
    "\n",
    "// by user \"Bill Johnson\"\n",
    "let bill_comb size aList = \n",
    "    let rec pairHeadAndTail acc bList = \n",
    "        match bList with\n",
    "        | [] -> acc\n",
    "        | x::xs -> pairHeadAndTail (List.Cons ((x,xs),acc)) xs\n",
    "    let remainderAfter = aList |> pairHeadAndTail [] |> Map.ofList\n",
    "    let rec comboIter n acc = \n",
    "        match n with\n",
    "        | 0 -> acc\n",
    "        | _ -> \n",
    "            acc\n",
    "            |> List.fold (fun acc alreadyChosenElems ->\n",
    "                match alreadyChosenElems with\n",
    "                | [] -> aList //Nothing chosen yet, therefore everything remains.\n",
    "                | lastChoice::_ -> remainderAfter.[lastChoice]\n",
    "                |> List.fold (fun acc elem ->\n",
    "                    List.Cons (List.Cons (elem,alreadyChosenElems),acc)\n",
    "                ) acc\n",
    "            ) []\n",
    "            |> comboIter (n-1)\n",
    "    comboIter size [[]]\n",
    "\n",
    "// by user \"mitzsh\"\n",
    "let mitzsh_comb (k : int) (xs : 'a list) : ('a list) seq =\n",
    "    let rec loop (k : int) (xs : 'a list) : ('a list) seq = seq {\n",
    "        match xs with\n",
    "        | [] -> ()\n",
    "        | xs when k = 1 -> for x in xs do yield [x]\n",
    "        | x::xs ->\n",
    "            let k' = k - 1\n",
    "            for ys in loop k' xs do\n",
    "                yield x :: ys\n",
    "            yield! loop k xs }\n",
    "    loop k xs\n",
    "    |> Seq.filter (List.length >> (=)k)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "kvb_comb: 715.447900 ms\n",
       "ghost_comb: 803.832400 ms\n",
       "ray_1_comb: 905.011200 ms\n",
       "ray_2_comb: 61125.410800 ms\n",
       "bill_comb: 304.491400 ms\n",
       "mitzsh_comb: 0.656500 ms\n"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": []
    }
   ],
   "source": [
    "// executing the test\n",
    "let kvb_res = bench \"kvb_comb\" kvb_comb\n",
    "let ghost = bench \"ghost_comb\" ghost_comb\n",
    "let ray_1 = bench \"ray_1_comb\" ray_1_comb\n",
    "let ray_2 = bench \"ray_2_comb\" ray_2_comb\n",
    "let bill_res = bench \"bill_comb\" bill_comb\n",
    "let mitzsh_res = bench \"mitzsh_comb\" mitzsh_comb"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "F#",
   "language": "fsharp",
   "name": "ifsharp"
  },
  "language": "fsharp",
  "language_info": {
   "codemirror_mode": "",
   "file_extension": ".fs",
   "mimetype": "text/x-fsharp",
   "name": "fsharp",
   "nbconvert_exporter": "",
   "pygments_lexer": "",
   "version": "4.3.1.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}