¿Cómo puedo hacer un producto cartesiano con secuencias de Java 8?

java-8 java-stream

Question

Tengo el siguiente tipo de colección:

Map<String, Collection<String>> map;

Me gustaría crear combinaciones únicas de cada uno de map.size() partir de un único valor en la colección para cada Clave.

Por ejemplo, suponga que el mapa tiene el siguiente aspecto:

A, {a1, a2, a3, ..., an}
B, {b1, b2, b3, ..., bn}
C, {c1, c2, c3, ..., cn}

El resultado que me gustaría obtener sería un resultado List<Set<String>> , similar a (ordenar no es importante, solo necesita ser un resultado ''completo'' que conste de todas las combinaciones posibles):

{a1, b1, c1},
{a1, b1, c2},
{a1, b1, c3},
{a1, b2, c1},
{a1, b2, c2},
{a1, b2, c3},
...
{a2, b1, c1},
{a2, b1, c2},
...
{a3, b1, c1},
{a3, b1, c2},
...
{an, bn, cn}

Esto es básicamente un problema de conteo, pero me gustaría ver si es posible una solución usando flujos Java 8.

Answer 1

Aquí hay otra solución, que no utiliza tantas características de Streams como el ejemplo de Tagir; Sin embargo, creo que es más sencillo:

public class Permutations {

    transient List<Collection<String>> perms;

    public List<Collection<String>> list(Map<String, Collection<String>> map) {

        SortedMap<String, Collection<String>> sortedMap = new TreeMap<>();
        sortedMap.putAll(map);

        sortedMap.values().forEach((v) ->  perms = expand(perms, v));

        return perms;
    }

    private List<Collection<String>> expand(List<Collection<String>> list, Collection<String> elements) {

        List<Collection<String>> newList = new LinkedList<>();

        if (list == null) {
            elements.forEach((e) -> {
                SortedSet<String> set = new TreeSet<>();
                set.add(e);
                newList.add(set);
            });
        } else {
            list.forEach((set) ->
                elements.forEach((e) -> {
                    SortedSet<String> newSet = new TreeSet<>();
                    newSet.addAll(set);
                    newSet.add(e);
                    newList.add(newSet);
                }));
        }

        return newList;
    }
}

Puede eliminar el prefijo ordenado si no está interesado en ordenar elementos; Sin embargo, creo que es más fácil depurar si todo está ordenado.

Uso:

Permutations p = new Permutations();
List<Collection<String>> plist = p.list(map);
plist.forEach((s) -> System.out.println(s));

¡Disfrutar!

Answer 2

En bucle crear lista combinada

List<String> cartesianProduct(List<List<String>> wordLists) {

 List<String> cp = wordLists.get(0);

 for (int i = 1; i < wordLists.size(); i++) 
 {      
     List<String> secondList = wordLists.get(i);
     List<String> combinedList = cp.stream().flatMap(s1 -> secondList.stream().map(s2 -> s1 + s2))
                    .collect(Collectors.toList());
        cp = combinedList;

    }
        return cp;
}

Answer 3

Escribí una clase implementando Iterable , y guardando solo el elemento actual en la memoria. Iterable como Iterator se pueden convertir a Stream si se desea.

class CartesianProduct<T> implements Iterable<List<T>> {
    private final Iterable<? extends Iterable<T>> factors;

    public CartesianProduct(final Iterable<? extends Iterable<T>> factors) {
        this.factors = factors;
    }

    @Override
    public Iterator<List<T>> iterator() {
        return new CartesianProductIterator<>(factors);
    }
}

class CartesianProductIterator<T> implements Iterator<List<T>> {
    private final List<Iterable<T>> factors;
    private final Stack<Iterator<T>> iterators;
    private final Stack<T> current;
    private List<T> next;
    private int index = 0;

    private void computeNext() {
        while (true) {
            if (iterators.get(index).hasNext()) {
                current.add(iterators.get(index).next());
                if (index == factors.size() - 1) {
                    next = new ArrayList<>(current);
                    current.pop();
                    return;
                }
                index++;
                iterators.add(factors.get(index).iterator());
            } else {
                index--;
                if (index < 0) {
                    return;
                }
                iterators.pop();
                current.pop();
            }
        }
    }

    public CartesianProductIterator(final Iterable<? extends Iterable<T>> factors) {
        this.factors = StreamSupport.stream(factors.spliterator(), false)
                .collect(Collectors.toList());
        if (this.factors.size() == 0) {
            index = -1;
        }
        iterators = new Stack<>();
        iterators.add(this.factors.get(0).iterator());
        current = new Stack<>();
        computeNext();
    }

    @Override
    public boolean hasNext() {
        if (next == null && index >= 0) {
            computeNext();
        }
        return next != null;
    }

    @Override
    public List<T> next() {
        if (!hasNext()) {
            throw new IllegalStateException();
        }
        var result = next;
        next = null;
        return result;
    }
}

Answer 4

Producto cartesiano en Java 8 con forEach:

List<String> listA = new ArrayList<>();
listA.add("0");
listA.add("1");
List<String> listB = new ArrayList<>();
listB.add("a");
listB.add("b"); 

List<String> cartesianProduct = new ArrayList<>();
listA.forEach(a -> listB.forEach(b -> cartesianProduct.add(a + b)));

cartesianProduct.forEach(System.out::println);
//Output : 0a 0b 1a 1b 

Answer 5

Puede resolver esto usando la cadena recursiva flatMap .

Primero, ya que necesitamos movernos hacia adelante y hacia atrás por los valores del mapa, es mejor copiarlos a la ArrayList (esta no es la copia profunda, en su caso es solo ArrayList de 3 elementos, por lo que el uso de memoria adicional es bajo).

En segundo lugar, para mantener un prefijo de elementos visitados anteriormente, Prefix clase de Prefix inmutable auxiliar:

private static class Prefix<T> {
    final T value;
    final Prefix<T> parent;

    Prefix(Prefix<T> parent, T value) {
        this.parent = parent;
        this.value = value;
    }

    // put the whole prefix into given collection
    <C extends Collection<T>> C addTo(C collection) {
        if (parent != null)
            parent.addTo(collection);
        collection.add(value);
        return collection;
    }
}

Esta es una lista enlazada inmutable muy simple que se puede usar así:

List<String> list = new Prefix<>(new Prefix<>(new Prefix<>(null, "a"), "b"), "c")
                          .addTo(new ArrayList<>()); // [a, b, c];

A continuación, creemos el método interno que encadena flatMaps:

private static <T, C extends Collection<T>> Stream<C> comb(
        List<? extends Collection<T>> values, int offset, Prefix<T> prefix,
        Supplier<C> supplier) {
    if (offset == values.size() - 1)
        return values.get(offset).stream()
                     .map(e -> new Prefix<>(prefix, e).addTo(supplier.get()));
    return values.get(offset).stream()
            .flatMap(e -> comb(values, offset + 1, new Prefix<>(prefix, e), supplier));
}

Parece recurrencia, pero es más complejo: no se llama a sí mismo directamente, sino que pasa lambda que llama al método externo. Parámetros:

• valores: la List de valores originales ( new ArrayList<>(map.values) en su caso).
• offset: el desplazamiento actual dentro de esta lista
• prefijo: el prefijo actual de desplazamiento de longitud (o null si offset == 0 ). Contiene elementos actualmente seleccionados de las colecciones list.get(0) , list.get(1) hasta list.get(offset-1) .
• proveedor: el método de fábrica para crear la colección resultante.

Cuando llegamos al final de la lista de valores ( offset == values.size() - 1 ), offset == values.size() - 1 los elementos de la última colección de los valores a la combinación final utilizando el proveedor. De lo contrario, usamos el flatMap que para cada elemento intermedio amplía el prefijo y vuelve a llamar al método comb para el próximo desplazamiento.

Finalmente, aquí hay un método público para usar esta función:

public static <T, C extends Collection<T>> Stream<C> ofCombinations(
        Collection<? extends Collection<T>> values, Supplier<C> supplier) {
    if (values.isEmpty())
        return Stream.empty();
    return comb(new ArrayList<>(values), 0, null, supplier);
}

Un ejemplo de uso:

Map<String, Collection<String>> map = new LinkedHashMap<>(); // to preserve the order
map.put("A", Arrays.asList("a1", "a2", "a3", "a4"));
map.put("B", Arrays.asList("b1", "b2", "b3"));
map.put("C", Arrays.asList("c1", "c2"));

ofCombinations(map.values(), LinkedHashSet::new).forEach(System.out::println);

Recopilamos combinaciones individuales en LinkedHashSet nuevamente para preservar el pedido. Puede utilizar cualquier otra colección en su lugar (por ejemplo, ArrayList::new ).

Answer 6

Si bien no es una solución Stream, com.google.common.collect.Sets de Guava lo hace por usted

Set<List<String>> result = Sets.cartesianProduct(Set.of("a1","a2"), Set.of("b1","b2"), Set.of("c1","c2" ))

Answer 7

Una respuesta más simple, para una situación más simple en la que solo desea tener el producto cartesiano de los elementos de dos colecciones.

Aquí hay un código que usa flatMap para generar el producto cartesiano de dos listas cortas:

    public static void main(String[] args) {
      List<Integer> aList = Arrays.asList(1,2,3);
      List<Integer> bList = Arrays.asList(4,5,6);

      Stream<List<Integer>> product = aList.stream().flatMap(a -> 
          bList.stream().flatMap(b ->
            Stream.of(Arrays.asList(a, b)))
          );

      product.forEach(p -> { System.out.println(p); });

// prints:
//              [1, 4]
//              [1, 5]
//              [1, 6]
//              [2, 4]
//              [2, 5]
//              [2, 6]
//              [3, 4]
//              [3, 5]
//              [3, 6]
    }

Si desea agregar más colecciones, simplemente anide las transmisiones un poco más:

        aList.stream().flatMap(a -> 
          bList.stream().flatMap(b ->
            cList.stream().flatMap(c ->
               Stream.of(Arrays.asList(a, b, c))))
          );

Answer 8

Una solución que opera principalmente en listas, haciendo las cosas mucho más simples. Realiza una llamada recursiva en flatMap , realiza un seguimiento de los elementos que ya se han combinado y las colecciones de elementos que aún faltan, y ofrece los resultados de esta construcción recursiva anidada como una secuencia de listas:

import java.util.*;
import java.util.stream.Stream;

public class CartesianProduct {

    public static void main(String[] args) {
        Map<String, Collection<String>> map = 
            new LinkedHashMap<String, Collection<String>>();
        map.put("A", Arrays.asList("a1", "a2", "a3", "a4"));
        map.put("B", Arrays.asList("b1", "b2", "b3"));
        map.put("C", Arrays.asList("c1", "c2"));
        ofCombinations(map.values()).forEach(System.out::println);
    }

    public static <T> Stream<List<T>> ofCombinations(
        Collection<? extends Collection<T>> collections) {
        return ofCombinations(
            new ArrayList<Collection<T>>(collections), 
            Collections.emptyList());        
    }       

    private static <T> Stream<List<T>> ofCombinations(
        List<? extends Collection<T>> collections, List<T> current) {
        return collections.isEmpty() ? Stream.of(current) :
            collections.get(0).stream().flatMap(e -> 
            {
                List<T> list = new ArrayList<T>(current);
                list.add(e);
                return ofCombinations(
                    collections.subList(1, collections.size()), list);
            });
    }
}

Answer 9

Use una clase de función de consumidor, una lista y un foreach

    public void tester(){

        String[] strs1 = {"2","4","9"};
        String[] strs2 = {"9","0","5"};

        //Final output is {"29", "49, 99", "20", "40", "90", "25", "45", "95"}
        List<String> result = new ArrayList<>();
        Consumer<String> consumer = (String str) -> result.addAll(Arrays.stream(strs1).map(s -> s+str).collect(Collectors.toList()));
        Arrays.stream(strs2).forEach(consumer);

        System.out.println(result);

}