Evenly distribute lists into sublists in Java

Question

I want to evenly distribute a list into a given number of sublists. For example, I have a list with elements 1 to 10 and I want 3 lists. These should look like:

SL1 -> {1, 2, 3, 4}
SL2 -> {5, 6, 7}
SL3 -> {8, 9, 10}

Important: What each list contains is not relevant, i.e. SL1 could have {1, 5, 7, 10}. The most important thing is that there are 2 lists with size 3 and 1 list with size 4.

I have tried several things, including the Iterables.partition but that won't help.

The only thing I've come up with that works is:

public Iterable<List<Integer>> distributeEvenlyQueryListIntoLists(final LinkedList<Integer> bigList, final Integer numberOfSublists) {
    List<List<Integer>> result = new ArrayList<>();

    // Creates as many lists as needed
    for (int i = 0; i < numberOfSublists; i++) {
        result.add(new ArrayList<>());
    }

    while (bigList.iterator().hasNext()) {
        for (int i = 0; i < numberOfSublists; i++) {
            if (!bigList.iterator().hasNext()) {
                break;
            }
            result.get(i).add(bigList.poll());
        }
    }
    return result;
}

The passed bigList does not have to be a LinkedList, it can be any Iterable.

I especially hate the first loop where I create the sublists.

Thanks!


Show source
| java   | arrays   | algorithm   2016-12-22 17:12 2 Answers

Answers ( 2 )

  1. 2016-12-22 17:12

    Just distribute them in a round-robin pattern:

    public <T> List<List<T>> partition(Iterable<T> iterable, int partitions){
        List<List<T>> result = new ArrayList<>(partitions);
        for(int i = 0; i < partitions; i++)
            result.add(new ArrayList<>());
    
        Iterator<T> iterator = iterable.iterator()
        for(int i = 0; iterator.hasNext(); i++)
            result.get(i % partitions).add(iterator.next());
    
        return result;
    }
    

    A sample run with this code:

    List<String> l = Stream.iterate(0, i->i + 1).limit(25).map(i->Integer.toString(i)).collect(Collectors.toList());
    System.out.println(partition(l, 4).toString());
    

    Produces

    [[0, 4, 8, 12, 16, 20, 24], [1, 5, 9, 13, 17, 21], [2, 6, 10, 14, 18, 22], [3, 7, 11, 15, 19, 23]]

    The basic idea is to add a single element to each list in the result set roundwise. This way it's guaranteed that the difference in the number of elements between two lists never exceeds 1.

    As an alternative you could use guavas implementation of Iterables.partition, which takes a slightly different approach.

  2. 2016-12-22 18:12

    If you hate creating sublists, that implies you're looking for a fast solution. If you have the original List, and you plan on not altering the original List, consider List.subList().

    int subSize = bigList.length() / numSubs;
    int numBigSubs = 0; // # of subs that need to be one bigger
    if (bigList.length() % numSubs > 0) {
         subSize++;
         numBigSubs = bigList.length() % numSubs;
    }
    int from = 0;
    int to  = subSize;
    List<List<Integer>> subList = new ArrayList<List<Integer>>(numSubs);
    for (int i = 0; i < numSubs; i++) {
        List<Integer> newSub = bigList.subList(from, to);
        subList.add (newSub);
        from = to;
        to += subSize;
        if (i >= numBigSubs && numBigSubs > 0) to--; 
    }
    

    Note: I wrote this without testing - if it fails, I apologize, and hope someone will edit it to work.

    Again, the big upside to this is that it should be wicked fast - all the sublists are simply views into the larger one. The downside is that if you change the list, all bets are off.

◀ Go back