Split a list into equal parts?

Question

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.

maybe try section[0] = size/n; section[1] = (size - section[0])/(n-1); section[2] = (size-section[0]-section[1])/(n-2); ... — pmg
– pmg, Commented Oct 23, 2019 at 19:38
(Both comments will produce the same result, but unless you need it to be very fast - which was the idea for the line drawing algorithm -, @pmg's is the simpler one to comprehend) — tevemadar
– tevemadar, Commented Oct 23, 2019 at 19:43

Davis Herring · Accepted Answer · 2019-10-23 19:54:13Z

6

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.

answered Oct 23, 2019 at 19:54

Davis Herring

41.9k4 gold badges58 silver badges91 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Split a list into equal parts?

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related