全配列アルゴリズム:重複要素を含まない、重複要素を含む、アルファベット順配列

組合せ数学に関連するいくつかの背景では、全配列クラスのデータセットを生成する必要があります.全配列を生成するには,以下の2つのアルゴリズムが最もよく用いられる.
recursive generating
このアルゴリズムは、1つの要素が異なる配列を受け入れ、再帰的な呼び出しによってすべての全配列シーケンスを生成する.
再帰の原則は,生成シーケンスの全配列P(a 1,a 2,…,an)が生成シーケンスに等価であることである(以下の理解が重要である!!)
…
これは再帰アルゴリズム設計のdeduction-caseを構成する.base-caseは、全配列を生成するシーケンスに1つの要素しかありません.
アルゴリズム全体は概ね次のように実現できる.

void GenePermu(int A[], int i, int n)
{
	if (i == n-1)
	{
		for (int k = 0; k < n; ++k)
		{
			cout<

ここで、nはシーケンス中の要素個数を表し、iは現在処理されている(想像上の)要素個数を表す.
このアルゴリズムの実装は比較的優雅である(明らかにエンジニアリング上の設計の優雅さではない)が、使用上は小さな問題がある可能性がある:前述した入力要素は唯一異なる.入力に重複要素が含まれている場合、このアルゴリズムは重複結果を生成します.
数学的には全配列要素の相互性を確保する傾向があるが,実際の応用では避けられない.
1つの比較的直接的な方法は、再帰前に次の要素が重複しないことを確保することである.具体的なポリシーは次のとおりです.
A[i],A[j]を交換する前に、A[i..j-1]に要素がA[j]と等しくないことを保証します.
これは2つの理由に基づいています.
(1)A[i],A[j]を交換するたびに配列が生成され,P(A[i],.,P[j])の配列が重複しないようにするだけでよい.
(2)A[i],A[j]を交換する前に、A[i..j-1]に元素とA[j]が等しい、すなわちA[k]=A[j],i<=kが存在する
改善の実現は以下の通りである.

void GenePermu(int A[], int i, int n)
{
	if (i == n-1)
	{
		for (int k = 0; k < n; ++k)
		{
			cout<bool
{
for (int t = i; t < j; ++t)
{
if (A[t] == A[j])
{
return false;
}
}
return true;
};
for (int k = i; k < n; ++k)
{
if (CheckSwapValid(A, i, k))
{
swap(A[k], A[i]);
GenePermu(A, i + 1, n);
swap(A[k], A[i]);
}
}
}
}

basing on next_permutation
もう1つの一般的なアルゴリズムは、入力された1つの配列に対して次の辞書シーケンスの配列を構築することである.ディクショナリ・シーケンスについては、「」を参照してください.http://en.wikipedia.org/wiki/Lexicographical_order
たとえば、入力の1,3,2に対して、次の辞書順の2,1,3が出力されます.
アルゴリズムの大まかな考え方は以下の通りである.
(1)入力された辞書の許容配列について、第1のペアがa[j](2)a[j] (3)a[j]とa[k](4)を交換してa[i+1..n]をインクリメンタルに配列させるを満たすことを逆検索する
考えを言って、重点は分析です.
最初のステップは、辞書の順序定義に基づいて行います.
一方,条件を満たすjを見つけた後,a[j+1..n]は(厳密ではない)単調に減少配列しているという隠れた性質があり,これは反証法と第一歩を組み合わせて矛盾を導出することによって証明できる.したがって,第2部では,第1の条件を満たすkを検索するだけで,最小値の原則も満たす.
第4のステップでは、上記の逆シーケンス条件から分かるように、インクリメンタル配列特性は、a[j+1..n]を逆置するだけでよい.
次に,(1)要素繰返し(2)入力が最後の辞書順に配列されていることを考慮する.
実は最初の問題はすでに解決されました.最初のステップで私たちが満たす条件は厳格で小さいからです.そしてこの断言により,我々は第2ステップで条件を満たすkを検索する際に,必ずこのようなkを見つけることができる.
2番目の問題は、入力が最後の辞書順、すなわち単調な減算配列である場合、最初のステップは直接境界を越えます.解決策はjが負でないことを簡単に保証するだけでよい.
また,このアルゴリズムを用いて全配列を生成する場合は,入力配列が最初の辞書シーケンス,すなわち単調なインクリメント配列であることを保証すべきである.
コードの1つの実装は、次のとおりです.

bool GetNextPermu(int A[], int n)
{
	int j = n - 2;
	while (A[j] >= A[j+1] && j >= 0)
	{
		--j;
	}	

	if (j < 0)
	{
		wcout<= A[i])
	{
		--i;
	}

	swap(A[j], A[i]);

	int l = j + 1, r = n - 1; 
	while (l < r)
	{
		swap(A[l], A[r]);
		++l;
		--r;
	}

	return true;
}