Break a array into n chunks with overlapping start element

2
votes

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);
2
javascriptarraysalgorithm
Hi, what have you tried so far ? – Maxime Girou
I tried to code a working solution for ~2hr, it's simple problem but I can't get It right, really don't know why. My solutions had a problem with elements at the start/end of the output. So I decided to post it here to save time and frustration. – Damian Grzanka
You can show your solution and ask community to help fix it. – Slavik
hi @DamianGrzanka, we understand your feeling ! please share your code then. It doesnt matter if its not working – Maxime Girou
Does this answer your question? Split array into chunks – MrMythical

2 Answers

0
votes

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

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.