2。算法來源與互聯(lián)網(wǎng)
組合算法
本程序的思路是開一個(gè)數(shù)組，其下標(biāo)表示1到m個(gè)數(shù)，數(shù)組元素的值為1表示其下標(biāo)
代表的數(shù)被選中，為0則沒選中。
首先初始化，將數(shù)組前n個(gè)元素置1，表示第一個(gè)組合為前n個(gè)數(shù)。
然后從左到右掃描數(shù)組元素值的“10”組合，找到第一個(gè)“10”組合后將其變?yōu)?nbsp;
“01”組合，同時(shí)將其左邊的所有“1”全部移動(dòng)到數(shù)組的最左端。
當(dāng)?shù)谝粋€(gè)“1”移動(dòng)到數(shù)組的m-n的位置，即n個(gè)“1”全部移動(dòng)到最右端時(shí)，就得
到了最后一個(gè)組合。
例如求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進(jìn)制的方法吧。設(shè)一個(gè)N個(gè)單元的數(shù)組，對第一個(gè)單元做加一操作，滿N進(jìn)
一。每加一次一就判斷一下各位數(shù)組單元有無重復(fù)，有則再轉(zhuǎn)回去做加一操作，沒
有則說明得到了一個(gè)排列方案。
#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;
//}