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

Question

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

[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编写的一个hackish的解决方案：

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

但是，它使用的库功能，但非常好看一般。

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

Answer 2

去在所有不同尺寸的组合，并从原来的列表“中减去”他们似乎直觉方法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) 

输出

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

输出

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

Answer 3

更低廉使用按位算术计算应易于转换为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) 

Answer 4

虽然在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。这是为了避免重复。