1

So say I have an array l:

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24]

which holds some set of values, in this case integers. And I have another array m:

[2, 3, 2]

which holds divisors (I'll explain what I mean by divisor later). What I would like to do is successively divide l into slices based on the current value in m. So in this example, I'd first divide it into 2 lists (m[0] is 2) of equal size:

[[1,2,3,4,5,6,7,8,9,10,11,12], [13,14,15,16,17,18,19,20,21,22,23,24]]

Then divide those lists into 3 (m[1] is 3) lists, yielding:

[[[1,2,3,4],[5,6,7,8],[9,10,11,12]], [[13,14,15,16],[17,18,19,20],[21,22,23,24]]]

Then finally divide each of those lists into 2 lists (m[2] is 2):

[[[[1,2],[3,4]],[[5,6],[7,8]],[[9,10],[11,12]]],[[[13,14],[15,16]],[[17,18],[19,20]],[[21,22],[23,24]]]]

In the actual implementation of this, m will be of an arbitrary length and have arbitrary values.

Is there an existing algorithm that accomplishes this? This will basically be a tree structure, as each list that results from a division will receive a label, but I'm not sure how to implement a function that will return the list I need. I'm implementing in Javascript, but the algorithm is what's important here.

Gerald Shaeffer
  • 33
  • 2
  • 7
  • I do not see any tree structure here, What should happen if array length is smaller then divider size? – MaxZoom May 13 '15 at 22:00
  • @MaxZoom I probably should've been more clear; all elements that were in the first 2 list will receive a label and will retain that label through all divisions. So 1-12 will have a label 'a', and 13-24 will have a label 'b', and in the next step, 1-4 will have label 'c', 5-8, will have label 'd', and so on. Be tree I mean the structure has nodes and is hierarchical. – Gerald Shaeffer May 13 '15 at 22:05

2 Answers2

3

Try out this code. It splits the array recursively.

function split(arr, n) {
  if(n <= 1) return [arr];
  var partLength = Math.ceil(arr.length/n),
      part1 = arr.slice(0, partLength),
      result = split(arr.slice(partLength), n - 1);
  result.unshift(part1);
  return result;
}

function splitTree(arr, m) {
  if(m.length < 1) return arr;
  var result = split(arr, m[0]);
  return result.map(function(sublist) {
    return splitTree(sublist, m.slice(1));
  });
}

var l = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24];

console.log(splitTree(l, [2,3,2]));
Tesseract
  • 8,049
  • 2
  • 20
  • 37
0

Please, see

https://stackoverflow.com/a/10456644/1875956

it can be first step for you issue. And next will be recursive splitting each array

Community
  • 1
  • 1
Sabik
  • 1,599
  • 1
  • 11
  • 10