求集合{1,2,...,n}的长度等于M(M<n)的所有子集

参考:

1. http://blog.csdn.net/unclerunning/article/details/51112124 中提到的按字典顺序排序集合{1,2,…,n}的所有子集。
2. http://blog.csdn.net/unclerunning/article/details/51112399

code:

< 获取所有长度等于M的子集 >

/*这个函数用来获取所有长度等于M的子集*/
void subset_length_equalTo_M(int const &n, vector<vector<int>> &result){

    int  M;
    cout << "这个函数用来获取所有长度等于M的子集,并按字典顺序排序" << endl;
    cout << "请输入M" << endl;
    cin >> M;

    if (M == 0) { result.push_back(*new vector<int>()); return; }


    int size(0);
    vector<int> *temp;

    temp = new vector<int>(M);
    for (int i(1); i <= M; i++){
        (*temp)[i - 1] = i;
    }
    size = M;
    result.push_back(*temp);//初始化{1,2,3,...,M}
    if (size == n){ return; }


    int jumpPos = size - 2;
    while (true)
    {

        if ((*temp)[size - 1] < n){//向右shift

            //新开辟大小为size(M)的vector
            temp = new vector<int>(*temp);

            (*temp)[size - 1]++;//将第size个元素加1。
        }
        //else if ((*temp)[0]+(M-1)==n){//集合为{n-M+1,...,n-1,n}时，结束。
        else if (jumpPos == -1){//jumpPos==-1时结束。
                break;
        }
        else{//跳‘坎’

            //新开辟大小为size的vector
            temp = new vector<int>(*temp);
            (*temp)[jumpPos]++;
            for (int i(jumpPos+1); i < size; i++){
                (*temp)[i] = (*temp)[i-1] + 1;
            }

            if ((*temp)[size - 1] == n){
                jumpPos--;
            }
            else jumpPos = size - 2;

        }

        result.push_back(*temp);//将这一轮循环得到的结果保存

    }


}

< main >

int main(){

    vector<vector<int>> result;

    int n;
    cout << "输入集合上限n:" << endl;
    cin >> n;

    cout << "subset_length_equalTo_M:------------------------" << endl;
    subset_length_equalTo_M(n, result);
    for (int i(0); i < result.size(); i++){
        cout << "{";
        copy(result[i].begin(), result[i].end(), ostream_iterator<int>(cout));
        cout << "}";
        cout << endl;
    }

    system("pause");

    return 0;
}

说明:

直接跳过这个 ‘坎’ 和 ’结束’：

集合{1,2,3,4}过小，不适合说明“跳坎”以及“结束”。下面就一个大一点的集合说明这两种情况。
1. 跳坎：以从集合{1,…,7}中找出所有长度为5的集合为例。
当情况如下图所示时，我们就遇到了所谓的“跳坎”。

那么紧接着这个集合的下一个长度为5的集合是：



我们可以看到，所谓跳坎其实就是先将jumpPos位置的数自加1，然后把从jumpPos+1 ~ 4区间的所有数都迭代的置为前一个数加1。

1. 结束：以从集合{1,…,7}中找出所有长度为5的集合为例。
   当情况如下图所示时，就遇到到了最后一个长度为5的集合。
   这时有：jumpPos=-1, temp[0]=7-5+1=3