Kartesisches Produkt von zwei Liste mit Hashmaps<String,String> erstellen

[Dorfschmied]

Hallo, ich versuche aus zwei Listen ein Kartesisches Produkt zu bilden, was in etwa wie folgt aussehen soll:
[CODE lang="java" title="Beispiel"]d1 = [{Year = 1976, PersonID = 1},
{Year = 1987, PersonID = 3},
{Year = 1974, PersonID = 2}]

d2 = [{PersonID = 0,houseID = H-101},
{PersonID = 1, houseID = H-202}]

d3 = [{Year = 1976, PersonID = 1,PersonID = 0,houseID = H-101},
{Year = 1976, PersonID = 1,PersonID = 1, houseID = H-202},
{Year = 1987, PersonID = 3,PersonID = 0,houseID = H-101},
{Year = 1987, PersonID = 3,PersonID = 1, houseID = H-202},
{Year = 1974, PersonID = 2,PersonID = 0,houseID = H-101},
{Year = 1974, PersonID = 2,PersonID = 1, houseID = H-202}][/CODE]

Jetzt bin ich mit meinem Code lediglich so weit gekommen:

public static List<Map<String, String>> kartesischesProdukt(List<Map<String, String>> d1, List<Map<String, String>> d2) {
        List<Map<String, String>> result = new ArrayList<>();

        int s1 = d1.size();
        int s2 = d2.size();

        for (int i = 0; i < s1; i++) {
            for (int j = 0; j < s2; j++) {
                d3.add(d1.get(i));
                d3.add(d2.get(j));
            }
        }
        return d3;
    }

Was mir lediglich diesen den Output liefert:

d3 =
d3 = [{Year = 1976, PersonID = 1},{PersonID = 0,houseID = H-101},
    {Year = 1976, PersonID = 1},{PersonID = 1, houseID = H-202},
    {Year = 1987, PersonID = 3},{PersonID = 0,houseID = H-101},
    {Year = 1987, PersonID = 3},{PersonID = 1, houseID = H-202},
    {Year = 1974, PersonID = 2},{PersonID = 0,houseID = H-101},
    {Year = 1974, PersonID = 2},{,PersonID = 1, houseID = H-202}]

Eine neue Hashmap möchte ich nicht erstellen, kann mir jemand weiterhelfen?
LG

 

[kneitzel]

Also irgendwie passt das doch alles nicht. Eine Map ist immer ein key -> value, wobei key eindeutig ist.
Und wenn Du da nun je einen Datensatz von jeder Map hast, dann hast Du als Ergebnis doch kein List<Map>. Du hast dann ja keine Map mehr sondern nur noch 2 einzelne Datensätze - einer aus jeder Map!

Also nur um es noch mal deutlich zu machen:
Du hat map1 und aus der bekommst Du key1, value1.
Und map2 aus der du key2, value2 bekommst.

Im Ergebnis hast Du dann also etwas, bei deren Elementen Du dann key1, value1, key2 und value2 unterbringen musst.

Da beide Maps die gleichen Typen für key und value haben, kannst Du das ggf. zusammen fassen. Dann könntest Du evtl. auf eine List<Map> kommen. Aber list<Map> bedeutet natürlich, dass Du eine Liste von Maps hast -> Du musst also neue Maps erzeugen! Wobei die Frage ist, ob das überhaupt irgend einen Sinn ergibt.

Schauen wir einfach mal auf eine Datenbank: Du hast zwei Tabellen. Das können also einfache Datensatz-Mengen sein. Prinzipiell geht es auch als Map, dann hat man halt einen unique index, z.B. ein primary Key. Wenn Du die dann verknüpfst ohne Bedingung, dann kommt eben das Resultat heraus: Du hast eine "Tabelle" mit den Spalten aus Tabelle1 und Tabelle2. Da hast Du dann aber keinen Primary Key mehr. (Wobei das auch noch denkbar wäre: Eine Kombination aus eben den beiden Primary Keys.)

Das Ergebnis, das man da also jetzt erwarten würde: Du hast zwei mal zwei Spalten -> Liste von 4 Spalten.

 

[httpdigest]

Wenn wir eine Map als Set/Menge von Paaren betrachten (also Key/Value-Paare), dann macht das schon Sinn, denke ich.
Es gibt nur die Einschränkung, dass beim "Mergen" von jeweils zwei Maps/Sets diese Maps Einträge zumselben Schlüssel enthalten könnten (also Paare mit demselben ersten Element). Hier muss man eine Konfliktbehandlung durchführen.
Die Behandlung kann lauten: die "zweite" Map beim Merge überschreibt einfach immer den Eintrag aus der "ersten" Map, oder andersherum oder: Exception
Wenn du zur Implementierung z.B. die Methode Map.merge() verwendest, darfst du die Konfliktbehandlung selbst als Methode implementieren. Wenn du den toMap Collector (mit Streams) verwendest, dann gibt's eine Exception bei duplicate Keys oder, du verwendest auch hier die Überladung mit der expliziten Konfliktbehandlung als Parameter.
Eine mögliche Stream-Implementierung könnte z.B. so aussehen:

Spoiler

import java.util.List;
import java.util.Map;
import static java.util.stream.Collectors.toList;
import static java.util.stream.Collectors.toMap;
import static java.util.stream.Stream.concat;
public class Cartesian {
  private static <K, V> Map<K, V> mergeTwoMaps(
          Map<K, V> a, Map<K, V> b) {
      return concat(a.entrySet().stream(), b.entrySet().stream())
            .collect(toMap(Map.Entry::getKey, Map.Entry::getValue));
  }
  public static <K, V> List<Map<K, V>> cartesianProduct(
          List<Map<K, V>> a, List<Map<K, V>> b) {
      return a.stream()
              .flatMap(ae -> b.stream().map(be -> mergeTwoMaps(ae, be)))
              .collect(toList());
  }

  // test
  public static void main(String[] args) {
      System.out.println(cartesianProduct(
        List.of(Map.of("a", 1, "b", 2), Map.of("a", 3, "b", 4)),
        List.of(Map.of("c", 5, "d", 6), Map.of("c", 7, "d", 8))));
  }
}

 

[kneitzel]

@httpdigest das ist ein interessanter Gesichtspunkt. Aber damit hast Du dann doch nicht die erwartete Lösung, welche ja die 4 Elemente in der Zielmenge zeigt:

 d3 = [{Year = 1976, PersonID = 1,PersonID = 0,houseID = H-101},
    {Year = 1976, PersonID = 1,PersonID = 1, houseID = H-202},
    {Year = 1987, PersonID = 3,PersonID = 0,houseID = H-101},
    {Year = 1987, PersonID = 3,PersonID = 1, houseID = H-202},
    {Year = 1974, PersonID = 2,PersonID = 0,houseID = H-101},
    {Year = 1974, PersonID = 2,PersonID = 1, houseID = H-202}]

Und vom Verständnis her: Ist das, was Du da machst, denn dann noch das Kartesische Produkt? Das ist ja definiert als:
A x B := { (a,b) | a € A, b € B} (€ als Ersatz für das "Element aus" Zeichen genommen ... )

Und A als auch B sind ja Mengen, die sich als 2-Tupel darstellen (Mit zusätzlichen Regeln, die uninteressant sind, da wir die Mengen ja nicht modifizieren wollen sondern nur in der Operation nutzen wollen).

Und ich habe das auch noch einmal schnell nachgeschlagen und dazu https://de.wikipedia.org/wiki/Kartesisches_Produkt überflogen und das schien sich mit meinem Verständnis zu decken.

Das was Du machst ist doch:
A := Vereinigungsmenge der Keys beider Maps
B := Vereinigungsmenge der Values beider Maps (Da bekomme ich leichte Bauchschmerzen - damit wirfst Du ja PersonID und HouseID zusammen in eine Menge .. Sieht nicht vielversprechend aus.
Und von diesen neuen Mengen erstellst Du das kartesische Produkt.

Oder habe ich da jetzt etwas falsch verstanden / übersehen? Da die Antwort von Dir gekommen ist, würde ich erst einmal davon ausgehen, dass ich irgendwas übersehen haben muss.

Edit: Die Formel hat er im Editor schön eingefügt als Bild, aber das scheint nicht geklappt zu haben. Daher einmal in Textform ersetzt. Sorry für die nicht gute Darstellung.

 

[httpdigest]

@kneitzel du hast natürlich 100%ig Recht! 🙂 Ich habe mir seine Beispiele oben gar nicht ganz genau angesehen (leider).
Was er vorhat, geht natürlich dann auch mit Maps nicht, also sowas wie:
{Year = 1987, PersonID = 3,PersonID = 0,houseID = H-101}
PersonID kann ja nicht gleichzeitig 3 und 0 sein.
Er braucht also keine Map, sondern _wirklich_ Tupel/Paare.