2013-12-21

使用STL的prev_permutation生成组合数

今天碰到这么一个要求生成组合数的题目。其实前几天在果壳上就有人发过类似的题目，不过他那题其实是无解的。

---

题目简单说就是给你k个数，让你生成这k个数中取出6个所有的组合。要求按照数字升序排列。

输入每行第一个数为k，后面是k个数。如果k为0，则表示输入结束。

一般的思路是写一个递归程序——先生成k-1个数的组合数，再在后面添加上第k个数的所有情况。

不过会出点问题，就是不好排序。我曾经尝试着先把输出写进缓存，然后排序再输出。

但是这明显不是好的风格嘛。

就在这时我想到了STL的permutation函数。

---

在写果壳的看到的那题的时候，我了解到了有这么一个东西的存在，它能生成一组数据的全排列。

std::next_permutation(iterator begin, iterator end);和std::prev_permutation(iterator begin, iterator end);

知道了这个东西之后，我还知道了STL并没有能够遍历生成组合数的东西。当时觉得十分不解。。。直到我知道了现在这种方法。

---

简单的说，我们用一个二进制序列来表示我们需要取出的元素。比如我们有15个元素，需要从中取6个。

我们可以把这个序列定义为111111000000000。

其中1表示该元素取出，0表示该元素不取出。

如何遍历这个组合数呢？我们可以轻易发现所有的组合数刚好就是上面那个序列的全排列！

于是我们生成一个布尔值序列，并用STL的prev_permutation排列它。（←为什么不用next_permutation？其实自己试一下就知道了，当然是因为方向不一样，我这里要的是升序。）

然后这个序列中布尔值为真的地方，就是对应的目标序列中需要取出的元素。

---

最后，我还是会附上代码的：

#include <cstdio> 
#include <cstring> 
#include <string> 
#include <iostream> 
#include <algorithm> 
#include <vector> 
using namespace std; 
int S[140]; 
vector<bool> Serial; 
void CombinationNumber(int n,int k){ 
    Serial.clear(); 
    for(int i=0;i<k;i++){ 
        Serial.push_back(true); 
    } 
    for(int i=0;i<n-k;i++){ 
        Serial.push_back(false); 
    } 
    do{ 
        //int ZenMeNengGeShiCuoWuNe=0; 
        for(int i=0;i<n;i++){ 
            if(Serial[i]){ 
                cout<<S[i]; 
                //ZenMeNengGeShiCuoWuNe++; 
                //if(ZenMeNengGeShiCuoWuNe!=k){ 
                cout<<" "; 
                //} 

            } 
        } 
        cout<<endl; 
    }while(prev_permutation(Serial.begin(),Serial.end())); 
} 

int main(){ 
    int k; 
    while(cin>>k){ 
        if(k==0)break; 
        else{ 
            for(int i=0;i<k;i++){ 
                cin>>S[i]; 
            } 
        } 
        CombinationNumber(k,6); 
        cout<<'n'; 
    } 
    return 0; 
} 

此题在提交的时候还把我坑坏了，当然这个和本文主题无关，在此略过不表，具体来说可见代码中被注释掉的部分。

main