以所有可能的方式将列表拆分为 n 个子列表

Question

我想在 Java.

中以所有可能的方式将一个列表拆分为给定数量的 n 个子列表

例如 [1, 2, 3, 4]，其中 n = 3 将包括以下列表（但不是完整的解决方案 - 完整的解决方案需要更多 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])
...

等等

我从另一个类似的问题 (Split a list into two sublists in all possible ways) 中改编了一个解决方案，但它只适用于创建 2 个子列表的列表，我正在努力掌握如何为灵活而不是硬编码数量的子列表实现它。

这是我的代码：

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

我需要创建 n 个 EGroup 对象以添加到 listOfEGroupPairs 而不是硬编码的 2 个，但是如何在每个循环中始终获得正确数量 (n) 的不同大小的子列表？

Answer 1

您有 K 个元素，每个元素都可能属于 N 个列表中的任何一个。所以有 N^K 变体，我们可以将整数值从 0 映射到 N^K-1 到像 N 元数字系统这样的分布。

另一种方法 - 递归地将每个元素插入 N 个列表。

我可以用 Python 代码 recursive, N-ary 演示方法，希望它可以翻译成 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)

Answer 2

如果我正确理解问题，原始列表的每个元素都可以在任何 n 子列表中结束。这意味着，有 n^s 个可能的子列表（s 是原始列表中的元素数），可以在一个简单的循环中枚举。通过一些模数和整数除法，您可以获得每个元素的正确“桶”并相应地准备结果。

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

Answer 3

使用递归。

对于 n 等于 0 或负数的任务是不可能的。要么抛出异常，要么 return 一个空的子列表列表。特殊情况：如果 n 为 0 且列表为空，您可能会争辩说子列表的空列表是有效响应。

如果 n 为 1，唯一的解决方案就是整个列表。

对于n > 1：

如果列表的长度为4（例如[1, 2, 3, 4]），则有5个可能的第一个列表。通常有 list.length + 1 个可能的第一个子列表。找到他们。对于每个这样的子列表，进行递归调用，将列表的其余部分和 n - 1 作为参数传递，以查找由列表的其余部分组成的子列表的所有可能组合。将每个第一个子列表与每个剩余子列表的组合组合以形成完整的解决方案。

PS 草图的解决方案只会按照它们在原始列表中的顺序生成子列表。所以解决方案将包括 ([],[1],[2,3,4]) 和 ([1],[2,3,4], [])，但不包括 ([4],[],[1,2,3])。要将最后一个视为单独的解决方案，您还需要找到每个解决方案的所有排列，进而考虑到某些子列表可能相等，因此交换它们不会产生不同的解决方案。

以所有可能的方式将列表拆分为 n 个子列表

Split a list into n sublists in all possible ways

java

algorithm

sublist