uva331

テーマの意味がわかりにくい(英語のレベルが料理より高い)ので、まず肝心な内容を翻訳しましょう.
1つの配列を交換する隣接する2つの要素は、バブルソートと同様に配列ソートの機能を達成することができるが、交換のスキームは1つではない可能性がある.例えば配列A【3】が3、2、1、2、3の場合、位置1、2の要素(配列が2、3、1)を先に交換し、次に位置2、3の要素(2、1、3)を交換し、最後に位置1、2の要素(1、2、3)を交換することができる.もちろん、先に位置2と3(312)を交換し、次に位置1と2(132)を交換し、最後に位置2と3(123)を交換することもできるが、上述した方法は2,1,2であり、これはスキーム2である.もちろん、このような案は無限であり、例えば1,1,2,1,2のようにソートを実現することができるが、この場合、前の2回の交換は無駄であり、移動回数が最小の案ではない.この問題は移動回数が最も少ないシナリオが何個あるかを要求し,例の場合は2つのシナリオしかない.
題意を理解すれば難しくはないが,遡及を続け,順序に達したら案数に1を加え,最初が順序であれば深く検索しない.

#include<iostream>

using namespace std;

int n,result,data[5];

bool isorder()
{
	for (int i=0;i<n-1;i++)
		if (data[i]>data[i+1])
			return false;
	return true;
}
void dfs()
{
	int tmp,i;
	if (isorder())
		result++;
	else
	{
		for(i=0;i<n-1;i++)
		{
			if (data[i]>data[i+1])
			{
				tmp=data[i];data[i]=data[i+1];data[i+1]=tmp;
				dfs();
				tmp=data[i];data[i]=data[i+1];data[i+1]=tmp;
			}
		}
	}

}
int main()
{
	int col=0;
	while (cin>>n&&n)
	{
		col++;
		for (int i=0;i<n;i++)
			cin>>data[i];
		result=0;
		if (!isorder())
			dfs();
		cout<<"There are "<<result<<" swap maps for input data set "<<col<<"."<<endl;

	}
	return 0;
}