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.
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.
Martin Andersson
Dies ist eine ziemlich alte Frage, aber warum nicht verwenden Das kartesische Produkt der Guave?
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]]
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
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]]);
}
}
}
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.
9172300cookie-checkKartesisches Produkt beliebig vieler Mengenyes