c++ - 使用 vector 迭代地创建集合的子集

Question

所以我想创建一个子集，通过代码运行该子集，然后创建一个新的子集。我正在为集合和子集使用 vector 。到目前为止，我有 3 个嵌套的 for 循环，但我无法找出我需要的变量。

这是我想做的。 set = {0, 1, 2, 3, 4, 5} 值匹配索引只是为了简化这个例子。我现在想要 subset = {} -> {0} -> {1} -> ... -> {0,1} -> {0,2} -> ... -> {0,5} -> {0,1,2} -> ... -> {0,4,5}。我在用变量表示条件时遇到问题。

基本上我想要第一个 for 循环来增加子集的大小。从 0 到 set.size() (这很简单)。在该循环中，我希望有一个迭代器对应于子集元素中的索引。我将此迭代器初始化为 subset.size()，以便我们首先处理最后一个元素，然后处理子集中的第一个元素。然后是第三个 for 循环，我想在集合中的可能值之间进行迭代。假设我们当前的子集 = {0,1,2} 我如何让我的程序知道将值“2”放入子集的最后一个元素中，然后是 1，然后是 0？

我认为它会涉及到与 set.size()-1 和 subset.size()-1 的区别？但我不太确定如何。所以然后我想遍历直到 {0,1,5} 然后是 {0,4,5} 但是我又一次不确定如何告诉程序停止在 4，而不是 5。我再次认为这个是有区别的东西，但我不太明白。

回顾一下:

for loop to iterate through subset size
    for loop to iterate through subset "working" element, starting from back
        for loop to iterate through that index of subset,
        starting from the correct corresponding set value to ending
        at the correct corresponding set value

这样子集从 {} -> {0} -> {1} ->...-> {0,1} -> {4,5} -> {1,2,3} -> ... -> {1,4,5} 我实际上不需要 subset = {1,2,3,4,5} 但如果我不能在此之前停止，它不会伤害我的代码。我再次希望将起点和终点表示为变量以使内部循环工作，但我无法弄清楚。非常感谢任何能帮助我的人。

Answer 1

这就是我大致的处理方式。

//handle null subset
for ( int size = 1; size < n; i++ ) {
    int indices[size];
    for ( int i = 0; i < size; i++ ) indices[i] = i;

    while ( indices[0] <= n - size ) {
        int i;
        for ( i = 1; indices[size - i] == n - i; i-- );
        indices[i]++;
        for ( i = i + 1; i < size; i++ ) indices[i] = indices[i-1] + 1;
        //print out elems using the indices in `indices`
    }
    //done with all subsets of size `size`
}

外循环应该很容易解释。包括 0 似乎会使一些内部逻辑变得烦人，所以我从大小为 1 的子集开始。

indices 保存应包含在当前子集中的元素的索引。它以索引 0-size-1 开始。

while 的条件不是很明显。它生成的最后一个有效子集包含最后一个 size 元素，因此如果第一个索引超过 n - size，我们就做得太过了。

while 循环内部只是递增子集。它寻找最后一个可以递增并仍然给出有效子集的元素，递增它，然后将所有后续元素重置为尽可能小。然后你以某种方式打印出来。

而且这应该接近于满足您的需求。让我知道它是否需要澄清或更正。