2 つ (またはそれ以上) のセットのデカルト積を作成できる Java ライブラリをいくつか知っていますか?
例: 私は 3 つのセットを持っています。1 つは Person クラスのオブジェクト、2 番目は Gift クラスのオブジェクト、3 番目は GiftExtension クラスのオブジェクトです。
考えられるすべてのトリプル Person-Gift-GiftExtension を含む 1 つのセットを生成したいと考えています。
セットの数は異なる場合があるため、ネストされた foreach ループではこれを行うことができません。いくつかの条件下では、私のアプリケーションは Person-Gift ペアの製品を作成する必要があります。時には、Person-Gift-GiftExtension が 3 つである場合もあれば、Person-Gift-GiftExtension-GiftSecondExtension-GiftThirdExtension などのセットが存在する場合もあります。
以下のメソッドは、文字列のリストのリストのデカルト積を作成します。
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;
}
例：
System.out.println(cartesianProduct(Arrays.asList(Arrays.asList("Apple", "Banana"), Arrays.asList("Red", "Green", "Blue"))));
これが得られます：
[[Apple, Red], [Apple, Green], [Apple, Blue], [Banana, Red], [Banana, Green], [Banana, Blue]]
セットの数は異なる場合があるため、ネストされた foreach ループではこれを行うことができません。
2 つのヒント:
インデックスベースのソリューション
インデックスの操作は、高速でメモリ効率が高く、任意の数のセットを処理できる代替手段です。Iterable を実装すると、for-each ループで簡単に使用できます。使用例については #main メソッドを参照してください。
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]]);
}
}
}
これは、単純化された for ループを使用できる Iterable です。
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 (")");
}
}
それはどのように行われますか？単純化された for ループを使用するには Iterable が必要であり、Iterator は Iterable から返される必要があります。オブジェクトのリストを返します - これはリストではなくセットでもかまいませんが、セットにはインデックス付きアクセスがないため、リストではなくセットで実装するのは少し複雑です。ジェネリック ソリューションの代わりに、オブジェクトは多くの目的で問題ありませんでしたが、ジェネリックではより多くの制限が可能です。
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;
}
}
}
}
数学的な作業は「get」メソッドで行われます。10要素の2セットについて考えてください。00、01、02、... 10、... から 99 まで列挙された合計 100 の組み合わせがあります。5 X 10 要素の場合は 50、2 X 3 要素の場合は 6 つの組み合わせです。サブリスト サイズのモジュロは、反復ごとに 1 つの要素を選択するのに役立ちます。
Iterable i ここで最も興味深いこと:
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);
}
}
for-each の種類のループを可能にする Iterable を実装するには、iterator () を実装する必要があり、Iterator には hasNext ()、next ()、および remove () を実装する必要があります。
結果：
(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, )
Iteratorこれは、2 次元配列のデカルト積を与えるです。ここで、配列コンポーネントは質問のセットを表します (常に実際Setの s を配列に変換できます)。
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;
}
}
基本的な考え方は、多基数として扱うことですcount(数字には、 「第 1 セット」iの長さに等しい独自の基数があります)。i解決する必要があるときはいつでもnext(つまり、hasNext()が呼び出されてnextisである場合null)、数値をこの複数基数の数字に分解します。これらの数字は、さまざまなセットから要素を描画するためのインデックスとして使用されます。
使用例:
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));
}
出力：
[a, X, r]
[b, X, r]
[c, X, r]
[a, X, s]
[b, X, s]
[c, X, s]
配列が気に入らなければ、コードは簡単にコレクションを使用するように変換できます。
これは、再帰とコレクションがないだけで、「ユーザー不明」の回答と多かれ少なかれ似ていると思います。