Java: split list into n parts of random length

Question

I'm trying to split a list into several parts. I need to find all possible ways n integers can be distributed over k groups. For example, if my list is {1,2,3,4,5,6,7}, I need to find all ways this can be split into k=3 groups. I want to emphasise that I need to know all possible ways things can be split, which becomes a massive amount for large values of n and/or k. However, I expect these to stay relatively small (single digits), so there should be no problem. I have this piece of code that splits the list in two:

List<List<Integer>> results;        

public void findAllSublists(List<Integer> list, int minimalLengthOfSublist) {
    results = new ArrayList<List<Integer>>();
    List<List<Integer>> sublists = new ArrayList<List<Integer>>();
    for (int i = 0; i <= list.size(); i++) {
        recursiveSublist(list, sublists, i, new ArrayList<Integer>(), 0);
    }
    for (List<Integer> subList : sublists) {
        if (subList.size() >= minimalLengthOfSublist) {
            results.add(subList);
        }
    }       
}
private static void recursiveSublist(List<Integer> list, List<List<Integer>> subLists, int sublistSize, List<Integer> currentSubList, int startIndex) {
    if (sublistSize == 0) {
        subLists.add(currentSubList);
    } else {
        sublistSize--;
        for (int i = startIndex; i < list.size(); i++) {
            List<Integer> newSubList = new ArrayList<Integer>(currentSubList);
            newSubList.add(list.get(i));
            recursiveSublist(list, subLists, sublistSize, newSubList, i + 1);
        }
    }
}

I realise you might do another level of recursion, splitting sublists into smaller sublists until the desired amount of sublists is achieved. But I am failing to see the most efficient way of doing this, recursion not being my strong suit and all, so I was hoping someone could point me in the right direction. Help would be much appreciated. Thank you.

Answer 1

Here is a way to do it:

@SuppressWarnings("unchecked")
private static List<List<List<Integer>>> split(List<Integer> list, int groups) {
    if (groups <= 0 || groups > list.size())
        throw new IllegalArgumentException("Invalid number of groups: " + groups +
                                           " (list size: " + list.size() + ")");
    List<List<List<Integer>>> result = new ArrayList<>();
    split(list, 0, new List[groups], 0, result);
    return result;
}
private static void split(List<Integer> list, int listIdx,
                          List<Integer>[] combo, int comboIdx,
                          List<List<List<Integer>>> result) {
    if (combo.length - comboIdx == 1) {
        combo[comboIdx] = list.subList(listIdx, list.size());
        result.add(new ArrayList<>(Arrays.asList(combo)));
    } else {
        for (int i = 0; i <= (list.size() - listIdx) - (combo.length - comboIdx); i++) {
            combo[comboIdx] = list.subList(listIdx, listIdx + 1 + i);
            split(list, listIdx + 1 + i, combo, comboIdx + 1, result);
        }
    }
}

Test

public static void main(String[] args) {
    test(Arrays.asList(1,2,3,4,5), 2);
    test(Arrays.asList(1,2,3,4,5,6,7), 3);
}
private static void test(List<Integer> list, int groups) {
    System.out.println("Split of " + list + " into " + groups + " groups:");
    for (List<List<Integer>> combo : split(list, groups)) {
        String sep = "  ";
        for (List<Integer> group : combo) {
            System.out.print(sep + group);
            sep = ", ";
        }
        System.out.println();
    }
}

Output

Split of [1, 2, 3, 4, 5] into 2 groups:
  [1], [2, 3, 4, 5]
  [1, 2], [3, 4, 5]
  [1, 2, 3], [4, 5]
  [1, 2, 3, 4], [5]
Split of [1, 2, 3, 4, 5, 6, 7] into 3 groups:
  [1], [2], [3, 4, 5, 6, 7]
  [1], [2, 3], [4, 5, 6, 7]
  [1], [2, 3, 4], [5, 6, 7]
  [1], [2, 3, 4, 5], [6, 7]
  [1], [2, 3, 4, 5, 6], [7]
  [1, 2], [3], [4, 5, 6, 7]
  [1, 2], [3, 4], [5, 6, 7]
  [1, 2], [3, 4, 5], [6, 7]
  [1, 2], [3, 4, 5, 6], [7]
  [1, 2, 3], [4], [5, 6, 7]
  [1, 2, 3], [4, 5], [6, 7]
  [1, 2, 3], [4, 5, 6], [7]
  [1, 2, 3, 4], [5], [6, 7]
  [1, 2, 3, 4], [5, 6], [7]
  [1, 2, 3, 4, 5], [6], [7]

Answer 2

If my understanding is correct this is what you look for:

import java.util.Arrays;

public class Combination {
    public static void main(String[] args){
        String[] arr = {"A","B","C","D","E","F"};
        combinations2(arr, 3, 0, new String[3]);
    }

    static void combinations2(String[] arr, int len, int startPosition, String[] result){
        if (len == 0){
            System.out.println(Arrays.toString(result));
            return;
        }       
        for (int i = startPosition; i <= arr.length-len; i++){
            result[result.length - len] = arr[i];
            combinations2(arr, len-1, i+1, result);
        }
    }       
}

found it in this thread: Algorithm to return all combinations of k elements from n

I hope it helps.