Enumeration Kombinationen von K-Elementen mit Java 8

Question

Wie ist es mit einer Instanz von List<E> unter Verwendung von Java 8-Features möglich, eine List<List<E>> zu erstellen, die alle möglichen Kombinationen von k Elementen der ursprünglichen Liste aufzählt?

Answer 1

Dies ist ein Algorithmus, der ich für die Lösung einige Euler Projekt Probleme hat geschrieben:

public static <E> Stream<List<E>> combinations(List<E> l, int size) { 
    if (size == 0) { 
     return Stream.of(Collections.emptyList()); 
    } else { 
     return IntStream.range(0, l.size()).boxed(). 
      <List<E>> flatMap(i -> combinations(l.subList(i+1, l.size()), size - 1).map(t -> pipe(l.get(i), t))); 
    } 
} 

private static <E> List<E> pipe(E head, List<E> tail) { 
    List<E> newList = new ArrayList<>(tail); 
    newList.add(0, head); 
    return newList; 
} 

Es dauert eine List<E> und eine Größe und gibt alle Kombinationen der Liste der Größe size als Stream<List<E>>.

Es ist ein rekursiver Algorithmus: Die Idee ist, die Kombinationen der Größe size - 1 auf allen Elementen der Liste mit Ausnahme der ersten zu berechnen. Wenn Sie alle haben, fügen Sie einfach das erste Element hinzu, das Sie am Anfang jeder Kombination entfernt haben. Sie suchen dann nach allen Kombinationen der Größe size - 1 auf allen Elementen der Liste mit Ausnahme der ersten und der zweiten, und wenn Sie alle haben, fügen Sie das zweite Element zurück. Dies wird fortgesetzt, bis Sie size = 0 erreichen, wo Sie nur leere Kombinationen zurückgeben. Beachten Sie, dass diese Methode "Duplikate" zurückgibt (wenn die Kombination (a, b, c) zurückgegeben wird und (b, c, a) nicht zurückgegeben wird).

Sie haben nicht erwähnt, ob Duplikate enthalten sein sollten. Es ist nicht schwierig, diesen Algorithmus so zu ändern, dass er Duplikate enthält. Die Logik ist ein bisschen anders.

public static <E> Stream<List<E>> combinationsDupl(List<E> l, int size) { 
    if (size == 0) { 
     return Stream.of(Collections.emptyList()); 
    } else { 
     return l.stream().<List<E>> flatMap(h -> combinationsDupl(subtract(l, h), size - 1).map(t -> pipe(h, t))); 
    } 
} 

private static <E> List<E> pipe(E head, List<E> tail) { 
    List<E> newList = new ArrayList<>(tail); 
    newList.add(0, head); 
    return newList; 
} 

private static <E> List<E> subtract(List<E> list, E e) { 
    List<E> newList = new ArrayList<>(list); 
    newList.remove(e); 
    return newList; 
} 

Diesmal durchlaufen Sie alle Elemente in der Eingabeliste. Für jede von ihnen berechnen Sie die Kombinationen der Liste, in der dieses Element entfernt wird. Dann, wenn Sie alle haben, fügen Sie es jeder Kombination erneut hinzu.

Answer 2

Diese Lösung nicht rekursiv ist (was macht es ein bisschen klarer) und faul, aber die zurückgegebenen Kombinationen sind nicht durch eine Erhöhung Länge bestellt:

public class Combinations { 

    public static void main(String[] args) { 
     System.out.println(
       getCombinationsStream(Arrays.asList(1, 2, 3)) 
         .collect(Collectors.toList())); 
     // prints: [[1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]] 
    } 

    public static <T> Stream<List<T>> getCombinationsStream(List<T> list) { 
     // there are 2^list.size() possible combinations 
     // stream through them and map the number of the combination to the combination 
     return LongStream.range(1 , 1 << list.size()) 
       .mapToObj(l -> bitMapToList(l, list)); 
    } 

    public static <T> List<T> bitMapToList(long bitmap, List<T> list) { 
     // use the number of the combination (bitmap) as a bitmap to filter the input list 
     return IntStream.range(0, list.size()) 
       .filter(i -> 0 != ((1 << i) & bitmap)) 
       .mapToObj(list::get) 
       .collect(Collectors.toList()); 
    } 
} 

EDIT: nur Kombinationen von einer bestimmten Länge zu erhalten, fügen Sie ein .filter() in irgendwo.