CODEWITHSUNDEEP
c++carrayspartitioning
Jedediah Heal
Jedediah Heal

Reputation: 123

Split a list into equal parts?

I have an array of size elements, and I have a function that will split it into roughly equal sections. It does this by setting the size of the first size-1 sections with size/num_of_sections, and setting the size of the last section with whatever is left. The code is simple, works correctly and looks like so:

int section_size = size / num_of_sections;
int last_section_size = size - ( section_size * (num_of_sections - 1) );

The only problem is that there are some combinations of size and num_of_sections that does not split very well. For example, if size = 10 and num_of_sections = 6, then the first four sections will be 1 element each, and the last section will be 6 elements.

How can I change this to an algorithm that will split it up more evenly, specifically, so that all sections are either size X or X+1? In the above example, the first four sections would be size 2, then the last two sections will be 1 each. There would obviously need to be a third variable produced that indicates a section number where all previous sections up to and including it are size X and all following are size X+1.

Upvotes: 3

Views: 764

Answers (1)

Davis Herring
Davis Herring

Reputation: 40043

The usual approach, when you’re fine with grouping all the larger pieces, is

const int total=/*…*/,pieces=/*…*/;
const int base=total/pieces,extra=total%pieces;

Then the first extra (perhaps 0) pieces have size base+1 and the (pieces-extra) others have size base.

Upvotes: 6

Related Questions