Java全排列算法

解法一

public class Arrange {

	public static void main(String[] args) 
	{
		int[] a = {1,2,3,4};
		arrange(a,0,a.length);
	}
	
	//交換
	public static void swap(int a[],int i,int j)
	{
		int temp = a[i];
		a[i] = a[j];
		a[j] = temp;
	}
	//全排列
	public static void arrange(int a[],int index,int length)
	{
		if(index>=length-1)
		{
			output(a);//如果到達數組最後一個元素，則輸出數組
		}
		else
		{
			for(int i = index;i<length;i++)
			{
				swap(a,index,i);
				arrange(a,index+1,length);//遞歸
				swap(a,index,i);
			}
		}
	}
	//輸出數組
	public static void output(int a[])
	{
		for(int i=0;i<a.length;i++)
		{
			System.out.print(a[i]+" ");
		}
		System.out.println("");
	}

}
           

解法二

public class DfsArrange {

	public static int[] visit = new int[3];
	public static int[] array = new int[3];
	public static void main(String[] args) {
		dfs(0);
	}
	
	public static void dfs(int index)
	{
		if(index>=array.length)
		{
			outputArray(array);
		}
		else
		{
			for(int i = 0;i<array.length;i++)
			{
				if(visit[i]!=1)
				{
					visit[i] = 1;
					array[index] = i;
					dfs(index+1);
					visit[i] = 0;
				}
			}
		}
	}
	//輸出數組
	public static void outputArray(int[]array)
	{
		for(int a:array){
			System.out.print(a+" ");
		}
		System.out.println("");
	}

}