基於鏈接的間隔樹例子和答案，這聽起來好像你要生成的k-th最大的子集，而不會產生之前的子集，並及時這樣做比O(k)少，如果我理解正確的話，你所說的希望比以前的線性方法更快。解決方案將證明P=NP，因爲您可以通過在子指數時間內生成每個k-th最大子集來對所有子集執行二進制搜索。
我在幾年前玩過這個問題，試圖生成k-th最大的子集合，然後按照它們的總和順序對子集進行二分搜索，所以也許我可以嘗試解釋一個基本問題方法，即某些子集合本質上是無法比擬的，並且隨着輸入規模的增長，在最差情況下必須進行比較的無與倫比子集的數量呈指數增長。
子集求和問題的搜索空間是輸入集的冪集。更具體地說，搜索空間是輸入集的功率集的每個子集的總和。例如，對於輸入集{1, 2, 3}，搜索空間是{{1}, {2}, {1, 2}, {3}, {1, 3}, {2, 3}, {1, 2, 3}}，或者簡單地，{1, 2, 3, 3, 4, 5, 6}。無論輸入集合是什麼，最小子集合總是第一個元素的單子，次最小子集合總是第二個元素的單子，並且次最小子集合將總是前兩個子集合的子集合輸入集的元素。類似地，最大子集總和將總是整個輸入集的總和，而下一個最大子集總和將總是第一個元素的輸入集s的總和，下一個最大子集總和將總是輸入集合不包含第二個元素，而下一個最大子集合總是總是第一個元素和第二個元素的輸入集合的總和。
但是回到之前的輸入集合{1, 2, 3}，如何處理相同大小的輸入集，如{1, 2, 2}？搜索空間變爲{{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
換句話說，你可以設計一個算法上做的鏈和另一個二進制搜索二進制搜索鏈的{{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哈斯圖：
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作爲溶液的數量+ - 1 + - 2 + - 3 + - ... + - n = 0或1。這整數序列也已在Robert A. Proctor's 1982 paper "Solution of Two Difficult Combinatorial Problems with Linear Algebra,"討論中找到的一組的問題顯示n個不同的正實數與儘可能大的具有相同總和的子集的集合，顯示爲前n個正整數：{1,2,...,n}。普羅克特給出了這個結果的第一個基本證明，要求不超過線性代數的背景。具有相同總和n=1, 2, ...{1,2,...,n}的子集的最大數目是1，1，2，2，3，5，8，14，23，等等，或OEIS A025591，上面討論的相同的整數序列。事實上，這個序列是在論文中以與上面討論的相同的方式構建的。
再回到識別可比子集的問題，這個順序可以推廣到考慮三個情況下被設輸入的所有子集。由於兩個子集A和任何輸入的B設置S：
- 考慮的情況下的
A的cardinality大於B的基數較大。那麼不能保證B的總和大於A的總和。
- 考慮這樣的
A基數等於B基數的情況。對於每個元素A[i]和從i=0 to cardinality(A)B[i]，如果從其中A[i]繪製在S指數大於從中B[i]繪製在S索引時，則它不能被保證的B總和比的A總和。否則，可以保證B的總和大於A的總和。
- 考慮
A的基數小於B的基數的情況。刪除集合B中的最小元素，使得A和B的基數相等。現在可以應用第二種情況。
爲了幫助說明這一點，我扔一起一些代碼，建立從所述功率設定設定輸入的有向無環圖，其中，每個邊緣連接具有較小子集和向所有節點具有更大子集和一個節點。此過程形成傳遞閉包，因爲所有較小的節點都將連接到所有較大的節點。然後將傳遞性減少應用到該圖上，通過走Hasse圖並存儲每個級別的寬度，將最大antichain的大小與構成此反義詞的子集一起返回，格式爲[index, value]。最終的圖表將具有等於整數序列A025591的最大反向鏈接。
（此代碼被迅速放在一起證明什麼，我想說，我提前道歉做出的任何糟糕的編碼決定！）
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's Theorem，任何偏序集，最大antichain的基數等於可用於覆蓋部分有序集合的鏈的最小數量。對於任何輸入集合，這在最壞的情況下產生一個部分訂單，其中A025591鏈。此外，用於搜索部分訂單的最壞情況時間是O(w*log(n))，其中w是圖的寬度（等於最大反壟斷的基數）。這可以通過以下事實來證明：反張鏈表徵爲沒有兩個元素可比較的無序列表，並且搜索無序列表的最壞情況時間是O(n)。此外，鏈的特徵在於有序列表，其中每個元素可與列表中的所有其他元素相比較，並且搜索有序列表的最壞情況時間是O(log n)。因此，對於長度爲w的反義鏈中的每個元素，必須在最差情況下進行相應鏈中的比較，導致在最壞情況下搜索時間爲O(w*log(n))而不是任何偏序。
該部分順序搜索時間爲任意輸入集的每個子集的總和的排序提供最差情況表徵。這是由於以下事實：對於任何輸入集合，爲了推導出最佳搜索樹，需要觀察antichain中的每個和。回想一下，使用原始集合{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中定義的指數速率增長。
我將通過說我假定輸入集中使用的所有數字都是正數並且輸入集已排序來結束這一點。事實上，如果您使用未排序的名單或正數和負數混合使用，那麼沒有兩個元素保證可比。
我很抱歉，如果這個答案很漫長，但我希望這有助於爲您提供一些洞察力，解決您正在嘗試解決的問題。
任何算法都需要指數時間：有2^n個子集。 –