以递减的顺序生成笛卡尔积 [英] Generate cartesian product in decreasing sum order
问题描述
给出n个按降序排列的列表A1，A2，...，An，是否有一种算法可以按元组和降序有效地生成其笛卡尔积的所有元素？
Given n sorted lists A1, A2, ..., An of integers in decreasing order, is there an algorithm to efficiently generate all elements of their cartesian product in decreasing tuple sum order ?
例如，n = 3
A1 = [9，8，0] < br>
A2 = [4，2]
A3 = [5，1]
预期输出将是A1xA2xA3的笛卡尔积，其顺序为：
组合总和
9，4，5 18
8，4，5 17
9，2，5 16
8，2， 5 15
9，4，1 14
8， 4，1 13
9，2，1 12
8，2，1 11
0，4，5 9
0，2，5 7
0，4，1 5
0，2，1 3
The expected output would be the cartesian product of A1xA2xA3 in the following order:
combination sum
9, 4, 5 18
8, 4, 5 17
9, 2, 5 16
8, 2, 5 15
9, 4, 1 14
8, 4, 1 13
9, 2, 1 12
8, 2, 1 11
0, 4, 5 9
0, 2, 5 7
0, 4, 1 5
0, 2, 1 3
推荐答案
如果问题实例有N个交叉集，则可以将产品中的元组视为N维矩形网格，其中每个元组都对应一个网格元素。首先，发出最大和元组[9,4,5]，它位于网格的一个角。
If the problem instance has N sets to cross, then you can think of the tuples in the product as an N-dimensional "rectangular" grid, where each tuple corresponds to a grid element. You'll start by emitting the max-sum tuple [9,4,5], which is at one corner of the grid.
您将跟踪未发出的元组的候选集合，这些元组在每个维度上相对于至少一个已经发出的元组要小一个。如果有帮助，您可以将已经发出的元组可视化为网格中的实体。候选集是所有接触实体表面的元组。
You'll keep track of a "candidate set" of un-emitted tuples that are one smaller on each dimension with respect to at least one already emitted. If it helps, you can visualize the already-emitted tuples as a "solid" in the grid. The candidate set is all tuples that touch the solid's surface.
您将反复从候选集中选择要发射的下一个元组，然后使用的相邻集更新该元组。新发出的元组。
You'll repeatedly choose the next tuple to emit from the candidate set, then update the set with the neighbors of the newly emitted tuple. When the set is empty, you're done.
发出[9,4,5]后，候选集合为
After emitting [9,4,5], the candidate set is
[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]。与此相邻的是
Next emit the one of these with the largest sum. That's [8,4,5]. Adjacent to that are
[0,4,5], [8,2,5], [8,4,1]
将这些添加到候选集中，所以我们现在有了
Add those to the candidate set, so we now have
[9,2,5], [9,4,1], [0,4,5], [8,2,5], [8,4,1]
再次选择最高金额。就是[9,2,5]。
Again pick the highest sum. That's [9,2,5]. Adjacent are
[8,2,5], [9,2,1].
所以新的候选集是
[9,4,1], [0,4,5], [8,2,5], [8,4,1], [9,2,1]
注意[8,2,5]再次出现。请勿重复。
Note [8,2,5] came up again. Don't duplicate it.
这次最高金额为[8,2,5]。
This time the highest sum is [8,2,5]. Adjacent are
[0,2,5], [8,2,1]
这时您应该有了主意。
使用最大堆作为候选集。然后，找到具有最大总和的元组需要O（log | C |），其中C是候选集。
Use a max heap for the candidate set. Then finding the tuple with max sum requires O(log |C|) where C is the candidate set.
该集合能得到多大？有趣的问题。我会让你考虑一下。对于您的示例中的3个输入集，它是
How big can the set get? Interesting question. I'll let you think about it. For 3 input sets as in your example, it's
|C| = O(|A1||A2| + |A2||A3| + |A1||A3|)
因此，发出每个元组的成本为
So the cost of emitting each tuple is
O(log(|A1||A2| + |A2||A3| + |A1||A3|))
如果集合的大小最大为N，则这是O（log 3 N ^ 2）= O（log 3 + 2 log N）= O（log N）。
If the sets have size at most N, then this is O(log 3 N^2) = O(log 3 + 2 log N) = O(log N).
有| A1 || A2 | | A3 |要发出的元组，即O（N ^ 3）。
There are |A1||A2||A3| tuples to emit, which is O(N^3).
生成所有元组和排序的简单算法是O（log N ^ 3）= O（3 log N）= O（log N）。大约只慢了50％，这在渐近上是一样的。更复杂的算法的主要优点是节省了O（N）空间。堆/优先级队列的大小仅为O（N ^ 2）。
The simpler algorithm of generating all tuples and sorting is O(log N^3) = O(3 log N) = O(log N). It's very roughly only 50% slower, which is asymptotically the same. The main advantage of the more complex algorithm is that it saves O(N) space. The heap/priority queue size is only O(N^2).
这是一种快速的Java实现，意在使代码的大小保持较小。
Here is a quick Java implementation meant to keep the code size small.
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();
}
/** A max heap of indirect ref tuples that ignores addition of duplicates. */
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));
}
}
}
这篇关于以递减的顺序生成笛卡尔积的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
