手書きフル配列(再帰|非再帰)

クリックしてリンクを開く
C++で関数を書いて、例えばFoo(const char*str)、strの全配列を印刷して、例えばabcの全配列:abc、acb、bca、dac、cab、cba
 
一.全配列の再帰的実現
便宜上、123を例に挙げます.123の全配列は123,132,213,231,312,321の6種類である.まず、213と321の2つの数がどのように得られたかを考えます.いずれも123のうち1と後の2つの数を交換したことは明らかである.次いで、123の2番目の数と3番目の数とを交換して132を得ることができる.同様に、213および321に従って231および312を得ることができる.したがって、全配列は、最初の数字からそれぞれの数を後ろの数字と交換することであることがわかります.この法則を見つけたら、再帰的なコードが簡単に書けます.

//        
#include <stdio.h>
#include <string.h>
void Swap(char *a, char *b)
{
	char t = *a;
	*a = *b;
	*b = t;
}
//k           ,m       .
void AllRange(char *pszStr, int k, int m)
{
	if (k == m)
	{
		static int s_i = 1;
		printf("   %3d   \t%s
", s_i++, pszStr);
	}
	else
	{
		for (int i = k; i <= m; i++) // i                     
		{
			Swap(pszStr + k, pszStr + i);
			AllRange(pszStr, k + 1, m);
			Swap(pszStr + k, pszStr + i);
		}
	}
}
void Foo(char *pszStr)
{
	AllRange(pszStr, 0, strlen(pszStr) - 1);
}
int main()
{
	printf("                 
");
	printf("  --by MoreWindows( http://blog.csdn.net/MoreWindows )--

");
	char szTextStr[] = "123";
	printf("%s      :
", szTextStr);
	Foo(szTextStr);
	return 0;
}

このような方法は重複する数字を考慮していないことに注意してください.
二.重複する全配列を取り除く再帰的実現
全配列は、最初の数字からそれぞれの数を後ろの数字と交換するためです.まず、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を得ることができる.全配列生成が完了します.
これにより,全配列から重複を取り除くルールも得られた--重複を除く全配列は,最初の数字から各数がそれぞれその後ろに重複しない数字と交換される.プログラミングで説明すると、i番目の数とj番目の数を交換する場合、[i,j)にj番目の数と等しい数がないことが要求されます.以下に完全なコードを示します.

//          
#include <stdio.h>
#include <string.h>
void Swap(char *a, char *b)
{
	char t = *a;
	*a = *b;
	*b = t;
}
// pszStr   ，[nBegin,nEnd)          nEnd     
bool IsSwap(char *pszStr, int nBegin, int nEnd)
{
	for (int i = nBegin; i < nEnd; i++)
		if (pszStr[i] == pszStr[nEnd])
			return false;
	return true;
}
//k           ,m       .
void AllRange(char *pszStr, int k, int m)
{
	if (k == m)
	{
		static int s_i = 1;
		printf("   %3d   \t%s
", s_i++, pszStr);
	}
	else
	{
		for (int i = k; i <= m; i++) // i                     
		{
			if (IsSwap(pszStr, k, i))
			{
				Swap(pszStr + k, pszStr + i);
				AllRange(pszStr, k + 1, m);
				Swap(pszStr + k, pszStr + i);
			}
		}
	}
}
void Foo(char *pszStr)
{
	AllRange(pszStr, 0, strlen(pszStr) - 1);
}
int main()
{
	printf("                   
");
	printf("  --by MoreWindows( http://blog.csdn.net/MoreWindows )--

");
	char szTextStr[] = "122";
	printf("%s      :
", szTextStr);
	Foo(szTextStr);
	return 0;
}

OK,これまで再帰的な方法を熟練し,文字列中の重複データが引き起こす可能性のある重複数列問題を考慮した.では、非再帰的な方法で全配列を得るにはどうすればいいのでしょうか.
 
三.全配列の非再帰的実現
全配列の非再帰的実装を考慮するには,まず文字列の次の配列をどのように計算するかを考慮する.「1234」のような次の配列が「1243」です.文字列に対して次の配列を繰り返し求めるだけで,全配列も迎刃して解く.
文字列の次の配列を計算するにはどうすればいいですか?「926520」という文字列を考えると、私たちは後ろから第1の隣接する増分数字を探して、「20」、「52」はすべて非増分で、「26」は要求を満たして、前の数字2を置換数と呼んで、置換数の下のマークを置換点と呼んで、更に後ろから置換数より大きい最小数(この数は必然的に存在する)を探して、0、2はすべてだめで、5は、5と2を交換して「956220」を得ることができます.そして、置換点後の文字列「6220」を逆さまにすると「95026」となる.
「4321」のようなすでに最も「大きい」配列については、STLの処理方法を用いて、文字列全体を逆さまにして最も「小さい」配列「1234」を得てfalseを返す.
これにより,1サイクルに文字列の次の配列を計算する関数を加えるだけで,非再帰的な全配列アルゴリズムを容易に実現できる.上記の考え方に従ってSTLの実装ソースコードを参照すると、品質の高いコードを書くのは難しくありません.ループ前に文字列をソートする場合は、クイックソートのコードを自分で書くこともできます(「白話クラシックアルゴリズムの6クイックソートクイック完了」を参照)、VCライブラリのクイックソート関数を直接使用することもできます(「VCライブラリ関数のクイックソート関数を使用する」を参照).完全なコードを以下に示します.

//         
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
void Swap(char *a, char *b)
{
	char t = *a;
	*a = *b;
	*b = t;
}
//    
void Reverse(char *a, char *b)
{
	while (a < b)
		Swap(a++, b--);
}
//     
bool Next_permutation(char a[])
{
	char *pEnd = a + strlen(a);
	if (a == pEnd)
		return false;
	char *p, *q, *pFind;
	pEnd--;
	p = pEnd;
	while (p != a)
	{
		q = p;
		--p;
		if (*p < *q) //      2 ,        
		{
			//               
			pFind = pEnd;
			while (*pFind <= *p)
				--pFind;
			//  
			Swap(pFind, p);
			//          
			Reverse(q, pEnd);
			return true;
		}
	}
	Reverse(p, pEnd);//         ,       true
	return false;
}
int QsortCmp(const void *pa, const void *pb)
{
	return *(char*)pa - *(char*)pb;
}
int main()
{
	printf("                  
");
	printf("  --by MoreWindows( http://blog.csdn.net/MoreWindows )--

");
	char szTextStr[] = "abc";
	printf("%s      :
", szTextStr);
	//    
	qsort(szTextStr, strlen(szTextStr), sizeof(szTextStr[0]), QsortCmp);
	int i = 1;
	do{
		printf(" %3d   \t%s
", i++, szTextStr);
	}while (Next_permutation(szTextStr));
	return 0;
}

ここまで再帰と非再帰の方法を用いて全配列問題を解決したが,まとめてみると:
1.全配列とは、最初の数字からそれぞれの数を後ろの数字と交換することである.
2.重量除去の全配列は、最初の数字から各数がそれぞれその後ろに繰り返されない数字と交換される.
3.全配列の非再帰は、置換数と置換点を後から前へ探し、置換数より大きい最初の数を後から前へ探して置換数と交換し、最後に置換点後のすべてのデータを逆にすることである.