假设我有几个正数排序列表，例如：
double[] a1 = new double[]{0.70, 0.20, 0.10};
double[] a2 = new double[]{0.80, 0.10, 0.05, 0.05};
double[] a3 = new double[]{0.60, 0.15, 0.14, 0.10, 0.01};
我想按照条目的递减乘积顺序遍历这些数组的笛卡尔积，就像这样：
0000: Combo[product=3.36e-01, vals=[0.70, 0.80, 0.60], indexes=[0, 0, 0]]
0001: Combo[product=9.60e-02, vals=[0.20, 0.80, 0.60], indexes=[1, 0, 0]]
0002: Combo[product=8.40e-02, vals=[0.70, 0.80, 0.15], indexes=[0, 0, 1]]
0003: Combo[product=7.84e-02, vals=[0.70, 0.80, 0.14], indexes=[0, 0, 2]]
0004: Combo[product=5.60e-02, vals=[0.70, 0.80, 0.10], indexes=[0, 0, 3]]
0005: Combo[product=4.80e-02, vals=[0.10, 0.80, 0.60], indexes=[2, 0, 0]]
...
在上面的示例中，第一个条目是显而易见的（对数组进行排序），并且它是第一个值的组合：[0.70, 0.80, 0.60]与乘积0.70*0.80*0.60 = 3.36e-01以及数组a1, a2, a3中的对应值索引为[0, 0, 0]。现在第二个条目不太明显了，我们应该将0.70更改为0.20吗？还是0.60至0.15？还是0.80至0.10？第二个应为[0.20, 0.80, 0.60]，乘积为9.60e-02，索引为[1, 0, 0]。
这里是Java中用于生成/打印它们的程序：https://repl.it/repls/FilthyGreatRotation（所有逻辑都在printWholeCartesianProduct()方法中）该程序按字典顺序生成它们，然后按产品对整个集合进行排序。
问题：首先是否有一种简单的方法可以以正确的顺序实际生成连击？
这样做的原因：首先，我没有列表，只是迭代了一些排序的数字集合。可能是veerery的长度，提前不知道长度，但是已知每个迭代器中的数字都已排序。
要玩的MVCE（与上面的https://repl.it链接中的相同：]
import java.text.DecimalFormat;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.StringJoiner;
import java.util.function.Consumer;
import java.util.stream.Collectors;
public class Main {
public static void main(String[] args) {
List<List<Double>> data = createData();
printWholeCartesianProduct(data);
}
public static List<List<Double>> createData() {
double[] a1 = new double[]{0.70, 0.20, 0.10};
double[] a2 = new double[]{0.80, 0.10, 0.05, 0.05};
double[] a3 = new double[]{0.60, 0.15, 0.14, 0.10, 0.01};
return createData(a1, a2, a3);
}
public static void printWholeCartesianProduct(List<List<Double>> data) {
final DecimalFormat df = new DecimalFormat("0.00");
// print input data
String matrix = data.stream()
.map(l -> l.stream().map(df::format).collect(Collectors.joining(", ")))
.map(row -> "[" + row + "]")
.collect(Collectors.joining("\n"));
System.out.println("Input data:\n" + matrix);
// collect combos as they are generated
final List<Combo> combos = new ArrayList<>();
Consumer<int[]> callback = indexes -> {
double[] v = new double[indexes.length];
double prod = 1;
for (int i = 0; i < indexes.length; i++) {
List<Double> col = data.get(i);
int index = indexes[i];
v[i] = col.get(index);
prod *= v[i];
}
combos.add(new Combo(prod, v, indexes.clone()));
};
// generate combos
int[] c = new int[data.size()];
int ptr = c.length - 1;
while (ptr >= 0) {
callback.accept(c);
c[ptr]++; // increment
if (c[ptr] == data.get(ptr).size()) { // carry
do {
ptr--;
} while(ptr >= 0 && c[ptr] == data.get(ptr).size() - 1);
if (ptr < 0) {
break;
}
c[ptr]++;
// zero out
while (++ptr <= c.length - 1) {
c[ptr] = 0;
}
ptr = c.length - 1;
}
}
// cheating - sort after generation and print result
combos.sort((o1, o2) -> Double.compare(o2.product, o1.product));
StringBuilder sb = new StringBuilder();
double totalP = 0;
for (int i = 0; i < combos.size(); i++) {
sb.append(String.format("%04d: ", i)).append(combos.get(i)).append("\n");
totalP += combos.get(i).product;
}
System.out.printf("Cartesian product in descending product (total p=%.3e):\n%s", totalP, sb.toString());
}
public static List<Double> asList(double[] a) {
return Arrays.stream(a).boxed().collect(Collectors.toList());
}
public static List<List<Double>> createData(double[]... arrays) {
final List<List<Double>> vals = new ArrayList<>();
Arrays.stream(arrays).forEachOrdered(a -> vals.add(asList(a)));
return vals;
}
static class Combo {
final double product;
final double[] vals;
final int[] indexes;
Combo(double product, double[] vals, int[] indexes) {
this.product = product;
this.vals = vals;
this.indexes = indexes;
}
@Override
public String toString() {
return new StringJoiner(", ", Combo.class.getSimpleName() + "[", "]")
.add("product=" + String.format("%.2e", product))
.add("vals=[" + Arrays.stream(vals).boxed().map(v -> String.format("%.2f", v)).collect(
Collectors.joining(", ")) + "]")
.add("indexes=" + Arrays.toString(indexes))
.toString();
}
}
}
我不熟悉Java，但是由于它主要只是一种算法，因此伪代码就足够了：
Input:
Non-empty lists A, B, C: containing positive number(s).
Pseudo-code:
type-define tuple3 = (iterator, iterator, iterator);
function double value(tuple3 x) {
return x.elm[0] * x.elm[1] * x.elm[2];
}
function boolean greater_than (tuple3 x, tuple3 y) {
return (value(x) > value(y));
}
function void main() {
iterator a = A.first();
iterator b = B.first();
iterator c = C.first();
set<tuple3> Visit;
PriorityQueue<tuple3, greater_than> Q;
Q.add((a,b,c));
Visit.add((a,b,c));
while (!Q.empty()) {
tuple x = Q.pop_top();
output(x);
(a, b, c) = x;
if (a.next() != null && !Visit.contains((a.next(), b, c))) {
Q.add((a.next(), b, c));
Visit.add((a.next(), b, c));
}
if (b.next() != null && !Visit.contains((a, b.next(), c))) {
Q.add((a, b.next(), c));
Visit.add((a, b.next(), c));
}
if (c.next() != null && !Visit.contains((a, b, c.next()))) {
Q.add((a, b, c.next()));
Visit.add((a, b, c.next()));
}
}
}
注意，output()功能打印输出行。我并不真正处理索引打印，但这应该很容易，对吗？ （例如，只需通过将3-tuple扩展到6-tuple来跟踪索引，即可通过另外3个元素来保存索引。）应该很容易将此算法扩展到列表数大于3的问题。