配列全配列アルゴリズム(一)文字列配列全配列——一つずつ追加組合せアルゴリズム

アルゴリズムの問題:あなたのよく知っているプログラミング言語で、以下の機能の関数を設計します:1つの文字列を入力して、この文字列の中のすべてのアルファベットの全配列を出力します.プログラムは適切にコメントを追加してください.C++関数プロトタイプ:void Print(const char*str)入力サンプル:abc
分析:
n文字列の全配列がn!,2^32=4294967296,12!=479001600,11!=39916800,
本論文で論じたアルゴリズムはn<12を制限し,n>=12に関する後続の議論である.
また,ここに入力された文字も重複せず,重複は比較的複雑であり,後述する.
たとえば入力文字列がabcでvectorA,vectorBを定義する.
まずaをvectorAに入れて、それからbを取って、組み合わせて、ba,abがあって、vectorBに入れて、同時にvectorAを空にします.さらにcを取り、vectorBのba、abとそれぞれ組み合わせます.
cba,bca,bac,cab,acb,abcを順に得て,置く
vectorAにあります.
最後に空でないvectorを巡り、組合せ結果を印刷します.
このアルゴリズムは,個々に組合せアルゴリズムを追加するものである.
コードは次のように実装されます.

#define MAXNUM 12

//  2     vector，    。
std::vector<char*> g_vecA;
std::vector<char*> g_vecB;

void Print(const char *str)
{
	char Temp;
	int nLen = strlen(str);
	char Temp0[2];
	Temp0[0]=str[0];
	Temp0[1]='\0';
	g_vecA.push_back(Temp0);//            

	vector<char*>::iterator itor;
	for (int i=1; i<nLen; i++)
	{
		Temp = str[i];

		if (g_vecA.size()==0)
		{
			//  B    
			for(itor=g_vecB.begin();itor!=g_vecB.end();itor++) 
			{
				char* p = *itor;

				int nSize = strlen(p);
				// 0 nSize   Temp
				for (int j=0; j<nSize+1; j++)
				{
					char* q = new char[nSize+2];//                
					for (int k=0; k<j; k++)
					{
						q[k]=p[k];
					}

					q[j]=Temp;

					for (int m=j+1; m<nSize+1; m++)
					{
						q[m]=p[m-1];
					}

					q[nSize+1]='\0';
					g_vecA.push_back(q);
				}
			}

			for (itor = g_vecB.end()-1; itor>=g_vecB.begin(); itor--)
			{
				char* p = *itor;
				g_vecB.erase(itor);
			}
			g_vecB.clear();
		}
		else
		{
			//  A    
			for(itor=g_vecA.begin();itor!=g_vecA.end();itor++) 
			{
				char* p = *itor;
				
				int nSize = strlen(p);
				
				// 0 nSize   Temp
				for (int j=0; j<nSize+1; j++)
				{
					char* q = new char[nSize+2];
					for (int k=0; k<j; k++)
					{
						q[k]=p[k];
					}
					
					q[j]=Temp;
					
					for (int m=j+1; m<nSize+1; m++)
					{
						q[m]=p[m-1];
					}
					q[nSize+1]='\0';
					g_vecB.push_back(q);
				}
			}

			for (itor = g_vecA.end()-1; itor>=g_vecA.begin(); itor--)
			{
				char* p = *itor;
				g_vecA.erase(itor);
			}
			g_vecA.clear();
		}
	}

	int nCount = 0;

	//      
	if (g_vecA.size()==0)
	{
		for(itor=g_vecB.begin();itor!=g_vecB.end();itor++) 
		{
			nCount ++;
			char* p = *itor;
			cout << p << ", ";

			if (nCount%10 == 0)
			{
				cout << endl;
			}

			delete p;
			p=NULL;
		}
	}
	else
	{
		for(itor=g_vecA.begin();itor!=g_vecA.end();itor++) 
		{
			nCount ++;
			char* p = *itor;
			cout << p << ", ";
			
			if (nCount%10 == 0)
			{
				cout << endl;
			}

			delete p;
			p=NULL;
		}
	}

	g_vecA.clear();
	g_vecB.clear();

	cout << endl;

}

int main()  
{   
	g_vecA.clear();
	g_vecB.clear();
	char str[MAXNUM];

	char Temp[256];
	scanf("%s", Temp);

	if (strlen(Temp)>=12)
	{
		cout<<"      1-11。" <<endl;

		return 0;
	}
	else
	{
		strcpy(str, Temp);
	}

	Print(str);

	return 0;  
}  

テスト結果:
abcを入力すると:
cba, bca, bac, cab, acb, abc,
abcdを入力すると:
dcba, cdba, cbda, cbad, dbca, bdca, bcda, bcad, dbac, bdac, badc, bacd, dcab, cdab, cadb, cabd, dacb, adcb, acdb, acbd, dabc, adbc, abdc, abcd,
転載はオリジナルリンクを明記してください:http://write.blog.csdn.net/postedit/11894273