Break a array into n chunks with overlapping start element

user_13993723 0
Viewed 274

I have the following problem, I need to split an array into at least n even chunks, but the first element of every array except the first is the last element of the previous array. The last array can have a smaller number of elements if there aren't enough elements.

Edge case discovered by ~ @trincot

If it is not possible to split into n requested chunks, split to the closest number of chunks that when is possible.

Input:

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]

Expected output n=3:

[[1, 2, 3, 4, 5], [5, 6, 8, 9, 10], [10, 11]]

I need a solution in JavaScript but feel free to submit other languages, I will translate it and submit the solution in JavaScript.

My not working attempt, I couldn't figure out how to start with desired chunk number so I used chunk size here with intention to figure out chunk size from chunk number later.

let array = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11];
const range = 4;
const res = [array.slice(0, range)];

let start = range;
let end = range * 2;
while (true) {
  console.log(start, end);
  res.push(array.slice(start, end));
  start += range;
  end += range;
  if (start >= array.length) {
    break;
  }
}

console.log(res);
arrays algorithm javascript
2 Answers

Here is a mapping function that produces the result:

const overlapSplit = (arr, length) => {
    let chunk = 1 + Math.max(1, Math.ceil((arr.length - 1) / length));
    if (length > 1 && (chunk - 1) * (length - 1) + 1 > arr.length) return overlapSplit(arr, length - 1);
    return Array.from({length}, (_, i) =>
        arr.slice(i * chunk - i, i * chunk - i + chunk)
    );
}  

console.log(overlapSplit([1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13], 6));

user_54598390

This version splits it into n chunks, with as close to equal size as possible.

That is, 1 - 11 split into four chunks, with the overlap required, becomes: [1, 2, 3, 4], [4, 5, 6, 7], [7, 8, 9], and [9, 10, 11]. Note that all of them have either three or four elements, and the ones with four come before those with three.

const getIndices = (n, g, a = 0, c = Math .ceil (n / g) ) => 
  (n < 1 || g < 1) ? [] : [c + a, ... getIndices (n - c, g - 1, c + a - 1)]

const equalishChunks = (xs, g) =>
  getIndices (xs .length + g - 1, g) 
    .map ((n, i, a) => xs .slice ((a [i - 1] || 1) - 1, n))

console .log (equalishChunks ([1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11], 3))
console .log (equalishChunks ([1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11], 4))
console .log (equalishChunks ([1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14], 6))
.as-console-wrapper {max-height: 100% !important; top: 0}

We do the problem in two parts. First we find the indices at we need to break our array (in the call to getIndices), and then we break the array at these indices (in the .map call.)

getIndices recurs on the number of groups remaining to handle (g), using the number of items to group, n, an accumulator, a, and the current value, c, which is just the ceiling of the quotient of the n and g. This is not a generic function, because of your unusual overlap requirements, which are here handled by the - 1 in the final parameter to the recursive call. For example for 1 - 11 in four chunks, this will return [4, 7, 9, 11].

equalishChunks adds to the length of the array the number of overlapped values (one less than the number of groups), calls getIndices and then maps over them, splitting the array at these indices (with the overlap again handled by a - 1, the second one in (a [i - 1] || 1) - 1. The || 1 is just to handle the first index where a [i - 1] won't exist.

user_12436410
Related