如果问题实例有N个集合需要穿越,则可以将乘积中的元组视为N维“矩形”网格,其中每个元组对应一个网格元素。您将从发出位于网格角落处的最大和元组[9,4,5]开始。
您将跟踪“候选集”,这些未发出的元组在每个维度上都比已发出的至少小1。如果有帮助,您可以将已发出的元组视为网格中的“实体”。候选集是所有接触实体表面的元组。
您将重复从候选集中选择要发出的下一个元组,然后使用新发出的元组的邻居更新集合。当集合为空时,您就完成了。
在发出[9,4,5]后,候选集为
[8,4,5] (one smaller on first dimension)
[9,2,5] (one smaller on second dimension)
[9,4,1] (one smaller on third dimension)
下一步是发出这些数字之和最大的一个,即[8,4,5]。与此相邻的是:
[0,4,5], [8,2,5], [8,4,1]
将这些添加到候选集中,现在我们有:
[9,2,5], [9,4,1], [0,4,5], [8,2,5], [8,4,1]
再次选择最高的总和。这是 [9,2,5]。相邻的是
[8,2,5], [9,2,1].
所以新的候选集是:
[9,4,1], [0,4,5], [8,2,5], [8,4,1], [9,2,1]
注意 [8,2,5] 再次出现。请勿重复。
这次的最大和是 [8,2,5]。相邻元素有
[0,2,5], [8,2,1]
此时您应该已经有了想法。
使用最大堆来处理候选集。然后查找具有最大总和的元组需要 O(log |C|) 的时间,其中 C 是候选集。
这个集合可以有多大?这是一个有趣的问题。我会让你自己思考一下。对于您示例中的三个输入集,它是
|C| = O(|A1||A2| + |A2||A3| + |A1||A3|)
每个元组的发射成本为:
O(log(|A1||A2| + |A2||A3| + |A1||A3|))
如果集合大小不超过N,则时间复杂度为O(log 3 N^2) = O(log 3 + 2 log N) = O(log N)。
需要发出|A1||A2||A3|个元组,时间复杂度为O(N^3)。
生成所有元组并排序的简单算法的时间复杂度为O(log N^3) = O(3 log N) = O(log N)。它只比更复杂的算法慢大约50%,在渐近意义下是相同的。更复杂算法的主要优势是它节省了O(N)的空间,堆/优先队列大小仅为O(N^2)。
以下是一个代码量小的Java实现。
import java.util.Arrays;
import java.util.HashSet;
import java.util.PriorityQueue;
import java.util.Set;
public class SortedProduct {
final SortedTuple [] tuples;
final NoDupHeap candidates = new NoDupHeap();
SortedProduct(SortedTuple [] tuple) {
this.tuples = Arrays.copyOf(tuple, tuple.length);
reset();
}
static class SortedTuple {
final int [] elts;
SortedTuple(int... elts) {
this.elts = Arrays.copyOf(elts, elts.length);
Arrays.sort(this.elts);
}
@Override
public String toString() {
return Arrays.toString(elts);
}
}
class RefTuple {
final int [] refs;
final int sum;
RefTuple(int [] index, int sum) {
this.refs = index;
this.sum = sum;
}
RefTuple getSuccessor(int i) {
if (refs[i] == 0) return null;
int [] newRefs = Arrays.copyOf(this.refs, this.refs.length);
int j = newRefs[i]--;
return new RefTuple(newRefs, sum - tuples[i].elts[j] + tuples[i].elts[j - 1]);
}
int [] getTuple() {
int [] val = new int[refs.length];
for (int i = 0; i < refs.length; ++i)
val[i] = tuples[i].elts[refs[i]];
return val;
}
@Override
public int hashCode() {
return Arrays.hashCode(refs);
}
@Override
public boolean equals(Object o) {
if (o instanceof RefTuple) {
RefTuple t = (RefTuple) o;
return Arrays.equals(refs, t.refs);
}
return false;
}
}
RefTuple getInitialCandidate() {
int [] index = new int[tuples.length];
int sum = 0;
for (int j = 0; j < index.length; ++j)
sum += tuples[j].elts[index[j] = tuples[j].elts.length - 1];
return new RefTuple(index, sum);
}
final void reset() {
candidates.clear();
candidates.add(getInitialCandidate());
}
int [] getNext() {
if (candidates.isEmpty()) return null;
RefTuple next = candidates.poll();
for (int i = 0; i < tuples.length; ++i) {
RefTuple successor = next.getSuccessor(i);
if (successor != null) candidates.add(successor);
}
return next.getTuple();
}
static class NoDupHeap {
final PriorityQueue<RefTuple> heap =
new PriorityQueue<>((a, b) -> Integer.compare(b.sum, a.sum));
final Set<RefTuple> set = new HashSet<>();
void add(RefTuple t) {
if (set.contains(t)) return;
heap.add(t);
set.add(t);
}
RefTuple poll() {
RefTuple t = heap.poll();
set.remove(t);
return t;
}
boolean isEmpty() {
return heap.isEmpty();
}
void clear() {
heap.clear();
set.clear();
}
}
public static void main(String [] args) {
SortedTuple [] tuples = {
new SortedTuple(9, 8, 0),
new SortedTuple(4, 2),
new SortedTuple(5, 1),
};
SortedProduct product = new SortedProduct(tuples);
for (;;) {
int[] next = product.getNext();
if (next == null) break;
System.out.println(Arrays.toString(next));
}
}
}