如何將有序的整數列表劃分爲大小均勻的子列表？

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。

隨氮素子列表，並在原始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

Here's爲Python的解決方案。你可以把它翻譯成Java，你需要一種方法來獲得一個列表，然後返回它。儘管您不能使用生成器方法，但是您可以將每個子列表追加到新列表中。

Answer 4

僞...

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 5

這應該是一個更迭代的答案。

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

你可能會考慮這樣的事情：

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個子列表。我認爲當min == 1時算法崩潰了。

這應該是相當快的。祝你好運:)