JavaScript Array Division

Question

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");

What's the input & output you're after? (not the algorithm, calculation and so on, the arrays you want to splice) — Amit
– Amit, Commented Jun 13, 2016 at 22:29
I want to splice pointlist array and insert them into the divisions array, keeping them in the order created by the sort function. — Chris
– Chris, Commented Jun 13, 2016 at 22:32
Specific and accurate input and output samples please, description is not helpful. — Amit
– Amit, Commented Jun 13, 2016 at 22:33
I don't see any recursive function in your code and I'm not sure what exactly you're trying to do, But this may help as an example of proccessing an array by divide and conquer algorithm in Javascript: mgechev.github.io/javascript-algorithms/… — Hafez Divandari
– Hafez Divandari, Commented Jun 13, 2016 at 22:40
I have an array called pointlist, it contains point objects. I would like to divide the pointlist array in half using splice until those new arrays are no greater than 3 length each (3 or 2 objects in each). Than I would like to insert those arrays, in order, into a pre-made array called divisions. In either order it would work best. — Chris
– Chris, Commented Jun 13, 2016 at 22:43

trincot · Accepted Answer · 2016-06-13 22:54:50Z

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());

Redu · Accepted Answer · 2016-06-14 05:12:58Z

0

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));

answered Jun 14, 2016 at 5:12

Redu

26.3k6 gold badges61 silver badges84 bronze badges

Collectives™ on Stack Overflow

JavaScript Array Division

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related