Java:将列表分成n个随机长度的部分

Question

我正在尝试将列表分成几个部分。我需要找到 n 个整数分布在 k 个组中的所有可能方式。例如，如果我的列表是 {1,2,3,4,5,6,7}，我需要找到可以将其分成 k=3 组的所有方法。我想强调的是，我需要知道所有可能的拆分方式，这对于较大的 n 和/或 k 值来说是一个巨大的数目。但是，我希望这些保持相对较小(个位数)，所以应该没有问题。我有这段代码将列表一分为二:

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);
        }
    }
}

我知道你可以做另一层递归，将子列表拆分成更小的子列表，直到达到所需的子列表数量。但是我没有看到最有效的方法，递归不是我的强项，所以我希望有人能指出我正确的方向。帮助将不胜感激。谢谢。

Answer 1

这里有一个方法:

@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);
        }
    }
}

测试

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();
    }
}

输出

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]