全配列アルゴリズムの再帰とSTL実現,八皇后問題

ネット上に伝わる再帰型全配列アルゴリズムで、オリジナルは不明である.配列に重複する要素があればどうなるか分からないだけだ.

#include <iostream>

void permutation(char* list, int begin, int end) {
    if(begin < end) {
        for(int i = begin; i <= end; ++i) {
            std::swap(list[i], list[begin]);
            permutation(list, begin + 1, end);
            std::swap(list[i], list[begin]);
        }
    }
    else {
        for(int i = 0; i <= end; ++i){
            std::cout << list[i];
        }
        std::cout << std::endl;
    }
}

int main() {
    char a[] = "1234";
    std::cout << a << "        ：" << std::endl;
    permutation(a, 0, (int)strlen(a) - 1);
    return 0;
}

 
にあるhttp://blog.csdn.net/hackbuteer1/article/details/6657435STLの構想実現の全配列を見る
STLにはnext_という関数がありますpermutation()は、1つのシーケンスに対して辞書に従って並べ替えられた次の配列が存在する場合、trueを返し、その配列を生成し、そうでなければfalseを返す役割を果たす.全配列を生成するために、このシーケンスが整列している場合、すなわちsortを1回呼び出すことに注意してください.

#include <iostream>
#include <algorithm>

void permutation(char* list, int length) {
    std::sort(list, list + length);
    do {
        for(int i = 0; i < length; ++i) {
            std::cout << list[i];
        }
        std::cout << std::endl;
    }while(std::next_permutation(list, list + length));
}

int main() {
    char a[] = "1234";
    std::cout << a << "        ：" << std::endl;
    permutation(a, (int)strlen(a));
    return 0;
}

 
全配列アルゴリズムから古典的な問題を連想する:八皇后問題

/* ----- eight queen ----- */

#include <iostream>
#include <algorithm>

int g_number = 0;

void printQueen(int list[], int length) {
    printf("queenList[%d]:\t", g_number);
    for (int i = 0; i < length; ++i) {
        printf("%d ", list[i]);
    }
    printf("\r
");
}

bool check(int list[], int length) {
    for (int i = 0; i < length; ++i) {
        for (int j = i + 1; j < length; ++j) {
            if ( (i - j == list[i] - list[j]) || (i - j == list[j] - list[i]) ) {
                return false;
            }
        }
    }
    return true;
}

void permutation(int ColumnIndex[], int index, int length) {
    if (index == length) {
        if(check(ColumnIndex, length)) {
            ++g_number;
            printQueen(ColumnIndex, length);
        }
    }
    else {
        for(int i = index; i < length; ++ i) {
            std::swap(ColumnIndex[i], ColumnIndex[index]);
            permutation(ColumnIndex, index + 1, length);
            std::swap(ColumnIndex[i], ColumnIndex[index]);
        }
    }
}

void eightQueen() {
    const int queenCount = 8;
    int queenList[queenCount];
    for (int i = 0; i < queenCount; ++i) {
        queenList[i] = i;
    }
    permutation(queenList, 0, queenCount);
}

int main(int argc, char const *argv[]) {
    eightQueen();
    return 0;
}