編程算法 - 組合數 代碼(C)

組合數 代碼(C)

一個字符串的組合數, 如abc, 輸出的是a, b, c, ac, ab, bc, abc, 即包含順序的組合.

類似位(bit)的全排列, 如 001, 010, 100, 011, 101, 110, 111. 

代碼:

/*
 * main.cpp
 *
 *  Created on: 2014.7.20
 *      Author: Spike
 */

/*eclipse cdt, gcc 4.8.1*/

#include <iostream>
#include <vector>
#include <string>
#include <cmath>

using namespace std;

string BinaryString(string s, int i) {
 string tmp;
 int k=0;
 while (i != 0) {
  if (i & 0x1)
   tmp.push_back(s[k]);
  k++;
  i >>= 1;
 }
 return tmp;
}

vector<string> Combination(string s) {
 vector<string> vs;
 if (s.length() == 0)
  return vs;
 int num = pow(2.0, s.length());
 for (int i=1; i<num; ++i) {
  string tmp = BinaryString(s, i);
  vs.push_back(tmp);
 }
 return vs;
}

int main(void)
{
 string s = "abc";
 vector<string> vs = Combination(s);
 for (size_t i=0; i<vs.size(); ++i) {
  cout << vs[i] << endl;
 }
 return 0;
}

輸出:

a
b
ab
c
ac
bc
abc