递归实现1-n的全排列(JAVA语言)

思路：

For example：

123的全排列=

1在最前面 23的全排列

2在最前面 13的全排列

3最前面 12的全排列

所以只需交换和最前面元素的位置，生成剩余元素的全排列即可。

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		// TODO Auto-generated method stub

		Scanner in=new Scanner(System.in);

		int n=in.nextInt();

		int a[]=new int[n];

		for(int i=1;i<=n;i++) {

			a[i-1]=i;

		}

		dfs(a,0,n-1);

	}

	private static void dfs(int a[],int s,int e) {

		if(s==e) {

			for(int i=0;i<a.length;i++)

				System.out.print(a[i]+" ");

			System.out.println();

		}

		else

			for(int i=s;i<=e;i++) {

				swap(a,s,i);

				dfs(a,s+1,e);

				swap(a,s,i);

			}

	}

	private static void swap(int[] a, int s2, int i) {

		// TODO Auto-generated method stub

		int t=a[s2];

		a[s2]=a[i];

		a[i]=t;

	}

}

巴特西

递归实现1-n的全排列(JAVA语言)

最新文章

热门文章