// 全排列问题.cpp : 定义控制台应用程序的入口点。

//

#include "stdafx.h"

#include <iostream>

using namespace std;

template<class T>

void swap(T *str1,T *str2)

{

	T temp;

	temp=*str1;

	*str1=*str2;

	*str2=temp;

}

void permStr(char *str,int i)//字符串的全排列

{

	//printf("%d",i);

	if(i==strlen(str)-1)

		printf("%s\n",str);

	else

	{

		for(int j=i;j<strlen(str);j++)

		{

			//printf("i %d,j %d",i,j);

			swap(&str[i],&str[j]);

			permStr(str,i+1);

			swap(&str[i],&str[j]);

		}

	}

}

void permInt(int a[],int n, int k)//数组全排列

{

	if (k== n-1)

	{

		for (int i = 0; i < n; i ++)

			cout<<a[i]<<" ";

		cout<<endl;

	}

	else

	{

		for (int j = k; j < n; j ++)

		{

			swap(&a[j],&a[k]);

			permInt(a,n,k+1);

			swap(&a[j],&a[k]);

		}

	}

}

/*另外一个问题方法相似，一个数由1-9这10个数字组成。前i个数组成的数能被i整除*/

bool used[10];

void dfs(int a, int k)

{

	if (k && (a%k) !=0)

		return;

	if (k==9)

	{

		cout<<a<<" ";

		return;

	}

	else

	{

		for (int i = 1; i <= 9; i ++)

		{

			if (!used[i])

			{

				used[i] = 1;

				dfs(a*10+i,k+1);

				used[i] = 0;

			}

		}

	}

}

int main()

{

	char str[]={"abc"};

	permStr(str,0);

	int a[]={1,2,3};

	permInt(a,3,0);

	dfs(0,0);

	return 0;

}