以递减和顺序生成笛卡尔积

Question

给定 n 个按降序排列的整数排序列表 A1、A2、...、An，是否有一种算法可以按元组总和的降序有效地生成其笛卡尔积的所有元素？

例如，n=3

A1 = [9, 8, 0]
A2 = [4, 2]
A3 = [5, 1]

预期输出将是 A1xA2xA3 的笛卡尔积，顺序如下：
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

Answer 1

这里有一些 Python。（不是很有效 - 只生成整个列表然后对其进行排序可能会更好。）

#! /usr/bin/env python
import heapq

def decreasing_tuple_order(*lists):
    # Each priority queue element will be:
    #    (-sum, indices, incrementing_index, sliced)
    # The top element will have the largest sum.
    if 0 < min((len(l) for l in lists)):
        indices = [0 for l in lists]
        sliced = [lists[i][indices[i]] for i in range(len(indices))]
        queue = [(-sum(sliced), indices, 0, sliced)]
        while 0 < len(queue):
            #print(queue)
            (_, indices, indexable, sliced) = heapq.heappop(queue)
            yield sliced

            # Can we increment this index?
            if indices[indexable] + 1 < len(lists[indexable]):
                new_indices = indices[:]
                new_indices[indexable] = indices[indexable] + 1
                sliced = [lists[i][new_indices[i]] for i in range(len(indices))]
                heapq.heappush(queue, (-sum(sliced), new_indices, indexable, sliced))

            # Start indexing the next index?
            while indexable + 1 < len(lists):
                indexable = indexable + 1
                if 1 < len(lists[indexable]):
                    # Start incrementing here.
                    indices[indexable] = 1
                    sliced = [lists[i][indices[i]] for i in range(len(indices))]
                    heapq.heappush(queue, (-sum(sliced), indices, indexable, sliced))



a1 = [9, 8, 0]
a2 = [4, 2]
a3 = [5, 1]

for x in decreasing_tuple_order(a1, a2, a3):
    print((x,sum(x)))

Answer 2

如果问题实例有N个集合要交叉，那么你可以把乘积中的元组想象成一个N-dimensional"rectangular"网格，其中每个元组对应一个网格元素。您将从发出位于网格一角的 max-sum 元组 [9,4,5] 开始。

您将跟踪 "candidate set" 个 un-emitted 元组，这些元组在每个维度上至少比一个已经发出的元组小一个。如果有帮助，您可以将 already-emitted 元组可视化为网格中的 "solid"。候选集是接触实体表面的所有元组。

您将重复选择下一个要从候选集中发出的元组，然后用新发出的元组的邻居更新集合。当集合为空时，您就完成了。

发出[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 是候选集。

布景能放多大？有趣的问题。我会让你考虑一下。对于您示例中的 3 个输入集，它是

|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) space。 heap/priority 队列大小仅为 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();
  }

  /** 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));
    }
  }
}

以递减和顺序生成笛卡尔积

Generate cartesian product in decreasing sum order

sorting

algorithm

generator

combinatorics

cartesian-product