学步园

// 全排列问题.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;

}