Algorithm to split an alphabetical list into N evenly sized columns - Stack Overflow

admin管理员组

文章数量:1317915

Assume I have a list of names, with length L, sorted in alphabetical order. I want to split this list into N groups with these requirements:

1. The alphabetical order must be retained, reading group by group
2. All names with the same initial must be in the same group
3. The size of each group should be as even as possible

The requirements are in order of importance.

Is there a straightforward algorithm to accomplish this?

Example

Assume the following list of 30 names which we want to split over 3 groups/rows:

Abel Alex Amir Aria Axel Cali Enzo Evan Ezra Finn Hank Ivan Jade Jake Joel June Kane Lara Leon Levi Liam Luca Milo Nico Noah Remy Rory Sage Sean Theo

A naive implementation would be to iterate over the list and try to split as close to positions 10 and 20 as possible:

1	2	3	4	5	6	7	8	9	10	11	12
Abel	Alex	Amir	Aria	Axel	Cali	Enzo	Evan	Ezra	Finn
Hank	Ivan	Jade	Jake	Joel	June	Kane	Lara	Leon	Levi	Liam	Luca
Milo	Nico	Noah	Remy	Rory	Sage	Sean	Theo

Assume I have a list of names, with length L, sorted in alphabetical order. I want to split this list into N groups with these requirements:

1. The alphabetical order must be retained, reading group by group
2. All names with the same initial must be in the same group
3. The size of each group should be as even as possible

The requirements are in order of importance.

Is there a straightforward algorithm to accomplish this?

Example

Assume the following list of 30 names which we want to split over 3 groups/rows:

Abel Alex Amir Aria Axel Cali Enzo Evan Ezra Finn Hank Ivan Jade Jake Joel June Kane Lara Leon Levi Liam Luca Milo Nico Noah Remy Rory Sage Sean Theo

A naive implementation would be to iterate over the list and try to split as close to positions 10 and 20 as possible:

1	2	3	4	5	6	7	8	9	10	11	12
Abel	Alex	Amir	Aria	Axel	Cali	Enzo	Evan	Ezra	Finn
Hank	Ivan	Jade	Jake	Joel	June	Kane	Lara	Leon	Levi	Liam	Luca
Milo	Nico	Noah	Remy	Rory	Sage	Sean	Theo

The first group is easy, as we can make our first split after 10 names. However, for our second split we want to keep all five names starting with 'L' in the same group. Since we have 2 names with the initial 'L' after position 20 and 3 names before, it makes sense to make our second split after 'Luca', before 'Milo'. Giving the above result. Splitting before 'Lara' would have resulted in a less even distribution.

But by moving 'Hank' from the second group to the first, we get an even more even distribution, proving that our naive algorithm is not optimal:

1	2	3	4	5	6	7	8	9	10	11
Abel	Alex	Amir	Aria	Axel	Cali	Enzo	Evan	Ezra	Finn	Hank
Ivan	Jade	Jake	Joel	June	Kane	Lara	Leon	Levi	Liam	Luca
Milo	Nico	Noah	Remy	Rory	Sage	Sean	Theo

Limitations

There will of course be situations where it is impossible to fulfill all requirements. For example if all names start with the same letter and N>1. In this situation the requirement regarding evenness is impossible to achieve since the first group will be of length L and the other groups will have length 0.

Evenness (edit)

I've been told the evenness requirement is unclear. I am not sure how to define evenness, but want a visually pleasing presentation of the grouped list of names. Please suggest improvements to the question if you can.

Some ideas:

• minimize the maximum length of the largest group
• minimize the difference between the lengths of the largest group and the smallest group
• minimize the number of empty cells when the groups are displayed in a tabular format

• algorithm

Share Improve this question Follow edited Feb 3 at 19:05 greybeard 2,54699 gold badges3838 silver badges7070 bronze badges asked Jan 24 at 12:31 Tomas EklundTomas Eklund 63311 gold badge55 silver badges1919 bronze badges 3

• I would go for your "naive implementation" and than start a neighbourhood search for solutions that can be reached with small modifications and improve the overall result. – MrSmith42 Commented Jan 24 at 12:36
• 1 What does "as even as possible" mean? How do you define evenness? – no comment Commented Jan 25 at 12:38
• @nocomment Good question. I do not know, but I have edited the question elaborating on the topic. Do you have any suggestions? I'm not a computer scientist, nor a matematician. I just have a real world problem I would like to solve. – Tomas Eklund Commented Feb 4 at 7:10

Add a comment  | 

1 Answer 1

Sorted by: Reset to default 1

The criteria is unclear. But here is a solution to a closely related problem.

Write the following straightforward function that runs in time O(n).

def allocate_groups (sizes, max_group_size):
    ...

Now do a binary search for the smallest possible max_group_size that fits within N groups. Your starting bounds are max(sizes) to sum(sizes). This takes a fairly small number of passes.

This minimizes the max size. Note that if L was large enough to make a big group, this would divide the other groups unevenly. If you want to improve that, you can take out the largest group, and repeat with the remaining sizes for N-1 groups, and the idea of a "barrier". Recurse. Then put your chosen groups together in the right order. This will force a very even distribution, even if there is a large group.

You can introduce a barrier by changing your initial naive function with:

def assign_groups(grouping_sizes, max_group_size):
    ...

Where grouping_sizes is a list of lists of sizes. Note that this new function can be written in terms of the old allocate_groups - one cluster of groups is allocated per list of sizes.

本文标签： Algorithm to split an alphabetical list into N evenly sized columnsStack Overflow