【プログラミングテーマ】文字列の並び(文字列)★

53.文字列の並び(文字列).タイトル:文字列を入力し、その文字列のすべての並びを印刷する.例えば、文字列abcを入力すると、文字a、b、cで並べられるすべての文字列abc、acb、bac、bca、cab、cbaが出力される.
 
この問題は私に1日かかったので,よくまとめなければならない.
考え方:この問題は少し難しいと感じています.主に文字列の中の文字が重複する可能性があります.私の考えは、全部で何種類の文字と各文字が現れた回数を統計し、各位置がこれらの文字変数に対して、次の位置の利用可能な文字を減らして、さらに遍歴することです.

/*

53.      （   ）。

  ：       ，               。

        abc，       a、b、c             

abc、acb、bac、bca、cab   cba。

*/



#include <stdio.h>

#include <string.h>

#include <stdlib.h>



char A[128][2] = {0}; //               

char ANS[10000]; //     

int N; //     

int LEN; //       

int getTimes(char * in) //                   

{

    int len = strlen(in);

    bool B[100] = {0};

    int n = 0;

    for(int i = 0; in[i] != '\0'; i++)

    {

        if(B[i] == false)

        {

            for(int j = i; in[j] != '\0'; j++)

            {

                if(in[j] == in[i])

                {

                    A[n][0] = in[i];

                    A[n][1]++;

                    B[j] = true;

                }

            }

            n++;

        }

    }

    return n;

}



void traverse(int len) //             A       0    

{

    if(len == 0)

    {

        for(int i = 0; i < LEN; i++)

        {

            printf("%c ", ANS[i]);

        }

        printf("
");

        return;

    }

    for(int i = 0; i < N; i++)

    {

        if(A[i][1] != 0) //     0           

        {

            ANS[LEN - len] = A[i][0]; //          

            A[i][1]--;  //         1

            traverse(len - 1); //         

            A[i][1]++;  //            

        }

    }

    

}



void getall(char * in)

{

    LEN = strlen(in);

    N = getTimes(in);

    traverse(LEN);

}

int main()

{

    char in[100] = "abcc"; 

    getall(in);

    return 0;

}

 
 
书き终わった后に自分の书くのがよくないと感じて、多くの全局の変数、见ているのがつらいです.
ネット上で良い解答を見ました:http://blog.csdn.net/hackbuteer1/article/details/7462447
再帰と非再帰の構想を与えた.私は見終わった後も考えに倣って書き直して、またその通りに修正しました.
二、重複する全配列を取り除く再帰的な実現は、全配列が最初の数字から各数がそれぞれその後ろの数字と交換されるためである.まず、1つの数が後ろの数字と同じであれば、この2つの数は交換されないという判断を加えてみましょう.122のように、第1の数は、後で212、221に交換される.そして122のうちの2番目の数は3番目の数と交換する必要はないが、212では2番目の数と3番目の数が異なり、交換後221が得られる.122のうちの第1の数と第3の数とを交換した221と重複している.だからこの方法はだめです.換言すれば、122に対して、第1の数1と第2の数2とを交換して212を得、その後、第1の数1と第3の数2を交換することを考慮し、この場合、第3の数は第2の数に等しいため、第1の数は第3の数と交換しない.さらに212を考慮すると、その2番目の数と3番目の数との交換は解決221を得ることができる.全配列生成が完了します.これにより,全配列から重複を取り除くルールも得られた--重複を除く全配列は,最初の数字から各数がそれぞれその後ろに重複しない数字と交換される.
三、全配列の非再帰実装全配列の非再帰実装を考慮するには、まず文字列の次の配列をどのように計算するかを考慮する.「1234」のような次の配列が「1243」です.文字列に対して次の配列を繰り返し求めるだけで,全配列も迎刃して解く.文字列の次の配列を計算するにはどうすればいいですか?「926520」という文字列を考えると、後ろから最初の2つの隣接する増分数字を探します.「20」、「52」はいずれも非増分で、「26」は要求を満たし、前の数字2を置換数と呼び、置換数の下の記号を置換点と呼びます.さらに置換数よりも大きい最小数(この数は必然的に存在する)を後から探すと、0、2ともだめで、5は可能で、5と2を交換して「956220」を得て、それから置換点後の文字列「6220」を逆さまにすると「95026」を得る.「4321」のようなすでに最も「大きい」の配列については、STLの中の処理方法を採用して、文字列全体を逆さまにして最も「小さい」の配列「1234」を得るfalseを返します.
これにより,1サイクルに文字列の次の配列を計算する関数を加えるだけで,非再帰的な全配列アルゴリズムを容易に実現できる.上記の考え方に従ってSTLの実装ソースコードを参照すると、品質の高いコードを書くのは難しくありません.ループ前に文字列をソートする場合は、すばやくソートされたコードを自分で書くことができます.

/*

http://blog.csdn.net/hackbuteer1/article/details/7462447

                           ，           。              ，                 

    。         。

           ，                  ，      。

*/



//  

#include<stdio.h>

#include<string.h>

#include <algorithm>

using namespace std;

bool isswap(char * pBegin, char * pNow)

{

    for(char *p = pBegin; p < pNow; p++)

    {

        if(*p == *pNow)

            return false;

    }

    return true;

}



void traverse(char * pStr,char * pBegin)

{

    if(/**pBegin == '\0'*/strlen(pBegin) == 1) //         

    {

        static int n = 0;

        printf("%d: %s
", ++n, pStr);    

    }

    else

    {

        for(char *p = pBegin; *p != '\0'; p++)

        {

            if(isswap(pBegin, p))

            {

                swap(*pBegin, *p);    //  swap            

                traverse(pStr, pBegin + 1);

                swap(*p, *pBegin);

            }

        }

    }

}



//   

int cmp(const void * a,const void * b)

{

    return *((char *)a) - *((char *)b);

}



void reverse(char * pBegin, char * pEnd)

{

    while(pBegin < pEnd)

    {

        swap(*pBegin++, *pEnd--);

    }

}

bool nonrtraverse(char * pStr)

{

    int l = strlen(pStr);

    char * pEnd = pStr + l - 1; //        

    if(pStr == pEnd)  //            

        return false;

    for(char *p = pEnd; p != pStr; p--)

    {

        char * q = p - 1;

        if(*q < *p)

        {

            char* pFind = pEnd;

            while(*pFind <= *q) //    ，             

                --pFind;

            swap(*q, *pFind);

            reverse(p, pEnd);

            return true;

        }

    }

    reverse(pStr, pStr +l - 1);

    return false;

}



int main()

{

    char str[30] = "1224";

    traverse(str, str);

    qsort(str, strlen(str)-1, sizeof(char), cmp);

    int i = 0;

    do

    {

        printf("%d:%s
", ++i, str);

    }

    while(nonrtraverse(str));

    return 0;

}