How to split an ordered list of integers into subnets with uniform size?

Question

Does anyone have a good algorithm for receiving an ordered list of integers, i.e.:
[1, 3, 6, 7, 8, 10, 11, 13, 14, 17, 19, 23, 25, 27, 28]

to a given number of ordered ordered ordered sizes, i.e. for 4 it will be:
[1, 3, 6] [7, 8, 10, 11] [13, 14, 17, 19] [23, 25, 27, 28]

The requirement is that each subscription be streamlined and as similar as possible in size.

Answer 1

Splitting lists evenly means that you will have two sizes of lists - size S and S + 1.

With N subscriptions and X elements in the original, you get:

floor (X / N) is the number of elements in smaller sublists (S), and X% N is the number of large subscriptions (S + 1).

Then iterate over the original array and (look at your example), creating the first lists.

Something like this could be:

private static List<Integer[]> splitOrderedDurationsIntoIntervals(Integer[] durations, int numberOfIntervals) { int sizeOfSmallSublists = durations.length / numberOfIntervals; int sizeOfLargeSublists = sizeOfSmallSublists + 1; int numberOfLargeSublists = durations.length % numberOfIntervals; int numberOfSmallSublists = numberOfIntervals - numberOfLargeSublists; List<Integer[]> sublists = new ArrayList(numberOfIntervals); int numberOfElementsHandled = 0; for (int i = 0; i < numberOfIntervals; i++) { int size = i < numberOfSmallSublists ? sizeOfSmallSublists : sizeOfLargeSublists; Integer[] sublist = new Integer[size]; System.arraycopy(durations, numberOfElementsHandled, sublist, 0, size); sublists.add(sublist); numberOfElementsHandled += size; } return sublists; } 

Answer 2

Here is my own recursive solution based on merge sort and width of the first tree walk:

 private static void splitOrderedDurationsIntoIntervals(Integer[] durations, List<Integer[]> intervals, int numberOfInterals) { int middle = durations.length / 2; Integer[] lowerHalf = Arrays.copyOfRange(durations, 0, middle); Integer[] upperHalf = Arrays.copyOfRange(durations, middle, durations.length); if (lowerHalf.length > upperHalf.length) { intervals.add(lowerHalf); intervals.add(upperHalf); } else { intervals.add(upperHalf); intervals.add(lowerHalf); } if (intervals.size() < numberOfIntervals) { int largestElementLength = intervals.get(0).length; if (largestElementLength > 1) { Integer[] duration = intervals.remove(0); splitOrderedDurationsIntoIntervals(duration, intervals); } } } 

I was hoping someone has a suggestion for an iterative solution.

Answer 3

Here is a solution for Python. You can translate it into Java, you need a way to get part of the list, and then return it. However, you cannot use the generator approach, but you can add each list to a new list.

Answer 4

pseudo code ...

 private static void splitOrderedDurationsIntoIntervals(Integer[] durations, List<Integer[]> intervals, int numberOfInterals) { int num_per_interval = Math.floor(durations.length / numberOfInterals); int i; int idx; // make sure you have somewhere to put the results for (i = 0; i < numberOfInterals; i++) intervals[i] = new Integer[]; // run once through the list and put them in the right sub-list for (i = 0; i < durations.length; i++) { idx = Math.floor(i / num_per_interval); intervals[idx].add(durations[i]); } } 

This code will need to be cleaned up a bit, but I'm sure you understand. I also suspect that the list of intervals of uneven size will be at the end, not at the beginning. If you really want this, you can probably do this by changing the order of the loop.

Answer 5

This should be the answer in a more iterative way.

 public static void splitList(List<Integer> startList, List<List<Integer>> resultList, int subListNumber) { final int subListSize = startList.size() / subListNumber; int index = 0; int stopIndex = subListSize; for (int i = subListNumber; i > 0; i--) { resultList.add(new ArrayList<Integer>(startList.subList(index, stopIndex))); index = stopIndex; stopIndex = (index + subListSize > startList.size()) ? startList.size() : index + subListSize; } } 

Answer 6

You might think something like this:

 public static int[][] divide(int[] initialList, int sublistCount) { if (initialList == null) throw new NullPointerException("initialList"); if (sublistCount < 1) throw new IllegalArgumentException("sublistCount must be greater than 0."); // without remainder, length / # lists will always be the minimum // number of items in a given subset int min = initialList.length / sublistCount; // without remainer, this algorithm determines the maximum number // of items in a given subset. example: in a 15-item sample, // with 4 subsets, we get a min of 3 (15 / 4 = 3r3), and // 15 + 3 - 1 = 17. 17 / 4 = 4r1. // in a 16-item sample, min = 4, and 16 + 4 - 1 = 19. 19 / 4 = 4r3. // The -1 is required in samples in which the max and min are the same. int max = (initialList.length + min - 1) / sublistCount; // this is the meat and potatoes of the algorithm. here we determine // how many lists have the min count and the max count. we start out // with all at max and work our way down. int sublistsHandledByMax = sublistCount; int sublistsHandledByMin = 0; while ((sublistsHandledByMax * max) + (sublistsHandledByMin * min) != initialList.length) { sublistsHandledByMax--; sublistsHandledByMin++; } // now we copy the items into their new sublists. int[][] items = new int[sublistCount][]; int currentInputIndex = 0; for (int listIndex = 0; listIndex < sublistCount; listIndex++) { if (listIndex < sublistsHandledByMin) items[listIndex] = new int[min]; else items[listIndex] = new int[max]; // there probably a better way to do array copies now. // it been a while since I did Java :) System.arraycopy(initialList, currentInputIndex, items[listIndex], 0, items[listIndex].length); currentInputIndex += items[listIndex].length; } return items; } 

This is not completely polished - I ended up in an endless loop (I think) when I tried to transfer an array of 18 items with 10 sublists. I think the algorithm breaks when min == 1.

It should be pretty fast. Good luck :)