您是否知道一些简洁的Java库,允许您制作两个(或更多)集的笛卡尔积？
例如:我有三套.一个是Person类的对象,第二个是类Gift的对象,第三个是GiftExtension类的对象.
我想生成一个包含所有可能的三元组Person-Gift-GiftExtension的集合.
集的数量可能会有所不同,所以我不能在嵌套的foreach循环中执行此操作.在某些情况下,我的应用程序需要制作一个Person-Gift对的产品,有时它是三人Person-Gift-GiftExtension,有时甚至可能会设置Person-Gift-GiftExtension-GiftSecondExtension-GiftThirdExtension等.
1> Michael Myer..： 编辑: 删除了两组的先前解决方案.有关详情,请参阅编辑历史
这是一种递归执行任意数量的集合的方法:
public static Set> 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> _cartesianProduct(int index, Set... sets) {
Set> ret = new HashSet>();
if (index == sets.length) {
ret.add(new HashSet());
} else {
for (Object obj : sets[index]) {
for (Set set : _cartesianProduct(index+1, sets)) {
set.add(obj);
ret.add(set);
}
}
}
return ret;
}
请注意,不可能使用返回的集保留任何泛型类型信息.如果您事先知道要获取多少个集合,那么您可以定义一个通用元组来保存那么多元素(例如Triple),但是没有办法在Java中拥有任意数量的泛型参数.
2> Martin Ander..： 这是一个非常古老的问题,但为什么不使用Guava的cartesianProduct？
因为这是在问题发布后实施的.请参见http://stackoverflow.com/a/1723050/600500.
3> 小智..： 下面的方法创建一个字符串列表列表的笛卡尔积:
protected List> cartesianProduct(List> lists) {
List> resultLists = new ArrayList>();
if (lists.size() == 0) {
resultLists.add(new ArrayList());
return resultLists;
} else {
List firstList = lists.get(0);
List> remainingLists = cartesianProduct(lists.subList(1, lists.size()));
for (T condition : firstList) {
for (List remainingList : remainingLists) {
ArrayList resultList = new ArrayList();
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]]
4> Michael Borg..：
集的数量可能会有所不同,所以我不能在嵌套的foreach循环中执行此操作.
两个提示:
A x B x C = A x(B x C)
递归
5> 小智..： 基于索引的解决方案
使用索引是一种快速且具有内存效率的替代方案,可以处理任意数量的集合.实现Iterable允许在for-each循环中轻松使用.有关用法示例,请参阅#main方法.
public class CartesianProduct implements Iterable, Iterator {
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 iterator() {
return this;
}
public void remove() {
throw new UnsupportedOperationException();
}
/**
* Usage example. Prints out
*
*
* [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
* ...
*
*/
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]]);
}
}
}
京公网安备 11010802040832号