# Slice a slice as evenly as possible given the maximum length of the sub-slices

Hi,

This might be more of a math problem, but since I need to solve in Go, I hope someone could help me out here.

Say you have a sorted slice (of any length)

``````mySlice := []int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21}
``````

you know want to split it into smaller slices, as evenly as possible, which each sub-slice not exceeding a given length.

Slicing a slice is rather easy to do with:

``````func slicing(s []int, n int) [][]int {
var res [][]int
for {
if len(s) == 0 {
break
}

if len(s) < n {
n = len(s)
}

res = append(res, s[0:n])
s = s[n:]
}

return res
}
``````

However this implies that you know already what would be the value on `n` so that the lengths of the sub-slice are as evenly as possible.

Just to take make an example if I do

``````slicing(mySlice, 4)
``````

the result of `slicing` is `[[1 2 3 4] [5 6 7 8] [9 10 11 12] [13 14 15 16] [17 18 19 20] [21]]` which would not be correct, since we have 5 slice of length 4 and 1 slice of length 1, while the “more even” slicing should be `[[1 2 3 4] [5 6 7 8] [9 10 11 12] [13 14 15] [16 17 18] [19 20 21]]` (4+4+4+3+3+3)

Again, for

``````slicing(mySlice, 8)
``````

you get `[[1 2 3 4 5 6 7 8] [9 10 11 12 13 14 15 16] [17 18 19 20 21]]`, while the “more even” result would be `[[1 2 3 4 5 6 7] [8 9 10 11 12 13 14] [15 16 17 18 19 20 21]]` (7+7+7)

for

``````slicing(mySlice, 6)
``````

`[[1 2 3 4 5 6] [7 8 9 10 11 12] [13 14 15 16 17 18] [19 20 21]]``[[1 2 3 4 5 6] [7 8 9 10 11] [12 13 14 15 16] [17 18 19 20 21]]` (6+5+5+5)

Any suggestion?

Maybe you can round up (math package - math - pkg.go.dev).
For example,

``````slicing(mySlice, 4)
``````

21 elements and you want to split with max 4.
21 / 4 = 5.25 (you will need 6 slices)

You have to create 6 new slices with “3.5” elements each.
21 / 6 = 3.5
Round up to 4 for the first slice.

Now you have 17 elements and 5 slice left.
17 / 5 = 3.5
Round up to 4 for the second slice.

Now you have 13 elements and 4 slice left.
13 / 4 = 3.5
Round up to 4 for the third slice.

Now you have 9 elements and 3 slice left.
9 / 3 = 3
Round up to 3…

21 % 6 will give you 3, the number of slices that must have Math.ceil(21/6)==4 elements, the remaining slices must contain Math.floor(21/6)==3 elements. 3 slices of 4 elements + (6-3) slices of 3 elements = 12 + 9 = 21

In my terseness I was probably not clear. I hope you didn’t think I was correcting what was quoted. 21 / 6 is 3.5 as you said. Instead, I was expanding on that information to optimize the repetitive algorithm that you described. One can use the remainder from 21 /6, which is where 21 % 6 = 3 comes from, to determine directly how many of each of the larger and small subslices are needed.

Sure, maybe there are many solutions.
Try it with other cases like a slice with 17 elements and max 8.
I believe that your expected result is (6,6,5)?

17 / 8 = 2.5 or 2 with a remainder of 1. (17 %8 == 1)
2 slices
1 (the remainder) of the larger size and 2-1 = 1 of the smaller size
The smaller size is math.Floor(17/2) = 8 (2 → number of slices)
The larger size is math.Ceil(17/2) = 9
8 + 9 = 17

Looks like my max size is off by one. I’ll adjust my algorithm and add the corrected one shortly.

Thanks @GonzaSaya & @mje, your replies gave me some hints, and after banging my head a couple of times against the wall I came up with something that works. Not sure it is the most efficient way of doing it, but for it work

``````func slicing(s []int, maxv int) [][]int {
size := (len(s) + maxv - 1) / maxv
extra := len(s) % ((len(s) + maxv - 1) / maxv)
value := len(s) / ((len(s) + maxv - 1) / maxv)

pres := make([]int, size)
for i := 0; i < size; i++ {
pres[i] = value
}

for i := 0; i < extra; i++ {
pres[i] = pres[i] + 1
}

res := make([][]int, size)
for i := 0; i < size; i++ {
res[i] = s[:pres[i]]
s = s[pres[i]:]
}

return res
}
``````

Go Playground

Nice!
I like how you solve the size variable.

``````package main

import (
"fmt"
)

func main() {
mySlice := []int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21}
out := slicing(mySlice, 4)
fmt.Println(out)
out = slicing(mySlice, 8)
fmt.Println(out)
out = slicing(mySlice, 6)
fmt.Println(out)
}

func slicing(s []int, maxv int) [][]int {
size := (len(s) + maxv - 1) / maxv
res := make([][]int, size)
for i := 0; i < size; i++ {
currentSliceCount := len(s) / (size - i)
res[i] = s[:currentSliceCount]
s = s[currentSliceCount:]
}
return res
}
``````

Can you check this solution?

Thanks.
No, something is off.
`slicing(mySlice, 4)` and `slicing(mySlice, 6)` do not return the wanted result. I will look at it deeper as soon as I can

``````func slicing(s []int, maxv int) [][]int {
size := (len(s) + maxv - 1) / maxv
res := make([][]int, size)
for i := 0; i < size; i++ {
var currentSliceCount int
extra := len(s) % ((len(s) + maxv - 1) / maxv)
if extra > 0 {
currentSliceCount = (len(s) / (size - i)) + (extra / extra)
} else {
currentSliceCount = (len(s) / (size - i))
}
res[i] = s[:currentSliceCount]
s = s[currentSliceCount:]
}
return res
}
``````

This now gives the right output.
Probably this is a better alternative to my solution (just one loop, and no intermediate slice allocation), but I do not have the expertise to support this claim, neither I know how to benchmark it properly. If you do, please let me know

Nice!
Question: The only difference with my solution is which slice is bigger than the other. Is that important for your code?

I have only 2 suggestions:

``````extra := len(s) % ((len(s) + maxv - 1) / maxv)
``````

to

``````extra := len(s) % size
``````

AND

``````currentSliceCount = (len(s) / (size - i)) + (extra / extra)
``````

to

``````currentSliceCount = (len(s) / (size - i)) + 1
``````

So

``````currentSliceCount = (len(s) / (size - i)) + 1
``````

is indeed ok.
Regarding the first suggestion, you should notice that `s` changes inside the loop, so its length, and that is why `extra` keeps changes, and needs to be re-evaluate.

Regarding your question, it is kid of important, to be on the safe side the slicing should happen from left to right, rather than from right to left.

I did some benchmarking (hopefully in the right way, still learning) with various lengths of s [10-50-150-250-500] and maxv[7-13-16-19-23], your implementation seems to be slower but less demanding, mine is faster but definitely use more memory.

As an example, mine:

``````BenchmarkSlicing-12      6856872               172.5 ns/op           256 B/op          2 allocs/op
BenchmarkSlicing-12      6794420               174.5 ns/op           256 B/op          2 allocs/op
BenchmarkSlicing-12      7106743               182.1 ns/op           256 B/op          2 allocs/op
BenchmarkSlicing-12      6989544               176.6 ns/op           256 B/op          2 allocs/op
BenchmarkSlicing-12      6991738               177.7 ns/op           256 B/op          2 allocs/op
``````

yours:

``````BenchmarkSlicing2-12             3969279               309.4 ns/op           192 B/op          1 allocs/op
BenchmarkSlicing2-12             3916411               313.1 ns/op           192 B/op          1 allocs/op
BenchmarkSlicing2-12             3882604               317.2 ns/op           192 B/op          1 allocs/op
BenchmarkSlicing2-12             3988410               313.5 ns/op           192 B/op          1 allocs/op
BenchmarkSlicing2-12             3862108               313.9 ns/op           192 B/op          1 allocs/op
``````

Great, one last suggestion to improve performace/memory:

``````package main

import (
"fmt"
)

func main() {
mySlice := []int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21}
out := slicing(mySlice, 4)
fmt.Println(out)
out = slicing(mySlice, 8)
fmt.Println(out)
out = slicing(mySlice, 6)
fmt.Println(out)
}

func slicing(s []int, maxv int) [][]int {
size := (len(s) + maxv - 1) / maxv
res := make([][]int, size)
startFrom := 0
for i := 0; i < size; i++ {
currentSliceCount := (len(s) - startFrom) / (size - i)
res[i] = s[startFrom : startFrom+currentSliceCount]
startFrom += currentSliceCount
}
return res
}
``````