CODEWITHSUNDEEP
javascriptarraysmathdivide-and-conquer
Chris
Chris

Reputation: 336

JavaScript Array Division

I am trying to create a recursive function to splice an array in half until it only has lengths of 3 and 2, than to have all these new arrays neatly placed in an array.

I think I need a way to measure how many arrays I will need, create them and then throw them in my divided up arrays? (I was thinking Pow?).

I am using half and Round as I have experimented on paper and this means that I will end up with 2's and 3's, rather than dividing by 3's as it comes up with a remainder of 1 sometimes (and I am planning to use the same script to build triangulation later on with this data).

Current code, (incomplete, for this to work would have to continue creating additional if statements).

var pointlist = [];
var pointCount = 666;

var generate = function(t, n) {
  for (count = 0; count < n; count++) {
    var point = {
      x: (Math.random() * 1000),
      y: (Math.random() * 1000)
    };

    t.push(point);
  }
}

generate(pointlist, pointCount);
var divisions = [];
var divide = function(a) {
  a.sort(function(a, b) {
    return a.x - b.x
  });
  if (a.length > 3) {
    b = a.splice(Math.round(a.length / 2), a.length);
    divisions.push(a, b);
    if (a.length > 3) {
      c = a.splice(Math.round(a.length / 2), a.length);
      d = b.splice(Math.round(b.length / 2), b.length);
      divisions = [];
      divisions.push(a, c, b, d);
      if (a.length > 3) {
        e = a.splice(Math.round(a.length / 2), a.length);
        f = c.splice(Math.round(c.length / 2), c.length);
        g = b.splice(Math.round(b.length / 2), b.length);
        h = d.splice(Math.round(d.length / 2), d.length);
        divisions = [];
        divisions.push(a, e, c, f, b, g, d, g);
      }
    }
  }
};
divide(pointlist);
console.log(divisions.length + " arrays");
console.log(divisions[0].length + " first length");
console.log(divisions[1].length + " second length");

Upvotes: 1

Views: 2867

Answers (2)

Redu
Redu

Reputation: 26191

Not recursive but with the help of a useless Array method called Array.prototype.bisect() may be you can do something as follows;

Array.prototype.bisect = function(){
  var atIndex = Math.round(this.length/2);
  return [this.slice(0,atIndex),this.slice(atIndex)];
};
var arr = [0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19],
    brr = [];
function breakUp(arr){
  while (arr[0].length > 3) arr = [].concat(...arr.map(a => a.length > 3 && a.bisect()));
  return arr;
}
brr = breakUp([arr]);
console.log(JSON.stringify(brr));

Upvotes: 0

trincot
trincot

Reputation: 350776

Here is a recursive function, excluding the sorting which should only happen once:

var pointlist = [];
var pointCount = 666;

var generate = function(t, n) {
  for (count = 0; count < n; count++) {
    var point = {
      x: Math.floor(Math.random() * 1000),
      y: Math.floor(Math.random() * 1000)
    };

    t.push(point);
  }
}

generate(pointlist, pointCount);

var divide = function(a) {
  a.sort(function(a, b) {
    return a.x - b.x
  });
  function recurseDivide(a) {
    if (a.length <= 3) return [a];
    var b = a.splice(Math.round(a.length / 2), a.length);
    return recurseDivide(a).concat(recurseDivide(b));
  }
  return recurseDivide(a);
};
var divisions = divide(pointlist);
console.log(divisions.length + " arrays");
console.log(divisions[0].length + " first length");
console.log(divisions[1].length + " second length");</script>

Be aware that after the call to divide, the variable pointlist will have mutated. If you want to avoid this, make the call like this:

var divisions = divide(pointlist.slice());

Upvotes: 1

Related Questions