如何将有序的整数列表划分为大小均匀的子列表？

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]

有没有人有一个很好的算法来获取有序的整数列表,即:[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]

在给定数量的均匀大小的有序子列表中,即4,它将是:[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.

要求是每个子列表都是有序的并且尺寸尽可能相似。

6 个解决方案

#1

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

均匀拆分列表意味着您将拥有两种大小的列表 - 大小为S和S + 1。

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

使用N个子列表和原始X元素,您将获得:

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

floor(X / N)在较小子列表(S)中的元素数量,并且X%N是较大子列表(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;
}

#2

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.

我希望有人可能会建议迭代解决方案。

#3

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.

这是Python的解决方案。您可以将其转换为Java,您需要一种方法来获取一个列表然后返回它。但是,您不能使用生成器方法,但可以将每个子列表附加到新列表中。

#4

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.

该代码需要整理一下,但我相信你明白了。此外,我怀疑大小不均匀的间隔列表将在结束时而不是在开始时。如果你真的想要这样,你可以通过颠倒循环的顺序来做到这一点。

#5

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;
    }
}

#6

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.

这还不是很完美 - 当我试图通过10个子列表传递一个18项数组时,我进入了一个无限循环(我想)。我认为当min == 1时算法会崩溃。

This should be fairly fast. Good luck :)

这应该相当快。祝好运 :)