組合之01轉換法

m個數中取n個數的所有組合問題

從左到右掃描數組元素值的“10”組合，找到第一個“10”組合後將其變為“01”組合，同時將其左邊的所有“1”全部移動到數組的最左端

代碼如下：

#include 

using namespace std;

#define SIZE 100

struct data{
	int elem;
	int b;
};

inline void move(data tmp[], int num, int r){
	for(int i = 0; i < num; i++){
		tmp[i].b = 1;
	}
	for(int j = num; j < r; j++){
		tmp[j].b = 0;
	}
}

inline void println(data tmp[], int len){
	for(int i = 0; i < len; i++){
		if(tmp[i].b == 1)
			cout << tmp[i].elem << " ";
	}
	cout << endl;
}

void comb(int arr[], int len, int count){
	data tmp[SIZE];

	for(int i = 0; i < len; i++){
		tmp[i].elem = arr[i];
		if(i < count){
			tmp[i].b = 1;
		}
		else{
			tmp[i].b = 0;
		}
	}
	println(tmp, len);

	while(true){
		int j = 0;
		int num = 0;
		while(j+1 < len){
			if(tmp[j].b == 1){
				num++;
				if(tmp[j+1].b == 0){
					tmp[j].b = 0;
					tmp[j+1].b = 1;
					move(tmp, num-1, j);
					break;
				}
			}
			++j;	
		}
		if(j+1 < len)
			println(tmp, len);
		else
			break;
	}
}

int main(int argc, char* argv[])
{
	int testArr[] = {2, 5, 1, 7, 4};
	int len  = sizeof(testArr)/sizeof(int);

	comb(testArr, len, 3);

	return 0;
}