2。算法来源与互联网
组合算法
本程序的思路是开一个数组，其下标表示1到m个数，数组元素的值为1表示其下标
代表的数被选中，为0则没选中。
首先初始化，将数组前n个元素置1，表示第一个组合为前n个数。
然后从左到右扫描数组元素值的“10”组合，找到第一个“10”组合后将其变为
“01”组合，同时将其左边的所有“1”全部移动到数组的最左端。
当第一个“1”移动到数组的m-n的位置，即n个“1”全部移动到最右端时，就得
到了最后一个组合。
例如求5中选3的组合：
1 1 1 0 0 //1,2,3
1 1 0 1 0 //1,2,4
1 0 1 1 0 //1,3,4
0 1 1 1 0 //2,3,4
1 1 0 0 1 //1,2,5
1 0 1 0 1 //1,3,5
0 1 1 0 1 //2,3,5
1 0 0 1 1 //1,4,5
0 1 0 1 1 //2,4,5
0 0 1 1 1 //3,4,5
全排列算法
从1到N，输出全排列，共N！条。
分析：用N进制的方法吧。设一个N个单元的数组，对第一个单元做加一操作，满N进
一。每加一次一就判断一下各位数组单元有无重复，有则再转回去做加一操作，没
有则说明得到了一个排列方案。
#ifndef COMBINATORY_H
#define COMBINATORY_H
#include <iostream>
#include <cstring>
class Combinatory 
{
public:
Combinatory(const char *chars, size_t n) {
set(chars, n);
}
void parse() {
if (!isValid) {
return;
}
count = 0;
while (true) {
++count;
printResult();
size_t first10 = findFirst10();
if (first10 == END) {
break;
}
array[first10] = 0;
array[first10 + 1] = 1;
moveAll1OfFirst10ToLeft(first10);
}
std::cout << "There are " << count << " Combinaory." << std::endl;
}
void set(const char *chars, size_t n) {
this->m = strlen(chars);
this->n = n;
this->count = 0;
this->isValid = true;
if (n > m) {
isValid = false;
return;
}
this->chars = new char[m + 1];
strcpy(this->chars, chars);
this->array = new int[m];
memset(array, 0, m * sizeof(int));
for (size_t i = 0; i < n; ++i) {
array[i] = 1;
}
}
private:
enum condition {END = 8888888};
size_t m, n; // How many combinatory with n elements are there in m elements
size_t count;
bool isValid;
char *chars;
int *array;
int findFirst10() {
for (size_t i = 0; i < m - 1; ++i) {
if (array[i] == 1 && array[i + 1] == 0) {
return i;
}
}
return END;
}
void moveAll1OfFirst10ToLeft(size_t pos) {
size_t index = 0;
for (size_t i = 0; i < pos; ++i) {
if (array[i] == 1 && i == index) {
++index;
} else if (array[i] == 1) {
array[index++] = 1;
array[i] = 0;
}
}
}
void printResult() {
if (n == 0) {
for (size_t i = 0; i < m; ++i) {
std::cout << chars[i] << " ";
}
std::cout << std::endl;
return;
}
for (size_t i = 0; i < m; ++i) {
if (array[i] == 1) {
std::cout << chars[i] << " ";
}
}
std::cout << std::endl;
}
};
#endif
//int main() {
// Combinatory c("ABCDE", 0);
// c.parse();
//
// c.set("ABCDE", 1);
// c.parse();
//
// c.set("ABCDE", 2);
// c.parse();
//
// c.set("ABCDE", 3);
// c.parse();
//
// c.set("ABCDE", 4);
// c.parse();
//
// c.set("ABCDE", 5);
// c.parse();
//
// return EXIT_SUCCESS;
//}
// 求排列代码
#ifndef ARRANGEMENT_H
#define ARRANGEMENT_H
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdlib>
class Arrangement {
public:
Arrangement(const char *chars) {
set(chars);
}
void set(const char *chars) {
this->isValid = true;
if (0 == chars) {
this->isValid = false;
return;
}
this->length = strlen(chars);
this->chars = new char[this->length + 1];
strcpy(this->chars, chars);
this->array = new int[length];
this->tempArray = new int[length];
for (size_t i = 0; i < length; ++i) {
this->array[i] = length - i - 1;
}
times = 0;
}
void parse() {
times = 0;
while (!end()) {
if (isResult()) {
++times;
printResult();
}
size_t carray = 0;
size_t index = 0;
do {
carray = (array[index] + 1) / length;
array[index] = (array[index] + 1) % length;
if (++index == length) {
break;
}
} while (carray != 0);
}
std::cout << "There ard " << times << " Arrangement." << std::endl;
}
private:
size_t length;
size_t times;
bool isValid;
char *chars;
int *array;
int *tempArray;
static int compare(const void *a, const void *b) {
return *((int*)a) - *((int*)b);
}
bool isResult() {
memcpy(tempArray, array, length * sizeof(int));
qsort(tempArray, length, sizeof(int), Arrangement::compare);
for (size_t i = 0; i < length - 1; ++i) {
if (tempArray[i] == tempArray[i + 1]) {
return false;
}
}
return true;
}
void printResult() {
if (!isResult()) {
return;
}
for (size_t i = 0; i < length; ++i) {
std::cout << array[i] << " ";
}
std::cout << std::endl;
}
bool end() {
for (size_t i = 0; i < length; ++i) {
if (array[i] != 0) {
return false;
}
}
return true;
}
};
#endif // ARRANGEMENT_H
//int main() {
// Arrangement a("ABCD");
// a.parse();
//
// a.set("123456");
// a.parse();
//
// a.set("123456789");
// a.parse();
//
// return EXIT_SUCCESS;
//}