Как разделить упорядоченный список целых чисел на подсписки одинакового размера?

Question

Есть ли у кого-нибудь хороший алгоритм взятия упорядоченного списка целых чисел, т.е. [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]

Требование состоит в том, чтобы каждый из подсписков был упорядочен и как можно большего размера.

Answer 1

Равномерное разбиение списков означает, что у вас будет два размера списков - размер S и S + 1.

С N подсписками и X элементами в оригинале вы получите:

этаж (X / N) количество элементов в меньших подсписках (S), а X% N - количество больших подсписков (S + 1).

Затем выполните итерацию по исходному массиву и (глядя на ваш пример) сначала создайте небольшие списки.

Примерно так:

 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

Вот мое собственное рекурсивное решение, основанное на сортировке слиянием и обходе первого дерева в ширину:

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

Я надеялся, что кто-то может предложить итеративное решение.

Answer 3

Вы могли бы рассмотреть что-то вроде этого:

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

Это не совсем отточено - я попал в бесконечный цикл (я думаю), когда я попытался передать массив из 18 элементов с 10 подсписками. Я думаю, что алгоритм не работает, когда мин == 1.

Это должно быть довольно быстро. Удачи:)

Answer 4

Это должен быть ответ более итеративным образом.

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 5

псевдокод ...

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

Этот код нужно немного привести в порядок, но я уверен, что вы поняли. Также я подозреваю, что список интервалов неравномерного размера будет в конце, а не в начале. Если вы действительно хотите это наоборот, вы можете сделать это, изменив порядок цикла.

Answer 6

Вот решение для Python. Вы можете перевести его на Java, вам нужен способ получить часть списка, а затем вернуть его. Вы не можете использовать генераторный подход, но вы можете добавить каждый подсписок в новый список.