**Updated on 2016-01-17**: note that the algorithms (or lack thereof) here have been superseded in Part 3.Continuing from Part 1, it's time to prepare the list of arithmetic operators.

## Generating Operators List

So we can generate list of numbers of various size, now we need to insert all the possible arithmetic operators between each pair of numbers. The requirement of generating operators list is a little different from numbers list: operators can be repeated - e.g. with 3 numbers in the list [n1, n2, n3] we can test n1+n2+n3 where the plus ('+') operator has been repeated in the expression.This means that we cannot use the

`k_combinations()`

function used for numbers generation. In stead I had to tweak it a little, and call it k_com as shown below:function k_com(set, k) { var i, j, combs, head, tailcombs; if (k > set.length || k <= 0) { return []; } if (k == set.length) { return [set]; } if (k == 1) { combs = []; for (i = 0; i < set.length; i++) { var item=[set[i]]; if(checkDup(combs, item)==false){ combs.push(item); } } return combs; } combs = []; for (i = 0; i < set.length - k + 1; i++) { head = set.slice(i, i+1); tailcombs = k_com(set, k - 1); for (j = 0; j < tailcombs.length; j++) { var item=head.concat(tailcombs[j]); if(checkDup(combs, item)==false) { combs.push(item); } } } return combs; } /* * set is [[], [], []] * item is just an [object] * checks if item is already in the set * returns dup=true; no dup=false */ function checkDup(set, item) { for (var i in set) { var src=set[i]; // assert.deepEqual(src, item) if(src.length == item.length) { var matched=true; for(var j=0; j<src.length; j++) { matched=matched && src[j]==item[j]; if(!matched) break; } if (matched) return true; } } return false; }There are a few problems with

`k_com()`

:- since it uses head and tail recursion approach, the last element of the array will be missed
- since operators are repeatable, it's not just a combination algorithm, but also involves permutation
- when there are more spaces than operators - e.g. 6 numbers require 5 operators, then this algorithm does not work.

So the

`getOps()`

function looks like below. I wish JS supports Ruby (or was it Erlang?) syntax of repeating arrays by overloading the '*' operator.function getOps(k) { var ops=["+", "-", "*", "/"]; var i=k; var r=[] while (i--) { r=r.concat(ops); } return k_com(r, k); }

The complexity of this algorithm is probably O(n!) which is quite bad. Fortunately in Numbers Game, the maximum number for k is 5. The performance of

`getOps()`

running in V8 that came with Node.js is shown below:> var then=new Date(); ops=getOps(2); var now=new Date(); console.log(("%d takes %d ms"),ops.length,now-then) 64 takes 2 ms undefined > var then=new Date(); ops=getOps(4); var now=new Date(); console.log(("%d takes %d ms"),ops.length,now-then) 256 takes 107 ms undefined > var then=new Date(); ops=getOps(5); var now=new Date(); console.log(("%d takes %d ms"),ops.length,now-then) 1024 takes 4185 ms undefined

## No comments:

Post a Comment