Java 8 divide n size collection to m lists of unknown size

Question

General problem I don't know how to divide a sorted list to smaller sorted lists but NOT in a manner like in Guava Lists.partition(list,size) - so not to a smaller lists of specified size BUT to a fixed number of lists of similar size.

For example having a source list: 1,2,3,4 I want to have 3 lists as a results (the 3 is the fixed number of resulting lists). I should have the results List<List<Long>>: ListOne: 1, ListTwo: 2, ListThree: 3,4 (keep in mind that sorting is kept). When source list is smaller then number of target lists, then OK, I could get smaller number of lists. So whe a source list is 1,2 and I want to have 3 lists, the algorithm should return two lists: List1 1, List2: 2.

The size of the source list is unknown, but there are hundret of thousends of elements that have to be divided to 10 lists, becaouse then 10 threads are ready to do some more complicated operations with those elements.

The below algorithm is totally wrong, having 14 elements on source list and passing GRD_SIZE=10 it returns 7 lists of 2 elements. It should return GRD_SIZE=10 lists of similar sizes. Propably I shouldn't also use the Guava Lists.partition method... But how to do this task ?

List<List<Long>> partitions = partition(sourceList, GRD_SIZE);

public static <T> List<List<T>> partition(List<T> ascSortedItems, int size)
{
     int threadSize =  (int) Math.ceil(
         new BigDecimal(ascSortedItems.size()).divide(
             new BigDecimal(
                 ascSortedItems.size() >= size ? size : ascSortedItems.size()
             )
          ).doubleValue()
     );

     final AtomicInteger counter = new AtomicInteger(0);

     return ascSortedItems.stream()
         .collect(Collectors.groupingBy(it -> counter.getAndIncrement() / threadSize))
         .values()
         .stream()
         .collect(Collectors.toList());
}

Answer 1

First, you should not use a mutable counter like in your attempted solution. A canonical alternative would be like in this answer, which, after adapting to your problem, would look like:

return IntStream.range(0, (ascSortedItems.size()+threadSize-1)/threadSize)
    .mapToObj(i -> ascSortedItems
          .subList(i*threadSize, Math.min(ascSortedItems.size(), (i+1)*threadSize)))
    .collect(Collectors.toList());
}

The calculation of threadSize doesn’t need that strange BigDecimal detour. You can calculate it as

int threadSize = Math.max(1, ascSortedItems.size()/size);

when rounding down or

int threadSize = Math.max(1, (ascSortedItems.size()+size-1)/size);

for rounding up.

But neither will work the intended way. To stay with your example, rounding down will create 14 lists of size one, rounding up will create 7 lists of size two.

A real solution can only be done by not calculating a batch size first:

public static <T> List<List<T>> partition(List<T> ascSortedItems, int numLists) {
    if(numLists < 2) {
        if(numLists < 1) throw new IllegalArgumentException();
        return Collections.singletonList(ascSortedItems);
    }
    int listSize = ascSortedItems.size();
    if(listSize <= numLists) {
        return ascSortedItems.stream()
            .map(Collections::singletonList)
            .collect(Collectors.toList());
    }
    return IntStream.range(0, numLists)
        .mapToObj(i -> ascSortedItems.subList(i*listSize/numLists, (i+1)*listSize/numLists))
        .collect(Collectors.toList());
}

The first part checks for the validity of the numLists argument and handles the trivial special case of one list.

The middle part handles your requirement of returning less lists if the source list is smaller than the requested number of lists (otherwise, the result would always have the requested number of lists, possibly containing empty lists).

The last part does the actual job. As you can see, the initial IntStream.range(0, numLists) invariably produces numLists elements which are then mapped to the sublists, postponing rounding to the latest point possible. For your example of [ 1, 2, 3, 4] and three requested lists, it produces

[1]
[2]
[3, 4]

for the 14 elements and requesting ten lists, it produces

[1]
[2]
[3, 4]
[5]
[6, 7]
[8]
[9]
[10, 11]
[12]
[13, 14]

It’s unavoidable to have some lists of size one and some of size two to fulfill the request to have exactly ten lists. That’s the fundamental difference to the first, size goal based, solution where at most one list has a different size than the others.

Answer 2

n is the number of elements in the original list
z is the grid size
s = z/n (integer division) gives the base number of items each array should hold
r is the remainder of the integer division

Run a loop for the first z-r arrays appending each with s items in correct order

Run second loop for the last r arrays appending each with s + 1 items in correct order.

Answer 3

Assumption: The following answer would work only with ordered & sequential streams. The question asks to break a sorted list(which is ordered) into smaller sorted lists.

If the stream is unordered, you'll have to order the stream by ways like Stream.sorted().

---

Let's construct a list of 17 elements.

List<Long> sourceList = LongStream.range(0,17).collect(ArrayList::new,ArrayList::add,ArrayList::addAll);

To divide 17 elements into equal sets of 10 lists, we will have to make 7 lists of 2 elements & 3 lists of 1 element.

In other words, 10 equal lists can be created with a min of 1 elements. And 7 extra elements can be added in the 1st 7 lists.

int minElementinEachList = sourceList.size() /10;      //1
int extraElements = sourceList.size() %10;             //7

Till 7(extraElements) lists are created, we can add an extra element in the lists. Use the following code:

AtomicInteger counter = new AtomicInteger(0);
Map<Number,List<Number>> map = sourceList.stream().collect(
    Collectors.groupingBy(it -> {
    int key = counter.getAndIncrement() / (minElementinEachList + 1);
    if(key >= extraElements && (counter.get() + 1) % (minElementinEachList +1 ) == 0){
        counter.getAndIncrement();
    }
    return key;
}));
System.out.println(map);

Output:

{0=[0, 1], 1=[2, 3], 2=[4, 5], 3=[6, 7], 4=[8, 9], 5=[10, 11], 6=[12, 13], 7=[14], 8=[15], 9=[16]}