dividere una lista in due elenchi secondari in tutti i modi possibili

Question

Ho una lista di dimensioni variabili, per esempio

[1, 2, 3, 4] 

e voglio ottenere ogni modo possibile per dividere questa lista in due:

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

Sono abbastanza sicuro che questo non è un problema sconosciuto e probabilmente c'è un algoritmo per questo, ma non sono riuscito a trovarne uno. Inoltre, questo non dovrebbe utilizzare alcuna libreria esterna, ma lavorare con caratteristiche linguistiche semplici (cicli, condizioni, metodi/funzioni, variabili, ...) presenti nella maggior parte delle lingue.

Ho scritto una soluzione hackish in 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, []) 

Tuttavia, utilizza funzioni di libreria e non è molto bello guardare in generale.

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 

risultati:

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

Può essere facilmente adattato a 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

Andando su tutte le diverse dimensioni di combinazioni e "sottraendo" dall'elenco originale sembra intuitivo approccio IMO:

USCITA

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

Lo stesso approccio può essere applicato con Java (solo che è più prolisso ...):

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

USCITA

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

Answer 3

A più bassa -la soluzione a livello usando l'aritmetica bit a bit per contare i sottoinsiemi che dovrebbero essere facili da tradurre in 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

Anche se in Python, è abbastanza facile ottenere il risultato con la sua vasta libreria, in Java, è possibile scrivere una soluzione ricorsiva. Quanto segue stampa tutte le possibili combinazioni di vostro allineamento:

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

Il sublists porta tutte le combinazioni trovate fino ad ora. L'ultimo parametro è il startIndex per l'elemento successivo della sottolista corrente. Questo per evitare duplicati.