1、实验内容

输入2-20个大于0的正整数（1、2、3或者100、200、300），输入0作为结束，0不参与排列。按题目要求规则输出全排列。

1. 实验步骤

Ⅰ首先观察题目的测试样例，发现有以下特点：

①不需要对输入数据进行排序。

②输出不需要按字典序，即递归时，不需要确保输出顺序，不用dfs算法。

③发现递归设计时，只需要考虑元素的交换即可。

Ⅱ然后基于以上要求，构思设计程序算法：

我们观察最基础的样例 输入为1、2、3；

观察输出：1 2 3；1 3 2；2 1 3；2 3 1；3 1 2；3 2 1；

可以发现都是按顺序，先输出1开头的（前两个），再输出2开头的（中间两个），最后是3开头的（最后两个）；然后以1开头的，剩下的数字按顺序是2、3；所以先输出2、3；再输出3、2；以2或3开头的可同理分析。我们发现，只需要按照输入顺序，把第一个数字和每一个都交换一次，当与最后一个数字交换结束后，就可以开始输出了。这就是递归设计中最根本的一环，子问题可以按相同思路求解。

Ⅲ最后，我们按规定的输出格式写出程序，编写printPerm方法输出全排列。首先写递归出口，也就是左边n==右边m的时候，输出数组的值；如果n!=m，此时要从左边m开始，用for循环依次和左边的值m交换，然后递归调用printPerm方法，最后不要忘了把交换的元素换回去。至此程序编写结束。

Ⅳ通过运行测试，程序符合要求。提交通过。

结论分析与体会：

递归的设计十分巧妙，也是编程较为困难和复杂的部分。需要从复杂的现象中抽出最一般的本质。需要考虑把整个问题化解为几个相同的子问题，而且子问题可以嵌套，符合这种条件的问题求解可以考虑递归的思路。

设计递归时，不要忘记考虑题目的输出规则，要按照要求的逻辑去分析问题。

若设计技能还需要加强训练，可以补做实验一，求子集的题目。

#include<bits/stdc++.h>
using namespace std;


void change(int * in,int x,int y)
{
	int temp = in[x];
	in[x] = in[y];
	in[y] = temp;
}

void printPerm(int *input,int totalnumber,int m,int n)
{
	if(m == n)
	{
		for(int i=0;i<totalnumber-1;i++)
		{
			cout<<input[i]<<",";
		}
		cout<<input[totalnumber-1];
		cout<<endl;
	}
	else
	{
		for(int i=m;i<n+1;i++)
		{
			change(input,m,i);
			printPerm(input,totalnumber,m+1,n);
			change(input,m,i);
		}
	}
}

int main()
{
	cout<<"Input"<<endl;
	int count = 0;int inputint=0;int input[21];
	while(cin>>inputint && inputint!=0){
		input[count++] = inputint;
	}
	cout<<"Output"<<endl;
	printPerm(input,count,0,count-1);
	cout<<"End0";
	return 0;
}