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

algorithm list python java sublist

2022-09-03 07:26:47

我有一个可变大小的列表，例如

[1, 2, 3, 4]

我想用一切可能的方法把这个列表分成两个：

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

我很确定这不是一个未知的问题，可能有一个算法可以解决这个问题，但是我找不到一个。此外，这不应该使用任何外部库，而是使用大多数语言中的简单语言功能（循环，条件，方法/函数，变量等）。

我用Python写了一个黑客解决方案：

def get_all(objects):
    for i in range(1, len(objects)):
        for a in combinations(objects, i):
            for b in combinations([obj for obj in objects if obj not in up], len(objects) - i):
                yield State(up, down)
    if objects:
        yield State([], objects)
        yield State(objects, [])

但是，它使用库功能，并且总体上不是很好看。

答案 1

l = [1, 2, 3, 4]
flags = [False] * len(l)
while True:
    a = [l[i] for i, flag in enumerate(flags) if flag]
    b = [l[i] for i, flag in enumerate(flags) if not flag]
    print a, b
    for i in xrange(len(l)):
        flags[i] = not flags[i]
        if flags[i]:
            break
    else:
        break

结果：

[] [1, 2, 3, 4]
[1] [2, 3, 4]
[2] [1, 3, 4]
[1, 2] [3, 4]
[3] [1, 2, 4]
[1, 3] [2, 4]
[2, 3] [1, 4]
[1, 2, 3] [4]
[4] [1, 2, 3]
[1, 4] [2, 3]
[2, 4] [1, 3]
[1, 2, 4] [3]
[3, 4] [1, 2]
[1, 3, 4] [2]
[2, 3, 4] [1]
[1, 2, 3, 4] []

它可以很容易地适应java：

public static void main(String[] args) {
    int[] l = new int[] { 1, 2, 3, 4 };
    boolean[] flags = new boolean[l.length];
    for (int i = 0; i != l.length;) {
        ArrayList<Integer> a = new ArrayList<>(), b = new ArrayList<>();
        for (int j = 0; j < l.length; j++)
            if (flags[j]) a.add(l[j]); else b.add(l[j]);
        System.out.println("" + a + ", " + b);
        for (i = 0; i < l.length && !(flags[i] = !flags[i]); i++);
    }
}

答案 2

一个更低级的解决方案，使用按位算术来计算应该很容易转换为Java的子集：

def sublists(xs):
    l = len(xs)
    for i in range(1 << l):
        incl, excl = [], []
        for j in range(l):
            if i & (1 << j):
                incl.append(xs[j])
            else:
                excl.append(xs[j])
        yield (incl, excl)