按总和顺序生成子集的算法
Algorithm to generate a subset in order of its sum
我对一种算法很感兴趣，它可以按照总和的递增顺序生成或排序某些集合的子集。我已经回顾了一些类似的问题，但他们只谈论按线性顺序生成子集，比如 Algorithm to generate k element subsets in order of their sum and Algorithm wanted: Enumerate all subsets of a set in order of increasing sums
有没有更快的聪明方法？
我之前试过从所有子集生成一棵区间树，然后沿着它搜索，其中根节点是集合中最右边的整数，左边节点将最左边的整数向下移动一个，右边节点追加下一个最大整数。所以 {1,3,5,8} 是
8
5 5,8
3 3,5 3,8 3,5,8
1 1,3 1,5 1,3,5 1,8 1,3,8 1,5,8 1,3,5,8
在任何节点，左区间将被子集中的最小值替换为左节点子集中集合中的最小值，其中包括该左节点子集中最大元素左侧的所有元素。正确的间隔是相同的逻辑但镜像。如果目标和不在其中一个区间内，则不要搜索子树。如果它在两个子树中，则搜索两者。这几乎可以在不需要生成任何子树的情况下检索范围的地方完成，因此它不需要实际构建树，只需要在每个步骤中构建每个节点。这种方法似乎在一般情况下有效，但在最坏的情况下呈指数增长。
是否有任何类似的方法？
如果你的集合只能包含正个整数，那么直接的方法就是使用优先级队列，如下：
- 将空集 {} 添加到队列
- 从队列中取出总和最小的集合并输出
- 枚举所有可以通过向您删除的集合添加一个元素来创建的集合，如果之前没有添加过，则将它们添加到队列中。
- 如果队列还不是空的，回到2。
这基本上是在子集图上使用Dijkstra的算法，其中每个集合是一个顶点，边都是增量方式来生成增加总和的新集合。
如果你的集合中可以有负整数，你仍然可以使用上面的变体。只要确保您从尽可能小的子集开始——包含所有负数的子集，然后在第 3 步中您将通过所有增量方法来获得更大的总和，这意味着要么添加一个正数，要么删除一个负数.
根据您的间隔树示例和链接的答案，听起来好像您想生成 k-th 最大的子集而不生成先前的子集并且这样做的时间少于 O(k)，如果我理解正确，正如你提到的想要比以前的线性方法更快的东西。对此的解决方案将证明 P=NP，因为您可以通过在次指数时间内生成每个 k-th 最大子集来对所有子集进行二进制搜索。
我几年前就解决了这个问题，试图生成 k-th 最大的子集，然后按总和的顺序对子集进行二分搜索，所以也许我可以尝试解释一下这种方法的一个基本问题，即某些子集组本质上是不可比较的，并且在最坏情况下必须比较的不可比较子集的数量随着输入大小的增长呈指数增长。
子集和问题的搜索space是输入集的幂集。更具体地说，搜索space是输入集的幂集的每个子集的总和。例如，对于输入集 {1, 2, 3}，搜索 space 是 {{1}, {2}, {1, 2}, {3}, {1, 3}, {2, 3}, {1, 2, 3}}，或者简单地说，{1, 2, 3, 3, 4, 5, 6}。无论输入集如何，最小子集和总是第一个元素的单例，下一个最小子集和总是第二个元素的单例，下一个最小子集和总是前两个元素的子集输入集的元素。类似地，最大子集总和将始终是整个输入集的总和，而下一个最大子集总和将始终是输入集第一个元素的总和，下一个最大子集总和将始终是输入集的总和输入集没有第二个元素，下一个最大的子集总和将始终是输入集没有第一和第二个元素的总和。
但是回到之前的输入集{1, 2, 3}，如果{1, 2, 2}这样大小相同的输入集呢？搜索 space 变为 {{1}, {2}, {1, 2}, {2}, {1, 2}, {2, 2}, {1, 2, 2}}，或 {1, 2, 3, 2, 4, 5, 6}。如果您试图按照集合 {a, b, c} 的总和的顺序对幂集进行排序，那么您必须比较 {a, b} 和 {c}，因为存在 {a, b} 的输入集] 更大，其他 {c} 更大。这两个子集是不可比的。如果你能保证一个总是大于另一个，那么你可以适当地设计一个搜索算法，但你没有，所以你至少要检查这两个元素。
对于大小为4的输入集{a, b, c, d}，还有两个不可比较的子集：{a, d}和{b, c}；比较 {1, 2, 4, 8} 和 {1, 3, 3, 3} 这些子集的总和。事实上，还有其他几组对偶不可比子集，例如 {a, b, c} 和 {b, d}。如果我们绘制一个 Hasse diagram ，我们得到（对 ASCII 艺术表示歉意）：
a,b,c,d
|
b,c,d
|
a,c,d--------|
| |
a,b,d---|---c,d
| |
a,b,c b,d
| |
b,c a,d
| |
a,c----d
-------| |
a,b c-----|
| |
|------b
|
a
换句话说，你可以设计一个算法在 {{a}, {b}, {a, b}, {a, c}, {b, c}, {a, b, c}, {a, b, d}, {a, c, d}, {b, c, d}, {a, b, c, d}} 的链上进行二分搜索，在 {{c}, {d}, {a, d}, {b, d}, {c, d}} 的链上进行另一个二分搜索，或者在另一个配置上进行两次二分搜索这些链，但最终您将不得不执行至少两次二进制搜索。您始终可以保证 a+b <= a+c 或 b+d <= a+c+d（如 b+d <= c+d <= a+c+d），但您不能保证，例如b+c <= a+d。在最坏的情况下，您将不得不进行这些比较。
更进一步，对于大小为 5 {a, b, c, d, e} 的输入集，{a, d}、{b, c} 和 {e} 的子集是无可比拟的。例如：
{1, 2, 4, 8, 16} 有 {b, c} <= {a, d} <= {e}
{1, 2, 2, 2, 5} 有 {a, d} <= {b, c} <= {e}
{5, 5, 5, 6, 6} 有 {e} <= {b, c} <= {a, d}
{1, 5, 5, 6, 6} 有 {e} <= {a, d} <= {b, c}
{1, 4, 4, 4, 6} 有 {a, d} <= {e} <= {b, c}
{1, 2, 2, 6, 6} 有 {b, c} <= {e} <= {a, d}
再拼一张ASCII Hasse图：
a,b,c,d,e
|
b,c,d,e
|
a,c,d,e-------------------------|
| |
a,b,d,e-------------------|---c,d,e
| |
a,b,c,e------------|----b,d,e
| | |
a,b,c,d a,d,e b,c,e
| | |
b,c,d d,e a,c,e
| | |
a,c,d--------|---c,e-----|---a,b,e
| | | |
a,b,d---|---c,d b,e-----------|
| | |
a,b,c b,d --a,e
| | / |
b,c -a,d---/ e
| / | |
a,c d---------|
-------| |
a,b c-----|
| |
|------b
|
a
在最坏的情况下，您将不得不进行三次二进制搜索，因为无法比较的集合的最大分组是三个。
这里有个规律。子集的总和形成一个偏序。对于大小为 3 的集合，此偏序的宽度（也称为 maximum antichain）为 2。对于大小 4，它也为 2。对于大小 5，宽度为 3。对于大小为 6 的集合，宽度为 5。7 号的宽度为 8。8 号的宽度为 14。9 号的宽度为 23。10 号的宽度为 40。11 号的宽度为 70。
其实这个整数序列是已知的。它在 Online Encyclopedia of Integer Sequences A025591 as the number of solutions to +- 1 +- 2 +- 3 +- ... +- n = 0 or 1. This integer sequence has also been discussed in Robert A. Proctor's 1982 paper "Solution of Two Difficult Combinatorial Problems with Linear Algebra," in which the problem of finding a set of n distinct positive real numbers with as large a collection as possible of subsets with the same sum is shown to be the first n positive integers: {1,2,...,n}. Proctor gave the first elementary proof of this result requiring no more than a background in linear algebra to follow. The maximal numbers of subsets of {1,2,...,n} having the same sum for n=1, 2, ... are 1, 1, 2, 2, 3, 5, 8, 14, 23, etc, or OEIS A025591 中，与上面讨论的整数序列相同。事实上，这个序列是按照上面讨论的相同方式在论文中构建的。
回到识别可比较子集的问题，这个排序可以被概括为通过三个案例来解释输入集的所有子集。给定任意输入集 S:
的两个子集 A 和 B
- 考虑
A 的 cardinality 大于 B 的基数的情况。那么不能保证B的总和大于A的总和。
- 考虑
A 的基数等于 B 的基数的情况。对于 i=0 to cardinality(A) 中的每个元素 A[i] 和 B[i]，如果从中提取 A[i] 的 S 中的索引大于 S 中的索引B[i]是从哪里得出的，那么不能保证B的和大于A的和。否则可以保证B之和大于A. 之和
- 考虑
A 的基数小于 B 的基数的情况。删除集合 B 中的最少元素，使得 A 和 B 的基数相等。现在可以应用第二种情况。
为了帮助说明这一点，我拼凑了一些代码，这些代码根据输入集的幂集构建有向无环图，其中每条边将子集总和较小的节点连接到子集总和较大的所有节点。这个过程形成了一个传递闭包，因为所有较小的节点都将连接到所有较大的节点。然后将传递归约应用于该图，并返回最大反链的大小以及构成该反链的子集，格式为 [index, value]，通过沿着 Hasse 图向上走并存储每一层的宽度.最终图的最大反链等于整数序列 A025591.
（这段代码是为了证明我想表达的意思而快速组合在一起的。对于任何糟糕的编码决定，我提前表示歉意！）
</p>
<pre><code>import com.google.common.graph.*;
import java.util.*;
public class AntichainDecomposition {
MutableGraph<Subset> graph;
public static void main(String[] args) {
// Input set. Modify this as needed.
int[] set = new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9};
ArrayList<Subset> input = buildSubsets(set);
AntichainDecomposition antichain = new AntichainDecomposition(input);
}
public AntichainDecomposition(ArrayList<Subset> input) {
graph = GraphBuilder.directed().build();
for (int i = 0; i < input.size(); ++i) {
graph.addNode(input.get(i));
}
for (int i = 0; i < input.size(); ++i) {
for (int j = 0; j < input.size(); ++j) {
if (i != j && isTargetGreater(input.get(i), input.get(j))) {
graph.putEdge(input.get(i), input.get(j));
}
}
}
graphReduction();
int width = getWidth(input.get(input.size() / 2));
System.err.println(width);
}
private int getWidth(Subset first) {
HashMap<Integer, HashSet<Subset>> levelMap = new HashMap<Integer, HashSet<Subset>>();
HashMap<Subset, Integer> subsetToLevel = new HashMap<Subset, Integer>();
int level = 1;
// Mark all the vertices as not visited
HashMap<Subset, Boolean> visited = new HashMap<Subset, Boolean>();
Iterator iter = graph.nodes().iterator();
while (iter.hasNext()) {
Subset node = (Subset)iter.next();
visited.put(node, false);
}
// Create a queue for breadth first search
LinkedList<Subset> queue = new LinkedList<Subset>();
// Mark the current node as visited and enqueue it
levelMap.put(level, new HashSet<Subset>());
levelMap.get(level).add(first);
subsetToLevel.put(first, level);
visited.put(first, true);
queue.add(first);
while (queue.size() != 0) {
// Dequeue a vertex from the queue and store it in the appropriate level
Subset s = queue.poll();
level = subsetToLevel.get(s);
// Get all adjacent vertices of the dequeued vertex s
// If a successor has not been visited, then mark it
// visited and enqueue it
iter = graph.successors(s).iterator();
while (iter.hasNext()) {
Subset n = (Subset)iter.next();
if (!visited.get(n)) {
if (!levelMap.containsKey(level + 1)) {
levelMap.put(level + 1, new HashSet<Subset>());
}
levelMap.get(level + 1).add(n);
subsetToLevel.put(n, level + 1);
visited.put(n, true);
queue.add(n);
}
}
}
int width = Integer.MIN_VALUE;
iter = levelMap.values().iterator();
Iterator subsetIter = null;
while (iter.hasNext()) {
HashSet<Subset> levelSet = (HashSet<Subset>)iter.next();
if (levelSet.size() > width) {
width = levelSet.size();
subsetIter = levelSet.iterator();
}
}
if (subsetIter != null) {
while (subsetIter.hasNext()) {
System.out.println((Subset)subsetIter.next());
}
}
return width;
}
private void graphReduction() {
// Reflexive reduction
Iterator iter1 = graph.nodes().iterator();
while (iter1.hasNext()) {
Subset i = (Subset)iter1.next();
graph.removeEdge(i, i);
}
// Transitive reduction
iter1 = graph.nodes().iterator();
while (iter1.hasNext()) {
Subset j = (Subset)iter1.next();
Iterator iter2 = graph.nodes().iterator();
while (iter2.hasNext()) {
Subset i = (Subset)iter2.next();
if (graph.removeEdge(i, j)) {
graph.putEdge(i, j);
Iterator iter3 = graph.nodes().iterator();
while (iter3.hasNext()) {
Subset k = (Subset)iter3.next();
if (graph.removeEdge(j, k)) {
graph.putEdge(j, k);
graph.removeEdge(i, k);
}
}
}
}
}
}
private Stack<Subset> topologicalSort() {
Stack<Subset> stack = new Stack<Subset>();
int vertices = graph.nodes().size();
// Mark all the vertices as not visited
HashMap<Subset, Boolean> visited = new HashMap<Subset, Boolean>();
Iterator iter = graph.nodes().iterator();
while (iter.hasNext()) {
Subset node = (Subset)iter.next();
visited.put(node, false);
}
// Call the recursive helper function to store topological sort
// starting from all vertices one by one
iter = graph.nodes().iterator();
while (iter.hasNext()) {
Subset node = (Subset)iter.next();
if (!visited.containsKey(node) || !visited.get(node)) {
topologicalSortHelper(node, visited, stack);
}
}
return stack;
}
private void topologicalSortHelper(Subset v, HashMap<Subset, Boolean> visited, Stack<Subset> stack) {
visited.put(v, true);
// Recurse for all the vertices adjacent to this vertex
Iterator iter = graph.successors(v).iterator();
while (iter.hasNext()) {
Subset node = (Subset)iter.next();
if (!visited.containsKey(node) || !visited.get(node)) {
topologicalSortHelper(node, visited, stack);
}
}
// Push current vertex to stack which stores topological sort
stack.push(v);
}
private boolean isTargetGreater(Subset source, Subset target) {
// An edge between two nodes exists if each index in the target subset is greater than or
// equal to its respective index in the source subset. If the target subset size is greater
// than the source subset size, then an edge between the two subsets exists if and only if
// the target subset has indices that are greater than or equal to corresponding indices of
// the source subset, ignoring the additional indices of the target subset.
if (source.size() > target.size()) {
return false;
}
SubsetEntry[] newSubset = new SubsetEntry[target.size()];
System.arraycopy(target.getSubset(), 0, newSubset, 0, newSubset.length);
Subset newTarget = new Subset(Arrays.asList(newSubset).subList(target.size() -
source.size(), target.size()).
toArray(new SubsetEntry[source.size()]));
for (int i = 0; i < source.size(); ++i) {
if (source.getEntry(i).getIndex() > newTarget.getEntry(i).getIndex()) {
return false;
}
}
return true;
}
private static ArrayList<Subset> buildSubsets(int[] set) {
ArrayList<Subset> power = new ArrayList<Subset>();
int elements = set.length;
int powerElements = (int) Math.pow(2, elements);
for (int i = 0; i < powerElements; ++i) {
// Convert the binary number to a string containing n digits
String binary = intToBinary(i, elements);
// Create a new set
ArrayList<SubsetEntry> innerSet = new ArrayList<SubsetEntry>();
// Convert each digit in the current binary number to the corresponding element
// in the given set
for (int j = 0; j < binary.length(); ++j) {
if (binary.charAt(j) == '1') {
innerSet.add(new SubsetEntry(j, set[j]));
}
}
// Add the new set to the power set
if (!innerSet.isEmpty()) {
power.add(new Subset(innerSet.toArray(new SubsetEntry[innerSet.size()])));
}
}
return power;
}
private static String intToBinary(int binary, int digits) {
String temp = Integer.toBinaryString(binary);
int foundDigits = temp.length();
String returner = temp;
for (int i = foundDigits; i < digits; ++i) {
returner = "0" + returner;
}
return returner;
}
}
class SubsetEntry {
private int index;
private int value;
public SubsetEntry(int i, int v) {
index = i;
value = v;
}
public int getIndex() {
return index;
}
public int getValue() {
return value;
}
public String toString() {
return "[" + index + ", " + value + "]";
}
}
class Subset {
private SubsetEntry[] entries;
public Subset(SubsetEntry[] e) {
entries = new SubsetEntry[e.length];
System.arraycopy(e, 0, entries, 0, entries.length);
}
public void setSubset(SubsetEntry[] subset) {
entries = new SubsetEntry[subset.length];
System.arraycopy(subset, 0, entries, 0, subset.length);
}
public SubsetEntry[] getSubset() {
return entries;
}
public SubsetEntry getEntry(int index) {
return entries[index];
}
public int size() {
return entries.length;
}
public String toString() {
String s = "{";
for (int i = 0; i < entries.length; ++i) {
s += entries[i].toString();
}
s += "}";
return s;
}
}
根据 Dilworth 定理，对于任何偏序集，最大反链的基数等于可用于覆盖偏序集的最小链数。对于任何输入集，在最坏的情况下，这会产生一个带有 A025591 链的偏序。此外，搜索偏序的最坏情况时间是 O(w*log(n))，其中 w 是图的宽度（等于最大反链的基数）。这可以通过以下事实来证明：反链的特征是无序列表，其中没有两个元素是可比较的，并且搜索无序列表的最坏情况时间是 O(n)。此外，链的特征是有序列表，其中每个元素都可与列表中的所有其他元素进行比较，并且搜索有序列表的最坏情况时间是O(log n)。因此，对于长度为 w 的反链中的每个元素，在最坏情况下必须在相应链中进行 log(n) 比较，导致最坏情况下的搜索时间为 O(w*log(n))任何偏序。
这个偏序搜索时间为任意输入集的每个子集的总和的排序提供了最坏情况的特征。这是因为，对于任何输入集，都需要观察反链中的每个总和才能推导出最佳搜索树。回想一下，以您的原始集合 {1, 3, 5, 8} 为例，索引 1 和 2 处的子集 {3, 5} 的总和小于索引 0 和 3 处的子集 {1, 8} 的总和。但是，对于集合 {1, 2, 3, 3}，索引 1 和 2 的子集 {2, 3} 的总和大于索引 0 和 3 的子集 {1, 3} 的总和。索引集合 {1, 2}和{0, 3}是后来无法比较的。随着集合的扩展，这种不可比性的顺序以 A025591 中定义的指数速率增长。
我将通过说我假设输入集中使用的所有数字都是正数并且输入集已排序来结束这个。事实上，如果您使用的是未排序的列表或正数和负数的混合，则没有两个元素可以保证具有可比性。
如果这个答案冗长且杂乱无章，我深表歉意，但我希望这有助于让您对您要解决的问题有一些了解。
我对一种算法很感兴趣，它可以按照总和的递增顺序生成或排序某些集合的子集。我已经回顾了一些类似的问题，但他们只谈论按线性顺序生成子集，比如 Algorithm to generate k element subsets in order of their sum and Algorithm wanted: Enumerate all subsets of a set in order of increasing sums
有没有更快的聪明方法？
我之前试过从所有子集生成一棵区间树，然后沿着它搜索，其中根节点是集合中最右边的整数，左边节点将最左边的整数向下移动一个，右边节点追加下一个最大整数。所以 {1,3,5,8} 是
8
5 5,8
3 3,5 3,8 3,5,8
1 1,3 1,5 1,3,5 1,8 1,3,8 1,5,8 1,3,5,8
在任何节点，左区间将被子集中的最小值替换为左节点子集中集合中的最小值，其中包括该左节点子集中最大元素左侧的所有元素。正确的间隔是相同的逻辑但镜像。如果目标和不在其中一个区间内，则不要搜索子树。如果它在两个子树中，则搜索两者。这几乎可以在不需要生成任何子树的情况下检索范围的地方完成，因此它不需要实际构建树，只需要在每个步骤中构建每个节点。这种方法似乎在一般情况下有效，但在最坏的情况下呈指数增长。
是否有任何类似的方法？
如果你的集合只能包含正个整数，那么直接的方法就是使用优先级队列，如下：
- 将空集 {} 添加到队列
- 从队列中取出总和最小的集合并输出
- 枚举所有可以通过向您删除的集合添加一个元素来创建的集合，如果之前没有添加过，则将它们添加到队列中。
- 如果队列还不是空的，回到2。
这基本上是在子集图上使用Dijkstra的算法，其中每个集合是一个顶点，边都是增量方式来生成增加总和的新集合。
如果你的集合中可以有负整数，你仍然可以使用上面的变体。只要确保您从尽可能小的子集开始——包含所有负数的子集，然后在第 3 步中您将通过所有增量方法来获得更大的总和，这意味着要么添加一个正数，要么删除一个负数.
根据您的间隔树示例和链接的答案，听起来好像您想生成 k-th 最大的子集而不生成先前的子集并且这样做的时间少于 O(k)，如果我理解正确，正如你提到的想要比以前的线性方法更快的东西。对此的解决方案将证明 P=NP，因为您可以通过在次指数时间内生成每个 k-th 最大子集来对所有子集进行二进制搜索。
我几年前就解决了这个问题，试图生成 k-th 最大的子集，然后按总和的顺序对子集进行二分搜索，所以也许我可以尝试解释一下这种方法的一个基本问题，即某些子集组本质上是不可比较的，并且在最坏情况下必须比较的不可比较子集的数量随着输入大小的增长呈指数增长。
子集和问题的搜索space是输入集的幂集。更具体地说，搜索space是输入集的幂集的每个子集的总和。例如，对于输入集 {1, 2, 3}，搜索 space 是 {{1}, {2}, {1, 2}, {3}, {1, 3}, {2, 3}, {1, 2, 3}}，或者简单地说，{1, 2, 3, 3, 4, 5, 6}。无论输入集如何，最小子集和总是第一个元素的单例，下一个最小子集和总是第二个元素的单例，下一个最小子集和总是前两个元素的子集输入集的元素。类似地，最大子集总和将始终是整个输入集的总和，而下一个最大子集总和将始终是输入集第一个元素的总和，下一个最大子集总和将始终是输入集的总和输入集没有第二个元素，下一个最大的子集总和将始终是输入集没有第一和第二个元素的总和。
但是回到之前的输入集{1, 2, 3}，如果{1, 2, 2}这样大小相同的输入集呢？搜索 space 变为 {{1}, {2}, {1, 2}, {2}, {1, 2}, {2, 2}, {1, 2, 2}}，或 {1, 2, 3, 2, 4, 5, 6}。如果您试图按照集合 {a, b, c} 的总和的顺序对幂集进行排序，那么您必须比较 {a, b} 和 {c}，因为存在 {a, b} 的输入集] 更大，其他 {c} 更大。这两个子集是不可比的。如果你能保证一个总是大于另一个，那么你可以适当地设计一个搜索算法，但你没有，所以你至少要检查这两个元素。
对于大小为4的输入集{a, b, c, d}，还有两个不可比较的子集：{a, d}和{b, c}；比较 {1, 2, 4, 8} 和 {1, 3, 3, 3} 这些子集的总和。事实上，还有其他几组对偶不可比子集，例如 {a, b, c} 和 {b, d}。如果我们绘制一个 Hasse diagram ，我们得到（对 ASCII 艺术表示歉意）：
a,b,c,d
|
b,c,d
|
a,c,d--------|
| |
a,b,d---|---c,d
| |
a,b,c b,d
| |
b,c a,d
| |
a,c----d
-------| |
a,b c-----|
| |
|------b
|
a
换句话说，你可以设计一个算法在 {{a}, {b}, {a, b}, {a, c}, {b, c}, {a, b, c}, {a, b, d}, {a, c, d}, {b, c, d}, {a, b, c, d}} 的链上进行二分搜索，在 {{c}, {d}, {a, d}, {b, d}, {c, d}} 的链上进行另一个二分搜索，或者在另一个配置上进行两次二分搜索这些链，但最终您将不得不执行至少两次二进制搜索。您始终可以保证 a+b <= a+c 或 b+d <= a+c+d（如 b+d <= c+d <= a+c+d），但您不能保证，例如b+c <= a+d。在最坏的情况下，您将不得不进行这些比较。
更进一步，对于大小为 5 {a, b, c, d, e} 的输入集，{a, d}、{b, c} 和 {e} 的子集是无可比拟的。例如：
{1, 2, 4, 8, 16} 有 {b, c} <= {a, d} <= {e}
{1, 2, 2, 2, 5} 有 {a, d} <= {b, c} <= {e}
{5, 5, 5, 6, 6} 有 {e} <= {b, c} <= {a, d}
{1, 5, 5, 6, 6} 有 {e} <= {a, d} <= {b, c}
{1, 4, 4, 4, 6} 有 {a, d} <= {e} <= {b, c}
{1, 2, 2, 6, 6} 有 {b, c} <= {e} <= {a, d}
再拼一张ASCII Hasse图：
a,b,c,d,e
|
b,c,d,e
|
a,c,d,e-------------------------|
| |
a,b,d,e-------------------|---c,d,e
| |
a,b,c,e------------|----b,d,e
| | |
a,b,c,d a,d,e b,c,e
| | |
b,c,d d,e a,c,e
| | |
a,c,d--------|---c,e-----|---a,b,e
| | | |
a,b,d---|---c,d b,e-----------|
| | |
a,b,c b,d --a,e
| | / |
b,c -a,d---/ e
| / | |
a,c d---------|
-------| |
a,b c-----|
| |
|------b
|
a
在最坏的情况下，您将不得不进行三次二进制搜索，因为无法比较的集合的最大分组是三个。
这里有个规律。子集的总和形成一个偏序。对于大小为 3 的集合，此偏序的宽度（也称为 maximum antichain）为 2。对于大小 4，它也为 2。对于大小 5，宽度为 3。对于大小为 6 的集合，宽度为 5。7 号的宽度为 8。8 号的宽度为 14。9 号的宽度为 23。10 号的宽度为 40。11 号的宽度为 70。
其实这个整数序列是已知的。它在 Online Encyclopedia of Integer Sequences A025591 as the number of solutions to +- 1 +- 2 +- 3 +- ... +- n = 0 or 1. This integer sequence has also been discussed in Robert A. Proctor's 1982 paper "Solution of Two Difficult Combinatorial Problems with Linear Algebra," in which the problem of finding a set of n distinct positive real numbers with as large a collection as possible of subsets with the same sum is shown to be the first n positive integers: {1,2,...,n}. Proctor gave the first elementary proof of this result requiring no more than a background in linear algebra to follow. The maximal numbers of subsets of {1,2,...,n} having the same sum for n=1, 2, ... are 1, 1, 2, 2, 3, 5, 8, 14, 23, etc, or OEIS A025591 中，与上面讨论的整数序列相同。事实上，这个序列是按照上面讨论的相同方式在论文中构建的。
回到识别可比较子集的问题，这个排序可以被概括为通过三个案例来解释输入集的所有子集。给定任意输入集 S:
A 和 B
- 考虑
A的 cardinality 大于B的基数的情况。那么不能保证B的总和大于A的总和。 - 考虑
A的基数等于B的基数的情况。对于i=0 to cardinality(A)中的每个元素A[i]和B[i]，如果从中提取A[i]的S中的索引大于S中的索引B[i]是从哪里得出的，那么不能保证B的和大于A的和。否则可以保证B之和大于A. 之和
- 考虑
A的基数小于B的基数的情况。删除集合B中的最少元素，使得A和B的基数相等。现在可以应用第二种情况。
为了帮助说明这一点，我拼凑了一些代码，这些代码根据输入集的幂集构建有向无环图，其中每条边将子集总和较小的节点连接到子集总和较大的所有节点。这个过程形成了一个传递闭包，因为所有较小的节点都将连接到所有较大的节点。然后将传递归约应用于该图，并返回最大反链的大小以及构成该反链的子集，格式为 [index, value]，通过沿着 Hasse 图向上走并存储每一层的宽度.最终图的最大反链等于整数序列 A025591.
（这段代码是为了证明我想表达的意思而快速组合在一起的。对于任何糟糕的编码决定，我提前表示歉意！）
</p>
<pre><code>import com.google.common.graph.*;
import java.util.*;
public class AntichainDecomposition {
MutableGraph<Subset> graph;
public static void main(String[] args) {
// Input set. Modify this as needed.
int[] set = new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9};
ArrayList<Subset> input = buildSubsets(set);
AntichainDecomposition antichain = new AntichainDecomposition(input);
}
public AntichainDecomposition(ArrayList<Subset> input) {
graph = GraphBuilder.directed().build();
for (int i = 0; i < input.size(); ++i) {
graph.addNode(input.get(i));
}
for (int i = 0; i < input.size(); ++i) {
for (int j = 0; j < input.size(); ++j) {
if (i != j && isTargetGreater(input.get(i), input.get(j))) {
graph.putEdge(input.get(i), input.get(j));
}
}
}
graphReduction();
int width = getWidth(input.get(input.size() / 2));
System.err.println(width);
}
private int getWidth(Subset first) {
HashMap<Integer, HashSet<Subset>> levelMap = new HashMap<Integer, HashSet<Subset>>();
HashMap<Subset, Integer> subsetToLevel = new HashMap<Subset, Integer>();
int level = 1;
// Mark all the vertices as not visited
HashMap<Subset, Boolean> visited = new HashMap<Subset, Boolean>();
Iterator iter = graph.nodes().iterator();
while (iter.hasNext()) {
Subset node = (Subset)iter.next();
visited.put(node, false);
}
// Create a queue for breadth first search
LinkedList<Subset> queue = new LinkedList<Subset>();
// Mark the current node as visited and enqueue it
levelMap.put(level, new HashSet<Subset>());
levelMap.get(level).add(first);
subsetToLevel.put(first, level);
visited.put(first, true);
queue.add(first);
while (queue.size() != 0) {
// Dequeue a vertex from the queue and store it in the appropriate level
Subset s = queue.poll();
level = subsetToLevel.get(s);
// Get all adjacent vertices of the dequeued vertex s
// If a successor has not been visited, then mark it
// visited and enqueue it
iter = graph.successors(s).iterator();
while (iter.hasNext()) {
Subset n = (Subset)iter.next();
if (!visited.get(n)) {
if (!levelMap.containsKey(level + 1)) {
levelMap.put(level + 1, new HashSet<Subset>());
}
levelMap.get(level + 1).add(n);
subsetToLevel.put(n, level + 1);
visited.put(n, true);
queue.add(n);
}
}
}
int width = Integer.MIN_VALUE;
iter = levelMap.values().iterator();
Iterator subsetIter = null;
while (iter.hasNext()) {
HashSet<Subset> levelSet = (HashSet<Subset>)iter.next();
if (levelSet.size() > width) {
width = levelSet.size();
subsetIter = levelSet.iterator();
}
}
if (subsetIter != null) {
while (subsetIter.hasNext()) {
System.out.println((Subset)subsetIter.next());
}
}
return width;
}
private void graphReduction() {
// Reflexive reduction
Iterator iter1 = graph.nodes().iterator();
while (iter1.hasNext()) {
Subset i = (Subset)iter1.next();
graph.removeEdge(i, i);
}
// Transitive reduction
iter1 = graph.nodes().iterator();
while (iter1.hasNext()) {
Subset j = (Subset)iter1.next();
Iterator iter2 = graph.nodes().iterator();
while (iter2.hasNext()) {
Subset i = (Subset)iter2.next();
if (graph.removeEdge(i, j)) {
graph.putEdge(i, j);
Iterator iter3 = graph.nodes().iterator();
while (iter3.hasNext()) {
Subset k = (Subset)iter3.next();
if (graph.removeEdge(j, k)) {
graph.putEdge(j, k);
graph.removeEdge(i, k);
}
}
}
}
}
}
private Stack<Subset> topologicalSort() {
Stack<Subset> stack = new Stack<Subset>();
int vertices = graph.nodes().size();
// Mark all the vertices as not visited
HashMap<Subset, Boolean> visited = new HashMap<Subset, Boolean>();
Iterator iter = graph.nodes().iterator();
while (iter.hasNext()) {
Subset node = (Subset)iter.next();
visited.put(node, false);
}
// Call the recursive helper function to store topological sort
// starting from all vertices one by one
iter = graph.nodes().iterator();
while (iter.hasNext()) {
Subset node = (Subset)iter.next();
if (!visited.containsKey(node) || !visited.get(node)) {
topologicalSortHelper(node, visited, stack);
}
}
return stack;
}
private void topologicalSortHelper(Subset v, HashMap<Subset, Boolean> visited, Stack<Subset> stack) {
visited.put(v, true);
// Recurse for all the vertices adjacent to this vertex
Iterator iter = graph.successors(v).iterator();
while (iter.hasNext()) {
Subset node = (Subset)iter.next();
if (!visited.containsKey(node) || !visited.get(node)) {
topologicalSortHelper(node, visited, stack);
}
}
// Push current vertex to stack which stores topological sort
stack.push(v);
}
private boolean isTargetGreater(Subset source, Subset target) {
// An edge between two nodes exists if each index in the target subset is greater than or
// equal to its respective index in the source subset. If the target subset size is greater
// than the source subset size, then an edge between the two subsets exists if and only if
// the target subset has indices that are greater than or equal to corresponding indices of
// the source subset, ignoring the additional indices of the target subset.
if (source.size() > target.size()) {
return false;
}
SubsetEntry[] newSubset = new SubsetEntry[target.size()];
System.arraycopy(target.getSubset(), 0, newSubset, 0, newSubset.length);
Subset newTarget = new Subset(Arrays.asList(newSubset).subList(target.size() -
source.size(), target.size()).
toArray(new SubsetEntry[source.size()]));
for (int i = 0; i < source.size(); ++i) {
if (source.getEntry(i).getIndex() > newTarget.getEntry(i).getIndex()) {
return false;
}
}
return true;
}
private static ArrayList<Subset> buildSubsets(int[] set) {
ArrayList<Subset> power = new ArrayList<Subset>();
int elements = set.length;
int powerElements = (int) Math.pow(2, elements);
for (int i = 0; i < powerElements; ++i) {
// Convert the binary number to a string containing n digits
String binary = intToBinary(i, elements);
// Create a new set
ArrayList<SubsetEntry> innerSet = new ArrayList<SubsetEntry>();
// Convert each digit in the current binary number to the corresponding element
// in the given set
for (int j = 0; j < binary.length(); ++j) {
if (binary.charAt(j) == '1') {
innerSet.add(new SubsetEntry(j, set[j]));
}
}
// Add the new set to the power set
if (!innerSet.isEmpty()) {
power.add(new Subset(innerSet.toArray(new SubsetEntry[innerSet.size()])));
}
}
return power;
}
private static String intToBinary(int binary, int digits) {
String temp = Integer.toBinaryString(binary);
int foundDigits = temp.length();
String returner = temp;
for (int i = foundDigits; i < digits; ++i) {
returner = "0" + returner;
}
return returner;
}
}
class SubsetEntry {
private int index;
private int value;
public SubsetEntry(int i, int v) {
index = i;
value = v;
}
public int getIndex() {
return index;
}
public int getValue() {
return value;
}
public String toString() {
return "[" + index + ", " + value + "]";
}
}
class Subset {
private SubsetEntry[] entries;
public Subset(SubsetEntry[] e) {
entries = new SubsetEntry[e.length];
System.arraycopy(e, 0, entries, 0, entries.length);
}
public void setSubset(SubsetEntry[] subset) {
entries = new SubsetEntry[subset.length];
System.arraycopy(subset, 0, entries, 0, subset.length);
}
public SubsetEntry[] getSubset() {
return entries;
}
public SubsetEntry getEntry(int index) {
return entries[index];
}
public int size() {
return entries.length;
}
public String toString() {
String s = "{";
for (int i = 0; i < entries.length; ++i) {
s += entries[i].toString();
}
s += "}";
return s;
}
}
根据 Dilworth 定理，对于任何偏序集，最大反链的基数等于可用于覆盖偏序集的最小链数。对于任何输入集，在最坏的情况下，这会产生一个带有 A025591 链的偏序。此外，搜索偏序的最坏情况时间是 O(w*log(n))，其中 w 是图的宽度（等于最大反链的基数）。这可以通过以下事实来证明：反链的特征是无序列表，其中没有两个元素是可比较的，并且搜索无序列表的最坏情况时间是 O(n)。此外，链的特征是有序列表，其中每个元素都可与列表中的所有其他元素进行比较，并且搜索有序列表的最坏情况时间是O(log n)。因此，对于长度为 w 的反链中的每个元素，在最坏情况下必须在相应链中进行 log(n) 比较，导致最坏情况下的搜索时间为 O(w*log(n))任何偏序。
这个偏序搜索时间为任意输入集的每个子集的总和的排序提供了最坏情况的特征。这是因为，对于任何输入集，都需要观察反链中的每个总和才能推导出最佳搜索树。回想一下，以您的原始集合 {1, 3, 5, 8} 为例，索引 1 和 2 处的子集 {3, 5} 的总和小于索引 0 和 3 处的子集 {1, 8} 的总和。但是，对于集合 {1, 2, 3, 3}，索引 1 和 2 的子集 {2, 3} 的总和大于索引 0 和 3 的子集 {1, 3} 的总和。索引集合 {1, 2}和{0, 3}是后来无法比较的。随着集合的扩展，这种不可比性的顺序以 A025591 中定义的指数速率增长。
我将通过说我假设输入集中使用的所有数字都是正数并且输入集已排序来结束这个。事实上，如果您使用的是未排序的列表或正数和负数的混合，则没有两个元素可以保证具有可比性。
如果这个答案冗长且杂乱无章，我深表歉意，但我希望这有助于让您对您要解决的问题有一些了解。