java - 按条目的递减顺序生成列表的笛卡尔积(条目为正数,列表已排序)
问题描述
假设我有几个排序的正数列表,例如:
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()
方法中)
该程序按字典顺序生成它们,然后按产品对整个集合进行排序。
问题:有没有一种简单的方法可以首先以正确的顺序实际生成组合?
这样做的原因:我首先没有列表,只有一些排序的数字集合的迭代器。可能很长,长度事先不知道,但已知每个迭代器中的数字都是排序的。
要玩的 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].value() * x.elm[1].value() * x.elm[2].value();
}
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
to 来跟踪索引6-tuple
,以通过额外的 3 个元素来保存索引。)应该很容易将此算法扩展到列表数量大于 3 的问题。
更新
事实上,我们可以证明,在最坏的情况下,如果我们想优化速度,需要 O(N^2) 的存储空间。由于 O(exploration boundary) = O(N^2),我们的存储使用至少只是比最优解大一些的常数因子。
不提供官方证明,但我想用 2D 来解释它,即 2 列出乘法而不是 3。然后,很容易扩展解释。
假设我们有列表 A、B,其中 N 个正数按降序排列。我们将这些 NxN 乘法结果排列在 2D 数组中。例如,当 N = 4 时,它看起来像:
o > o > o > *
v v v v
o > o > * > o
v v v v
o > * > o > o
v v v v
* > o > o > o
每个o
或*
代表一个乘法结果。 >
意思是“大于”。
左上角o
代表A[0] * B[0]
。向右每一步意味着对 使用 +1 索引A[]
,向下每一步意味着对 使用 +1 索引B[]
。对于同一列,A
的索引是相同的。对于同一行,B
的索引是相同的。
考虑*
's:我们只知道A[]
并且B[]
是降序排序的。但我们不知道每一步是如何“下降”的。因此,那些*
可以是任何顺序!这4个中的任何一个!订单。如果您至少不将它们保存在一些预先排序的结构(堆、优先级队列等)中,我们必须一次又一次地读取和比较它(即对这 4 个产品进行排序),这会破坏优化速度假设。
因此,我们已经解释了为什么需要 N 存储。
现在我们需要证明我们的 2D 版本算法(即 2 个列表产品)最多只需要 2N 存储。
我只是想给个提示。完整的证明太长了。例如,如果在我们算法的中间,优先级队列存储的是 4 *
。假设其中一个*
被访问,并且其中两个被插入到队列中,如下:
o > o > o > *
v v v v
o > o > P > N
v v v v
o > * > N > o
v v v v
* > o > o > o
其中P
表示前一个,即从队列中弹出的最大值,N
表示接下来的两个,由与 相邻的每个索引 +1 生成P
。很明显,N
不能将这两个选为最高值(因为其中一个的*
乘积比它们中的每一个都大)。直到那些更高的那些被弹出队列,那些N
不能生成新的进入队列。现在,至少有两个*
“进步”的方向被挡住了!That means when one of the two is selected (ie highest value to pop-out), it can only generate one new product into the queue. 然后队列最多保持在 2N 大小。
将此应用于 3D,我们知道存储应该是 O(N^2)。
更新 “set”实现的存储使用情况
有人可能会问,“集”呢?Set 通常实现为哈希表,与使用的条目数成正比。一个简单的实现可能需要存储所有产品(即 2D 版本为 O(N^2),3D 版本为 O(N^3))。仔细调整以删除从未需要的条目,将使存储需求更小。考虑任何 2D 版本的产品,最多只能被其他 2 个产品访问。即每个产品最多执行两次 Set.Contains() 的测试。如果我们保持计数并删除那些未使用的哈希条目,它将使那些“需要”条目与我们队列中的那些产品非常接近。这意味着,在 2D 版本中,哈希表也使用 O(N) 存储,而在 3D 版本中使用 O(N^2)。
推荐阅读
- python - 捕获主目录中所有子文件夹中的所有 csv 文件 - Python 3.x
- javascript - JQuery 等于或包含字符串值不起作用
- swift - 用户切换 segmentController 索引时如何清理 searchText?
- unity3d - 有没有办法将多分支管道的所有分支只构建到一个目录中?
- javascript - Testcafe t.typeText 默认使用 { paste: true }
- python - Pyinstaller win32ctypes.pywin32.pywintypes.error: (1920, 'LoadLibraryExW', '系统无法访问文件')
- sql - 如何将系统分组依据应用于 SQL Server Management Studio 中的表
- javascript - 添加后“请填写此字段”
- zebra-printers - Zebra 打印机的位图打印性能
- javascript - 如何在 wordpress 主题中从 cdn 添加外部 js 文件和 jq 库?