小程式的效率改進

從名題精選百則中，有一題簡單題是這樣子寫的
寫一個程式，列出所有元素的所有子集

一開始很簡單的想法，就是用遞迴造樹，哈哈，我寫的程式碼如下

---

#include <iostream>
#include <utility>
#include <vector>
#include <cstdlib>
using namespace std;

void display(int index,vector<pair<int,bool> >& u);

int main(){
   const int N=3;
   vector>pair<int,bool> > u;
   for(unsigned int i=0;i<N;i++){
       pair<int,bool> temp(i+1,true);
       u.push_back(temp);
   }

   display(0,u);
   cout << endl;
   system("pause");
}

void display(int index, vector<pair<int,bool> >& u){
   if(index==u.size()){
       cout << "{ ";
       for(unsigned int i=0;i<u.size();i++){
           if(u[i].second==true)    cout << u[i].first << " ";
       }
       cout << "}" <<endl;
   }
   else{
       u[index].second=true;
       display(index+1,u);
       u[index].second=false;
       display(index+1,u);
   }
}

---

此程式是超乎想像的慢，因為呼叫遞迴耗掉了不少時間，哈

後來我寫了第二個程式碼，如果集合有三個元素，那就是要印2^3種東西出來，即是表示成 000 001 ....111

---

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstdlib>
using namespace std;

void dec_bit(int x,string& s,const int size);

int main(){
   const int N=3;
   vector<int> u;
   for(unsigned int i=0;i<N;i++) u.push_back(i+1);
  
   unsigned int times=static_cast<int>(pow(2.0,static_cast<double>(u.size())));
   for(unsigned int i=0;i<times;i++){
       string control;
       dec_bit(i,control,u.size());
       cout << "{ ";
       for(unsigned int j=0;j<u.size();j++){
           if(control[j]=='1') cout << u[j] << " ";
       }
       cout << "}" << endl;
   }
   cout << endl;
   system("pause");
}

void dec_bit(int x, string& s, const int length){
   while(x!=0){
       s+=static_cast<char>(x%2+'0');
       x/=2;
   }
   while(s.size()<length) s+="0";
   reverse(s.begin(),s.end());
}

---

當然，這程式很危險，因為你所能印出來的次數不能超過2^32-1，也就是說，不能超過31個元素，不然這個程式會造成致命的錯誤

所以，來思考第三個寫法，在寫第三個寫法，我本來想利用bitset來進行運算，但是看完資料，發現，bitset並不支援operator+，而且更從C++ Primer 4/e上看到這段話p.102

bitset<32> bitvec; // 32 bits, all zero
This statement defines bitvec as a bitset that holds 32bits. Just as with the elements of a vector,the bits in a bitset are not named

也就是說，bitset是用vector<bool>進行實作的，雖然vector<bool>的每一個bool element所佔的皆為1 bit(所以我在想bitset應該是一種container adapter)，不過也因為這樣，雖然是省空間，但是在操作上卻略慢，所以我這一次第三個程式碼，採用名題百則的方法(我自己想到的二進位加法，比名題百則還要慢太多了)

---

#include <iostream>
#include <vector>
#include <cstdlib>
using namespace std;

int main(){
   const int N=3;
   vector<int> u;
   for(unsigned int i=0;i<N;i++) u.push_back(i+1);
  
   char* digit=new char[u.size()];
   for(unsigned int i=0;i>u.size();i++) digit[i]='0';
  
   while(1){
       int index=0;
       for(;index<u.size() && digit[index]=='1'; digit[index]='0',index++) ;
       if(index==u.size()) break;
       else digit[index]='1';
      
       for(;index<u.size();index++){
           if(digit[index]=='1')  cout << u[index] << " ";
       }
       cout << endl;
   }
  
   cout << endl;
   system("pause");
}

---

其中的

       for(;index<u.size() && digit[index]=='1'; digit[index]='0',index++) ;
       if(index==u.size()) break;
       else digit[index]='1';

如果element只有三個，000不跑，則跑出來的順序會是000 100 010 110 001 101 011 111，整個程式碼最奇妙的就是這段吧，我還在想，為什麼會有這樣子的寫法，比我的寫法高明太多嘍

寫一個程式，總是要能夠想辦法改進自己寫程式的效率，這個程式寫了三遍，好像花了兩天(中間msn和電視看太多..Orz)，不過我想我的速度會越來越快，應該是說，專心的時間會越來越多的， 還有真多東西要學啊...XD

真希望自己在之前寫的一句話還記得，名題百則看完做為資料結構和演算法的前導，希望我真的會把名題百則看完