Split a list into n sublists in all possible ways

Question

I want to split a list into a given number n sublists in all possible ways in Java.

For example [1, 2, 3, 4] where n = 3 would include the following lists (but would not be a complete solution - complete would require much more space):

([], [], [1,2,3,4])
([],[1],[2,3,4])
([],[1,2],[3,4])
([],[1,2,3],[4])
([],[1,2,3,4],[])
([1],[2,3,4], [])
([1],[2,3],[4])
([2,3],[4],[1])
([4],[],[1,2,3])
...

etc

I adapted a solution from another similar question (Split a list into two sublists in all possible ways) however it only works for creating lists of 2 sublists and I am struggling to grasp how to implement it for a flexible rather than hardcoded number of sublists.

Here is my code:

public List<List<EGroup>> permutation(List<E> list) {
        List<List<E>> sublists = new ArrayList<List<E>>();
        for (int i = 0; i <= list.size(); i++) {
          permutationSplit(list, sublists, i, new ArrayList<E>(), 0);
        }

        List<List<EGroup>> listOfEGroupPairs = new ArrayList<List<EGroup>>();
       
        for (List<E> subList : sublists) {
            List<E> listCopy = new ArrayList<E>(list);
            listCopy.removeAll(subList);
            EGroup e1 = new EGroup(subList);
            EGroup e2 = new EGroup(listCopy);   
            List<EGroup> egr = new ArrayList<EGroup>();
            egr.add(e1);
            egr.add(e2);
            listOfEGroupPairs.add(egr);
        }
        
        return listOfEGroupPairs;
    }

   
    public void permutationSplit(List<E> list, List<List<E>> subLists, int sublistSize, List<E> currentSubList,
          int startIndex) {
        if (sublistSize == 0) {
          subLists.add(currentSubList);
        } else {
          sublistSize--;
          for (int i = startIndex; i < list.size(); i++) {
            List<E> newSubList = new ArrayList<E>(currentSubList);
            newSubList.add(list.get(i));
            permutationSplit(list, subLists, sublistSize, newSubList, i + 1);
          }
        }
    }

I need to create n number of EGroup objects to add to listOfEGroupPairs rather than the hardcoded 2, but how to always get the right number (n) of sublists of varied size each loop?

You have not listed sublists like [1,4],[2,3] - do you need them or you want to preserve order? — MBo, Jul 06 '20 at 11:48
Sorry, I'll edit the question to be more clear. I do not want to preserve order, and want all possible combinations. Although ideally, combinations within each sublist are unnecessary eg ([1,4],[2,3],[]) and ([4,1],[2,3],[]) are the same, but my current 2 sublist solution does not account for that and I can account for it later on — ie208, Jul 06 '20 at 13:56

MBo · Answer 1 · 2020-07-06T14:25:32.173

You have K elements and each might fall into any of N lists. So there are N^K variants and we can just map integer values from 0 to N^K-1 to distributions like N-ary numeral system.

Another approach - recursively insert every element into N lists.

I can demonstrate approaches with Python code recursive, N-ary and hope it might be translated to Java

def recdistr(K, N, level, ls):
    if level == K:
        print(ls)
    else:
        for i in range(N):
            ls[i].append(level)
            recdistr(K, N, level + 1, ls)   #recursive call with changed list
            ls[i].pop()  #remove last added element to revert list to previous state

K = 4
N = 3
lst = [[] for _ in range(N)]
recdistr(K, N, 0, lst)

def mapdistr(K, N):
    for x in range(N**K):
        t = x
        l = [[] for _ in range(N)]
        for i in range(K):
            id = t % N
            t = t // N   #integer division
            l[id].append(i)
        print(l)

 mapdistr(K, N)

@tobias_k Yours is in Java, so might be more convenient for author — MBo, Jul 06 '20 at 14:32

score 0 · Accepted Answer · answered Jul 06 '20 at 14:28

If I understand the question correctly, each element of the original list can end up in any of the n sublists. That means, there are n^s possible sublists (s being the number of elements in the original list), which can be enumerated in a simple loop. With a bit of modulo and integer division you can then get the proper "bucket" for each element and prepare the results accordingly.

public <T> List<List<List<T>>> partition(List<T> lst, int n) {
    var result = new ArrayList<List<List<T>>>();
    // k = SUM ( pos of lst[i] * n^i ) 
    for (int k = 0; k < Math.pow(n, lst.size()); k++) {
        // initialize result
        List<List<T>> res = IntStream.range(0, n)
                .mapToObj(i -> new ArrayList<T>())
                .collect(Collectors.toList());
        // distribute elements to sub-lists
        int k2 = k;
        for (int i = 0; i < lst.size(); i++) {
            res.get(k2 % n).add(lst.get(i));
            k2 /= n;
        }
        result.add(res);
    }
    return result;
}

score 0 · Answer 3 · edited Dec 13 '21 at 07:43

Use recursion.

For n equal to 0 or negative the task is impossible. Either throw an exception or return an empty lists of lists of sublists. Corner case: if n is 0 and the list is empty, you may argue that the empty list of sublists is a valid response.

If n is 1, the only solution is trivially the entire list.

For n > 1:

If the length of the list is 4 (for example [1, 2, 3, 4]), there are 5 possible first lists. In general there are list.length + 1 possible first sublists. Find them. For each such sublist make a recursive call passing the remainder of the list and n - 1 as arguments to find all possible combinations of sublists made from the remainder of the list. Combine each first sublist with each combination of remaining sublists to form a full solution.

PS The solution as sketched will only produce sublists in the order they come in the original list. So the solution will include ([],[1],[2,3,4]) and ([1],[2,3,4], []), but not ([4],[],[1,2,3]). To regard the last one as a separate solution, you will additionally need to find all permutations of each solution, in turn taking into account that some sublists may be equal and hence swapping them won’t make a distinct solution.

Split a list into n sublists in all possible ways

3 Answers3