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;
//}