Разделите список на два подсписка всеми возможными способами

У меня есть список переменных размера, например

[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)

Ответ 3

Хотя в Python довольно легко получить результат с помощью обширной библиотеки, на Java вы можете написать рекурсивное решение. Далее будут напечатаны все возможные комбинации вашего массива:

public static void main(String[] args) {
    List<Integer> num = Arrays.asList(1, 2, 3, 4);
    List<List<Integer>> sublists = new ArrayList<List<Integer>>();
    for (int i = 0; i <= num.size(); i++) {
      permutation(num, sublists, i, new ArrayList<Integer>(), 0);
    }

    for (List<Integer> subList : sublists) {
        List<Integer> numCopy = new ArrayList<Integer>(num);
        numCopy.removeAll(subList);
        System.out.println("(" + subList + ", " + numCopy + ")");
    }
}

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

sublists содержит все комбинации, найденные до сих пор. Последним параметром является startIndex для следующего элемента текущего подсписок. То есть, чтобы избежать дублирования.

Ответ 4

Перемещение всех разных комбинаций размеров и "вычитание" их из исходного списка кажется интуитивным подходом IMO:

from itertools import combinations

s = [1, 2, 3, 4]
for combs in (combinations(s, r) for r in range(len(s)+1))  :
    for comb in combs:
        diff = list(set(s[:]) - set(comb))
        print diff, list(comb)

OUTPUT

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

Тот же подход может быть применен к Java (только это более подробный...):

private static List<Integer> initial;

public static void main(String[] args) throws IOException {
    initial = Arrays.asList(1, 2, 3);
    combinations(initial);
}

static void combinations(List<Integer> src) {
    combinations(new LinkedList<>(), src);
}

private static void combinations(LinkedList<Integer> prefix, List<Integer> src) {        
    if (src.size() > 0) {
        prefix = new LinkedList<>(prefix); //create a copy to not modify the orig
        src = new LinkedList<>(src); //copy
        Integer curr = src.remove(0);
        print(prefix, curr); // <-- this is the only thing that shouldn't appear in a "normal" combinations method, and which makes it print the list-pairs
        combinations(prefix, src); // recurse without curr
        prefix.add(curr);
        combinations(prefix, src); // recurse with curr
    }
}

// print the prefix+curr, as one list, and initial-(prefix+curr) as a second list
private static void print(LinkedList<Integer> prefix, Integer curr) {
    prefix = new LinkedList<>(prefix); //copy
    prefix.add(curr);
    System.out.println(Arrays.toString(prefix.toArray()) +
                    " " + Arrays.toString(subtract(initial, prefix).toArray()));
}

private static List<Integer> subtract(List<Integer> initial, LinkedList<Integer> prefix) {
    initial = new LinkedList<>(initial); //copy
    initial.removeAll(prefix);
    return initial;
}

OUTPUT

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