Does anyone have a good algorithm for taking an ordered list of integers, i.e.:
[1, 3, 6, 7, 8, 10, 11, 13, 14, 17, 19, 23, 25, 27, 28]
into a given number of evenly sized ordered sublists, i.e. for 4 it will be:
[1, 3, 6] [7, 8, 10, 11] [13, 14, 17, 19] [23, 25, 27, 28]
The requirement being that each of the sublists are ordered and as similar in size as possible.
Here is my own recursive solution, inspired by merge sort and breadth first tree traversal:
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 might have a suggestion for an iterative solution.
Splitting the lists evenly means you will have two sizes of lists - size S and S+1.
With N sublists, and X elements in the original, you would get:
floor(X/N) number of elements in the smaller sublists (S), and X % N is the number of larger sublists (S+1).
Then iterate over the original array, and (looking at your example) creating small lists firsts.
Something like this maybe:
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;
}
Here's a solution for Python. You can translate it to Java, you need a way to get a piece of of a list and then to return it. You cannot use the generator approach though, but you can append each sublist to a new list.
pseudocode...
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]);
}
}
That code will need a bit of tidying up, but I'm sure you get the point. Also I suspect that the uneven sized interval list will be at the end rather than at the beginning. If you really want it that way round you can probably do that by reversing the order of the loop.
That should be an Answer in a more iterative fashion.
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;
}
}
You might consider 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's probably a better way to do array copies now.
// it's been a while since I did Java :)
System.arraycopy(initialList, currentInputIndex, items[listIndex], 0, items[listIndex].length);
currentInputIndex += items[listIndex].length;
}
return items;
}
This isn't quite polished - I got into an infinite loop (I think) when I tried to pass an 18-item array in with 10 sublists. I think the algorithm breaks down when min == 1.
This should be fairly fast. Good luck :)