c++ - 一个一个生成一个大小为n的子集来降低复杂度？

Question

void AlgoMMPCbar::subs(const std::vector<unsigned int>& org, const std::vector<unsigned int>& pre, size_t k, size_t n, SubSets& c){
   if (n <= 1) {
    for(size_t i = k; i < org.size(); i++){
        std::vector<unsigned int> v(pre);// instead of printing...
        v.push_back(org.at(i));
        c.push_back(v);
    }
} else {
    size_t n1 = n - 1;
    for(size_t i = k; i != org.size() - n1; i++){   // 
        std::vector<unsigned int> s(pre);
        s.push_back(org.at(i));
        subs(org,s,i+1,n1,c);
    }
}
}
void AlgoMMPCbar::computeSubSets(const std::vector<unsigned int>& org, size_t& n, SubSets& c){
 c.clear(); // clear previous data

std::vector<unsigned int> pre;
pre.reserve(n+1); // for performance
    if (n==0)
      c.push_back(pre);
else
        subs(org,pre,0, n, c); 
}

上述代码用于生成大小为 n 的子集以供进一步测试/处理。但我从不需要测试所有这些生成的子集(在最坏的情况下它会检查它们)。该程序的主要耗时部分是子集生成。现在我想将上述功能转换为一个一个地生成子集(不是一次全部，所以，我可以随时停止进一步的子集生成)。

请分享您的专业知识，将上述功能转换为类似 subset.next() 的函数，以节省计算时间。

提前致谢。

Answer 1

say ind 以递增顺序维护子集中元素的索引，即

ind[0] < ind[1] < ... < ind[n-1]

找到最小的 j 使得

j == n-1 || ind[j] + 1 < ind[j+1]

你可以到下一个子集

ind[j]++
ind[0] = 0; ind[1] = 1; ... ind[j-1] = j-1

请注意，新的 ind 数组仍然是有序的。你可以很容易地证明从

ind[] = [0, 1, ..., n-1]

您将通过上述过程迭代生成所有子集。如果您在上面使用一些技巧来“保持”j 的值而不是进行线性搜索，那么您可以获得快速代码。