全配列アルゴリズムのPerm再帰アルゴリズム実現

3548 ワード

全配列アルゴリズムのPerm再帰アルゴリズム実現
タイトルの説明:
異なる小文字からなる文字列を指定し、この文字列のすべての全配列を出力します.小文字には「a」<'b'<...<」があると仮定します.y'<'z'であり、与えられた文字列のアルファベットは小さい順に並べられている.
入力:
入力は1行のみで、異なる小文字からなる文字列で、既知の文字列の長さは1～6です.
出力:
この文字列のすべての配列方式を出力し、行ごとに1つの配列をします.アルファベット順の比較的小さい配列が前に必要です.アルファベット順は、既知のS=s 1 s 2...sk , T = t1t2...tkでは、Sサンプル入力:

abc

サンプル出力:

abc
acb
bac
bca
cab
cba

ヒント:
各サンプルの出力が終了したら、もう1つのリターンを出力します.
皆さんはperm再帰アルゴリズムの全配列を求めるのはよく知られていないと思いますが、私が貼った問題はpermアルゴリズムで解決できません.なぜですか.まず、テーマは全配列に対して非常に厳しい順序が要求されています.すなわち、辞書の順序で並べられています.このpermアルゴリズムでは満足できません(小さな変化で実現できるかもしれませんが、ここでは議論しません).ではpermアルゴリズムの核心的な考え方についてお話しします.例えば、あなたの1の全配列を挙げると、それは簡単ではないと思います.では、次に難易度を深めて1、2の全配列を求めるのは、実は難しくありません.今、1、2、3、4、5の全配列を求めてみましょう.そうですか.3,4,5の全配列は3で始まる4,5の全配列と4で始まる3,5の全配列と5で始まる3,4の全配列であると考えられる.これがpermアルゴリズムの核心思想であり、通俗的な式を列挙しています.
従って,p={r 1,r 2,r 3,...,rn}のセットをperm(p),pn=p−{rn}として全配列すると推定できる.
したがってperm(p)=r 1 perm(p 1),r 2 perm(p 2),r 3 perm(p 3),...,rnperm(pn).
n=1のときperm(p}=r 1.
次のコードを貼ります.

#include<cstdio>
#include<cstring>
#define MAX 10

using namespace std;

void swap(char str[],int i,int j)
{
	int temp;
	temp=str[i];
	str[i]=str[j];
	str[j]=temp;
}

void perm(char str[],int k,int m)
{
	int i;
	if(k>m)
	{
		for(i=0;i<=m;i++)
			printf("%c",str[i]);
		printf("
");
	}
	else
	{
		for(i=k;i<=m;i++)
		{
			swap(str,k,i);
			perm(str,k+1,m);
			swap(str,k,i);
		}
	}
}

int main(int argc,char *argv[])
{
	char str[MAX];
	while(scanf("%s",str)!=EOF)
	{
		int len=strlen(str);
		perm(str,0,len-1);
		printf("
");
	}

	return 0;
}

ここで2つの問題が発生します.1つはタイムアウトで、2つは答えの順序が間違っています..
毎回配列中の数と最初の数を交換するため、すべての全配列を重視しているが、シフト順序の問題には気づかず、1 2 3 4の全配列、2,3,4の全配列を処理すると4と2が交差し、1432が1423の前に並ぶという問題が発生する.したがって,全配列の順序に非常に厳密な順序があればpermアルゴリズムは用いられない.
例えばabcの全配列:
整列全列:perm全列:

abc abc acb acb bac bac bca bca cab cba cba cab

次にpermアルゴリズムのもう一つの大きな問題を見てみましょう.もし重複要素のあるシーケンスを全列に並べたら?たとえば、入力122は何を出力しますか.残念ながら、出力結果は、12221221221221212(直接言えばpermアルゴリズムの実行フローがわかります)、このような結果は明らかに間違っています.どうすればいいのでしょうか.1番目の数と2番目の数の交換は212(このとき1番目の数が2番目の位置にある)を得て、3番目の数と2番目の数の交換は221を得ます(このとき第1の数1は第3の位置にあり、第3の数は第2の位置にあり、第2の数は第1の位置にある)が、第2の数と第3の数は等しい(元のシーケンス上)が、これは直接第3の数と第1の数を交換したことに相当しないか?一気に次のことをしてしまう.したがって、第iの数と第jの数を交換する際には[i,j]が要求されるでj番目の数に等しい数がなければいいのですが..
コード:

#include<cstdio>
#include<cstring>
#define MAX 10

using namespace std;

void swap(char str[],int i,int j)
{
	int temp;
	temp=str[i];
	str[i]=str[j];
	str[j]=temp;
}

bool IsUnique(char str[],int start,int end)//     
{
	int i;
	for(i=start;i<end;i++)
		if(str[i]==str[end])
			return false;
	return true;
}

void perm(char str[],int k,int m)
{
	int i;
	if(k>m)
	{
		for(i=0;i<=m;i++)
			printf("%c",str[i]);
		printf("
");
	}
	else
	{
		for(i=k;i<=m;i++)
		{
			if(IsUnique(str,k,i))
			{
				swap(str,k,i);
			    perm(str,k+1,m);
		    	swap(str,k,i);
			}
		}
	}
}

int main(int argc,char *argv[])
{
	char str[MAX];
	while(scanf("%s",str)!=EOF)
	{
		int len=strlen(str);
		perm(str,0,len-1);
		printf("
");
	}

	return 0;
}

Couldn’t find the element to insert the template. Make sure your `data-association-insertion-*` on `link_to_add_association` is correct.

[rails]ransackを使用して検索機能