Kartesisches Produkt beliebig vieler Mengen

Lesezeit: 9 Minuten

Kartesisches Produkt beliebig vieler Mengen
Spieler

Kennen Sie einige nette Java-Bibliotheken, mit denen Sie ein kartesisches Produkt aus zwei (oder mehr) Mengen erstellen können?

Zum Beispiel: Ich habe drei Sets. Eine mit Objekten der Klasse Person, eine zweite mit Objekten der Klasse Gift und eine dritte mit Objekten der Klasse GiftExtension.

Ich möchte einen Satz generieren, der alle möglichen Tripel Person-Gift-GiftExtension enthält.

Die Anzahl der Sätze kann variieren, daher kann ich dies nicht in einer verschachtelten Foreach-Schleife tun. Unter bestimmten Bedingungen muss meine Anwendung ein Produkt aus einem Person-Geschenk-Paar erstellen, manchmal ist es ein dreifaches Person-Geschenk-Geschenk-Erweiterung, manchmal kann es sogar Sets geben Person-Geschenk-Geschenk-Erweiterung-GiftSecondExtension-GiftThirdExtension usw.

Kartesisches Produkt beliebig vieler Mengen
Michael myers

Bearbeiten: Vorherige Lösungen für zwei Sätze entfernt. Siehe Bearbeitungsverlauf für Details.

Hier ist eine Möglichkeit, dies rekursiv für eine beliebige Anzahl von Mengen zu tun:

public static Set<Set<Object>> cartesianProduct(Set<?>... sets) {
    if (sets.length < 2)
        throw new IllegalArgumentException(
                "Can't have a product of fewer than two sets (got " +
                sets.length + ")");

    return _cartesianProduct(0, sets);
}

private static Set<Set<Object>> _cartesianProduct(int index, Set<?>... sets) {
    Set<Set<Object>> ret = new HashSet<Set<Object>>();
    if (index == sets.length) {
        ret.add(new HashSet<Object>());
    } else {
        for (Object obj : sets[index]) {
            for (Set<Object> set : _cartesianProduct(index+1, sets)) {
                set.add(obj);
                ret.add(set);
            }
        }
    }
    return ret;
}

Beachten Sie, dass es unmöglich ist, generische Typinformationen mit den zurückgegebenen Sätzen beizubehalten. Wenn Sie im Voraus wüssten, aus wie vielen Mengen Sie das Produkt nehmen möchten, könnten Sie ein generisches Tupel definieren, das so viele Elemente enthält (z Triple<A, B, C>), aber es gibt keine Möglichkeit, eine beliebige Anzahl generischer Parameter in Java zu haben.

  • Ich denke, das ist eine wirklich großartige Möglichkeit, mit Paaren umzugehen. Wenn er nicht weiß, ob er möglicherweise Paare, Dreier, Vierer braucht, dann passt es nicht direkt, aber er könnte Pair,GiftExtension> verwenden, denke ich.

    – Lena Schimmel

    3. April 2009 um 15:03 Uhr

  • Der Rückgabetyp sollte sein Set<List<Object>>andernfalls erhalten Sie möglicherweise Sätze unterschiedlicher Größe im Ergebnis (weil Duplikate).

    – Marco

    30. Juli 2019 um 11:31 Uhr

  • Wenn ich das Argument von ändere cartesianProduct an ArrayList werden die kartesischen Produkte in umgekehrter Reihenfolge zurückgegeben. Ich meine, das erste Element des kartesischen Produkts wird das Element der letzten gegebenen Menge sein. Warum ist das so?

    – Muhammad Aschfaq

    13. April 2020 um 8:25 Uhr

  • So ändern Sie die Argumente in ArrayList<ArrayList<Double>> und geben Sie die Methode in zurück ArrayList<ArrayList<Double>> Datentyp? Wenn ich Änderungen vornehme, ändert sich die Reihenfolge des kartesischen Produkts.

    – Muhammad Aschfaq

    13. April 2020 um 9:01 Uhr

  • @MuhammadAshfaq Der wahrscheinlich einfachste Weg ist, die Ausgabe nachträglich neu zu ordnen. Sätze haben keine Ordnung, also befasst sich meine Methode überhaupt nicht mit der Ordnung.

    – Michael myers

    13. April 2020 um 14:48 Uhr

1646263629 1 Kartesisches Produkt beliebig vieler Mengen
Martin Andersson

Dies ist eine ziemlich alte Frage, aber warum nicht verwenden Das kartesische Produkt der Guave?

  • Weil das implementiert wurde, nachdem die Frage gepostet wurde. Siehe stackoverflow.com/a/1723050/600500.

    – Paulo Ebermann

    14. Oktober 2015 um 19:00 Uhr

  • Aktuell ist das die einfachere Lösung 😉

    – Luan Nico

    4. Mai 2017 um 11:24 Uhr

1646263629 576 Kartesisches Produkt beliebig vieler Mengen
Philipp Meister

Die folgende Methode erstellt das kartesische Produkt einer Liste von Zeichenfolgen:

protected <T> List<List<T>> cartesianProduct(List<List<T>> lists) {
    List<List<T>> resultLists = new ArrayList<List<T>>();
    if (lists.size() == 0) {
        resultLists.add(new ArrayList<T>());
        return resultLists;
    } else {
        List<T> firstList = lists.get(0);
        List<List<T>> remainingLists = cartesianProduct(lists.subList(1, lists.size()));
        for (T condition : firstList) {
            for (List<T> remainingList : remainingLists) {
                ArrayList<T> resultList = new ArrayList<T>();
                resultList.add(condition);
                resultList.addAll(remainingList);
                resultLists.add(resultList);
            }
        }
    }
    return resultLists;
}

Beispiel:

System.out.println(cartesianProduct(Arrays.asList(Arrays.asList("Apple", "Banana"), Arrays.asList("Red", "Green", "Blue"))));

würde das ergeben:

[[Apple, Red], [Apple, Green], [Apple, Blue], [Banana, Red], [Banana, Green], [Banana, Blue]]

  • wäre die Zeitkomplexität dafür O(n)^2

    – j2emanue

    22. Januar 2017 um 2:06 Uhr

Die Anzahl der Sätze kann variieren, daher kann ich dies nicht in einer verschachtelten Foreach-Schleife tun.

Zwei Hinweise:

  • A x B x C = A x (B x C)
  • Rekursion

1646263630 435 Kartesisches Produkt beliebig vieler Mengen
Remko Popma

Indexbasierte Lösung

Das Arbeiten mit den Indizes ist eine Alternative, die schnell und speichereffizient ist und eine beliebige Anzahl von Sätzen verarbeiten kann. Die Implementierung von Iterable ermöglicht eine einfache Verwendung in einer for-each-Schleife. Siehe die Methode #main für ein Anwendungsbeispiel.

public class CartesianProduct implements Iterable<int[]>, Iterator<int[]> {

    private final int[] _lengths;
    private final int[] _indices;
    private boolean _hasNext = true;

    public CartesianProduct(int[] lengths) {
        _lengths = lengths;
        _indices = new int[lengths.length];
    }

    public boolean hasNext() {
        return _hasNext;
    }

    public int[] next() {
        int[] result = Arrays.copyOf(_indices, _indices.length);
        for (int i = _indices.length - 1; i >= 0; i--) {
            if (_indices[i] == _lengths[i] - 1) {
                _indices[i] = 0;
                if (i == 0) {
                    _hasNext = false;
                }
            } else {
                _indices[i]++;
                break;
            }
        }
        return result;
    }

    public Iterator<int[]> iterator() {
        return this;
    }

    public void remove() {
        throw new UnsupportedOperationException();
    }

    /**
     * Usage example. Prints out
     * 
     * <pre>
     * [0, 0, 0] a, NANOSECONDS, 1
     * [0, 0, 1] a, NANOSECONDS, 2
     * [0, 0, 2] a, NANOSECONDS, 3
     * [0, 0, 3] a, NANOSECONDS, 4
     * [0, 1, 0] a, MICROSECONDS, 1
     * [0, 1, 1] a, MICROSECONDS, 2
     * [0, 1, 2] a, MICROSECONDS, 3
     * [0, 1, 3] a, MICROSECONDS, 4
     * [0, 2, 0] a, MILLISECONDS, 1
     * [0, 2, 1] a, MILLISECONDS, 2
     * [0, 2, 2] a, MILLISECONDS, 3
     * [0, 2, 3] a, MILLISECONDS, 4
     * [0, 3, 0] a, SECONDS, 1
     * [0, 3, 1] a, SECONDS, 2
     * [0, 3, 2] a, SECONDS, 3
     * [0, 3, 3] a, SECONDS, 4
     * [0, 4, 0] a, MINUTES, 1
     * [0, 4, 1] a, MINUTES, 2
     * ...
     * </pre>
     */
    public static void main(String[] args) {
        String[] list1 = { "a", "b", "c", };
        TimeUnit[] list2 = TimeUnit.values();
        int[] list3 = new int[] { 1, 2, 3, 4 };

        int[] lengths = new int[] { list1.length, list2.length, list3.length };
        for (int[] indices : new CartesianProduct(lengths)) {
            System.out.println(Arrays.toString(indices) //
                    + " " + list1[indices[0]] //
                    + ", " + list2[indices[1]] //
                    + ", " + list3[indices[2]]);
        }
    }
}

1646263630 192 Kartesisches Produkt beliebig vieler Mengen
Benutzer unbekannt

Hier ist ein Iterable, mit dem Sie eine vereinfachte for-Schleife verwenden können:

import java.util.*;

// let's begin with the demo. Instead of Person and Gift, 
// I use the well known char and int. 
class CartesianIteratorTest {

    public static void main (String[] args) {
        List <Object> lc = Arrays.asList (new Object [] {'A', 'B', 'C', 'D'});
        List <Object> lC = Arrays.asList (new Object [] {'a', 'b', 'c'});   
        List <Object> li = Arrays.asList (new Object [] {1, 2, 3, 4});
            // sometimes, a generic solution like List <List <String>>
            // might be possible to use - typically, a mixture of types is 
            // the common nominator 
        List <List <Object>> llo = new ArrayList <List <Object>> ();
        llo.add (lc);
        llo.add (lC);
        llo.add (li);

        // Preparing the List of Lists is some work, but then ...    
        CartesianIterable <Object> ci = new CartesianIterable <Object> (llo);

        for (List <Object> lo: ci)
            show (lo);
    }

    public static void show (List <Object> lo) {
        System.out.print ("(");
        for (Object o: lo)
            System.out.print (o + ", ");
        System.out.println (")");
    }
}

Wie wird es gemacht? Wir brauchen ein Iterable, um die vereinfachte for-Schleife zu verwenden, und ein Iterator muss von dem Iterable zurückgegeben werden. Wir geben eine Liste von Objekten zurück – dies könnte ein Set anstelle von List sein, aber Set hat keinen indizierten Zugriff, daher wäre es etwas komplizierter, es mit Set anstelle von List zu implementieren. Anstelle einer generischen Lösung wäre Object für viele Zwecke gut gewesen, aber Generika erlauben mehr Einschränkungen.

class CartesianIterator <T> implements Iterator <List <T>> {

    private final List <List <T>> lilio;    
    private int current = 0;
    private final long last;

    public CartesianIterator (final List <List <T>> llo) {
        lilio = llo;
        long product = 1L;
        for (List <T> lio: lilio)
            product *= lio.size ();
        last = product;
    } 

    public boolean hasNext () {
        return current != last;
    }

    public List <T> next () {
        ++current;
        return get (current - 1, lilio);
    }

    public void remove () {
        ++current;
    }

    private List<T> get (final int n, final List <List <T>> lili) {
        switch (lili.size ())
        {
            case 0: return new ArrayList <T> (); // no break past return;
            default: {
                List <T> inner = lili.get (0);
                List <T> lo = new ArrayList <T> ();
                lo.add (inner.get (n % inner.size ()));
                lo.addAll (get (n / inner.size (), lili.subList (1, lili.size ())));
                return lo;
            }
        }
    }
}

Die mathematische Arbeit erfolgt in der ‘get’-Methode. Denken Sie an 2 Sätze mit 10 Elementen. Sie haben insgesamt 100 Kombinationen, aufgezählt von 00, 01, 02, … 10, … bis 99. Für 5 x 10 Elemente 50, für 2 x 3 Elemente 6 Kombinationen. Der Modulo der Unterlistengröße hilft dabei, ein Element für jede Iteration auszuwählen.

Iterable i das am wenigsten Interessante hier:

class CartesianIterable <T> implements Iterable <List <T>> {

    private List <List <T>> lilio;  

    public CartesianIterable (List <List <T>> llo) {
        lilio = llo;
    }

    public Iterator <List <T>> iterator () {
        return new CartesianIterator <T> (lilio);
    }
}

Um Iterable zu implementieren, das die for-each-Schleife erlaubt, müssen wir iterator() implementieren, und für Iterator müssen wir hasNext(), next() und remove() implementieren.

Ergebnis:

(A, a, 1, )
(B, a, 1, )
(C, a, 1, )
(D, a, 1, )
(A, b, 1, )
(B, b, 1, )
(C, b, 1, )
(D, b, 1, )
...
(A, a, 2, )
...
(C, c, 4, )
(D, c, 4, )

Hier ist ein Iterator das ergibt das kartesische Produkt eines zweidimensionalen Arrays, wobei die Array-Komponenten die Mengen aus der Frage darstellen (man kann immer tatsächliche Sets zu Arrays):

public class CartesianIterator<T> implements Iterator<T[]> {
    private final T[][] sets;
    private final IntFunction<T[]> arrayConstructor;

    private int count = 0;
    private T[] next = null;

    public CartesianIterator(T[][] sets, IntFunction<T[]> arrayConstructor) {
        Objects.requireNonNull(sets);
        Objects.requireNonNull(arrayConstructor);

        this.sets = copySets(sets);
        this.arrayConstructor = arrayConstructor;
    }

    private static <T> T[][] copySets(T[][] sets) {
        // If any of the arrays are empty, then the entire iterator is empty.
        // This prevents division by zero in `hasNext`.
        for (T[] set : sets) {
            if (set.length == 0) {
                return Arrays.copyOf(sets, 0);
            }
        }
        return sets.clone();
    }

    @Override
    public boolean hasNext() {
        if (next != null) {
            return true;
        }

        int tmp = count;
        T[] value = arrayConstructor.apply(sets.length);
        for (int i = 0; i < value.length; i++) {
            T[] set = sets[i];

            int radix = set.length;
            int index = tmp % radix;

            value[i] = set[index];

            tmp /= radix;
        }

        if (tmp != 0) {
            // Overflow.
            return false;
        }

        next = value;
        count++;

        return true;
    }

    @Override
    public T[] next() {
        if (!hasNext()) {
            throw new NoSuchElementException();
        }

        T[] tmp = next;
        next = null;
        return tmp;
    }
}

Die Grundidee ist zu behandeln count als Zahl mit mehreren Radixen (Ziffer i hat eine eigene Basis, die der Länge von entspricht i‘ten “Satz”). Wann immer wir eine Lösung finden müssen next (das ist wenn hasNext() heißt und next ist null), zerlegen wir die Zahl in diese Multi-Radix in ihre Ziffern. Diese Ziffern werden nun als Indizes verwendet, aus denen wir Elemente aus den verschiedenen Mengen ziehen.

Beispielanwendung:

String[] a = { "a", "b", "c"};
String[] b = { "X" };
String[] c = { "r", "s" };

String[][] abc = { a, b, c };

Iterable<String[]> it = () -> new CartesianIterator<>(abc, String[]::new);
for (String[] s : it) {
    System.out.println(Arrays.toString(s));
}

Ausgabe:

[a, X, r]
[b, X, r]
[c, X, r]
[a, X, s]
[b, X, s]
[c, X, s]

Wenn man Arrays nicht mag, lässt sich der Code trivialerweise in die Verwendung von Sammlungen umwandeln.

Ich denke, dies ist mehr oder weniger ähnlich der Antwort von “Benutzer unbekannt”, nur ohne Rekursion und Sammlungen.

917230cookie-checkKartesisches Produkt beliebig vieler Mengen

This website is using cookies to improve the user-friendliness. You agree by using the website further.

Privacy policy