How to split a slice into N chunks?

I'm looking for a nice way to split a slice into N chunks of approximately equal size. The chunks method allows me to split a slice into chunks of size M, with the last chunk having the remainder, but that results in the last one sometimes being much smaller. I want all the chunks to be the same size or one greater.

It kind of seems like this might be a common desire. Any suggestions for a built-in method that I missed, or some elegant way to manage this?

Well, that's a matter of picking a M for chunks where len() % M == 0. Then, it becomes a matter of finding a factor, M, where your originally selected chunk-size, Q, satisfies the following: M >= Q && len() % M == 0.

Your best choice is to search for a nice factor via looping, or just live with the last, oddly sized chunk.

let slice = /**/;
let mut factor = Q;
while slice.len() % factor != 0 {
    factor += 1; //Possibly fancier.
}
for chunk in slice.chunks(factor) {
    println!("Yay! These are all the same size!");
}

Note: If I have understood your question properly, you want to find an N such that your slice can always be broken into groups of N.

This iterator will yield n chunks, each of size (len / n) or (len / n) + 1. (The first len % n chunks will be one element longer than the chunks that follow.)

pub fn split<T>(slice: &[T], n: usize) -> impl Iterator<Item = &[T]> {
    let len = slice.len() / n;
    let rem = slice.len() % n;
    Split { slice, len, rem }
}

struct Split<'a, T> {
    slice: &'a [T],
    len: usize,
    rem: usize,
}

impl<'a, T> Iterator for Split<'a, T> {
    type Item = &'a [T];
    
    fn next(&mut self) -> Option<Self::Item> {
        if self.slice.is_empty() {
            return None;
        }
        let mut len = self.len;
        if self.rem > 0 {
            len += 1;
            self.rem -= 1;
        }
        let (chunk, rest) = self.slice.split_at(len);
        self.slice = rest;
        Some(chunk)
    }
}

Playground

2 Likes

If my previous reply misunderstood what you want to achieve, and it is as follows, then please disregard my previous post.


If you want to have it such that your slice is split into groups of N, where the last one would end up being len() % N long using the standard chunks function, but is instead appended to the last one so that the length of your chunks are always at least N, then you may want to roll out your own chunks-style iterator which deals with the edge case.


If, alternatively you want to search for some N where you can split your slice into chunks of size N, and the last one be at most N + 1 long, then something like the following might work:

fn chunks<T>(slice: &[T], mut size: usize) -> impl Iterator<Item = &[T]> {
    struct ChunksIterator<'a, I> {
        pub slice: &'a [I],
        pub total: usize,
        pub current: usize,
        pub chunk: usize,
    }
    impl<'a, I> Iterator for ChunksIterator<'a, I> {
        type Item = &'a [I];
        fn next(&mut self) -> Option<&'a [I]> {
            if self.current == self.total {
                None
            } else if self.slice.len() / self.chunk == 1 && self.slice.len() % self.chunk != 0 {
                self.current += 2;
                Some(self.slice)
            } else {
                self.current += 1;
                let (lhs, rhs) = self.slice.split_at(self.chunk);
                self.slice = rhs;
                Some(lhs)
            }
        }
    }
    while slice.len() % size > 1 {
        size += 1;
    }
    let mut len = slice.len() / size;
    if slice.len() % len != 0 {
        len += 1;
    }
    ChunksIterator {
        slice,
        total: len,
        chunk: size,
        current: 0,
    }
}

Playground.

1 Like
let slice = /**/;
let len = slice.len();
assert!(len >= N);
let (quo, rem) = (len / N, len % N);
let split = (quo + 1)*rem;
let mut iter = slice[..split].chunks(quo + 1).chain(slice[split..].chunks(quo));
5 Likes

Thanks for your suggestions, especially @TomP, @OptimisticPeach, and @mbrubeck. I ended up rolling my own solution vaguely based on that of @OptimisticPeach, who had the idea of making the iterator itself local to the chunks function. I realized that I wanted the length of the chunks (when not exactly even) to be distributed randomly (I'm dividing students into groups), and also simplified the counting.

fn split_evenly<T>(slice: &[T], n: usize) -> impl Iterator<Item = &[T]> {
    struct Iter<'a, I> {
        pub slice: &'a [I],
        pub n: usize,
    }
    impl<'a, I> Iterator for Iter<'a, I> {
        type Item = &'a [I];
        fn next(&mut self) -> Option<&'a [I]> {
            if self.slice.len() == 0 {
                return None;
            }
            let extra = if self.slice.len() % self.n == 0 {
                0
            } else if rand::random::<usize>() % self.n < self.slice.len() % self.n {
                0
            } else {
                1
            };
            let (first, rest) = self.slice.split_at(self.slice.len() / self.n + extra);
            self.slice = rest;
            self.n -= 1;
            Some(first)
        }
    }
    Iter { slice, n }
}

Playground.

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.