Split eine Liste in zwei Teil-Listen auf alle möglichen Arten

Question

ich eine Liste von variabler Größe haben, zum Beispiel

[1, 2, 3, 4] 

und ich möchte jeden möglichen Weg, um diese Liste in zwei Teile zu spalten:

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

Ich bin mir ziemlich sicher, dass dies kein unbekanntes Problem ist und es gibt wahrscheinlich einen Algorithmus dafür, aber ich konnte keinen finden. Außerdem sollte dies keine externen Bibliotheken verwenden, sondern mit einfachen Sprachfunktionen (Schleifen, Bedingungen, Methoden/Funktionen, Variablen, ...) arbeiten, die in den meisten Sprachen gefunden werden.

Ich habe eine hackish Lösung in Python geschrieben:

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

Allerdings verwendet er Bibliotheks-Features und ist nicht sehr schön im Allgemeinen suchen.

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 

Ergebnis:

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

Es kann leicht zu Java angepasst werden:

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

alle gehen über die verschiedenen Größen von Kombinationen und „Subtrahieren“, um sie von der ursprünglichen Liste scheint intuitiv Ansatz 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] 

Der gleiche Ansatz mit Java angewendet werden kann (nur dass es ausführlicher ist ...):

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

Answer 3

Ein niedriger -Level-Lösung mit bitweiser Arithmetik zum Zählen von Teilmengen, die leicht in Java zu übersetzen sein sollten:

Answer 4

Obwohl es in Python sehr einfach ist, das Ergebnis mit seiner umfangreichen Bibliothek zu erhalten, können Sie in Java eine rekursive Lösung schreiben. Im Folgenden werden alle möglichen Kombinationen von Array drucken:

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

Die sublists alle Kombinationen trägt bis jetzt gefunden. Der letzte Parameter ist startIndex für das nächste Element der aktuellen Unterliste. Das heißt, Duplikate zu vermeiden.