Java 全排列输出

java实现全排列输出

最近在找工作，面试java程序员或者软件工程师，在笔试的时候常常见到这么一道题：全排列的输出数组（常常要求是整数），其实这道题不难，主要是递归调用，在baidu或者google上已经有很多人提出了解法，但是大部分可读性很差，让我们莘莘学子根本就记不住。我来简单的说一下：

其实这个问题的解法基本思路是这样的：递归

但是我们在使用递归的时候要注意结束条件，也就是递归到最后，要推出递归方法，目前网上的主要思路如下：

 

public 递归方法（参数列表）{
      if(列表的元素只有两个){
           输出：“元素一元素二”
       输出：“元素二元素一”
    }else{
       //此时元素有两个以上，这时候要使用递归
        递归方法（参数列表）//使用递归方法将元素细分
    }
}

 

我这个思路是在百度上看到的，但是具体链接和源代码我再没找到，因为那个代码很乱……Sorry！

我在Eclipse实现了这个思路，代码如下：

import java.util.LinkedList;
import java.util.List;


public class ListAllPrint {
	/**
	 * 使用createList方法，填充参数列表传递过来的List，默认是Integer,一般是这个类型，你可以修改别的类型
	 */
	public void createList(int n,List list){
		if(n==0){//当是n=0是，默认就是3了
			n=3;
		}
		for(int i=1;i<=n;i++){//for循环填充list
			list.add(i);
		}
	}
	/**
	 * printAll是输出全排列的递归调用方法，list是传入的list，用LinkedList实现，而prefix用于转载以及输出的数据
	 */
	public void printAll(List candidate, String prefix){
		if(candidate.size()==1){
			//一个元素时候，输出……；不过这个实现，这个if传递不到递归中，仅仅是测试代码中list的size为1时调用一次
			 System.out.println(candidate.get(0));
		}
		if(candidate.size()==2){
			//输出两个元素时候,颠倒顺序
			 System.out.println(prefix+candidate.get(0)+candidate.get(1));
			 System.out.println(prefix+candidate.get(1)+candidate.get(0));
		}else{
			for (int i = 0; i < candidate.size(); i++) {
				 List temp = new LinkedList(candidate);
				 printAll(temp, prefix + temp.remove(i));//递归调用
			}
		}
	}

	/**
	 * 测试代码
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		LinkedList<Integer> list=new LinkedList<Integer>();
		ListAllPrint lap=new ListAllPrint();
		lap.createList(3, list);
		lap.printAll(list,"");
	}
}

 

我在编写这个程序的时候，发现自己要写一个

 

if(candidate.size()==1){
			//一个元素时候，输出……；不过这个实现，这个if传递不到递归中，仅仅是测试代码中list的size为1时调用一次
			 System.out.println(candidate.get(0));
		}

 语句，用来当list初始就为size就为1时使用。我觉得这个效率很差，不仅每次递归也判断，而且不符合递归的思想：递归到最后应该是一个元素（查找算法递归实现最后是一个元素的判断）

所以，我又添加了一个参数在递归的方法中，用来记录原list的长度，使得每次的排列字符串输出可以完全记载到第二个参数prefix，不使用2，而是使用length来判断是否加最后一个元素入prefix，从而结束输出，从而使代码显得漂亮多了。修改如下：

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;


public class ListAllPrint2 {
	/**
	 * 使用createList方法，填充参数列表传递过来的List，默认是Integer,一般是这个类型，你可以修改别的类型
	 */
	public void createList(int n,List list){
		if(n==0){
			n=3;
		}
		for(int i=1;i<=n;i++){
			list.add(i);
		}
	}
	/**
	 * printAll是输出全排列的递归调用方法，list是传入的list，用LinkedList实现，
	 * 而prefix用于转载以及输出的数据
	 * length用于记载初始list的长度，用于判断程序结束。
	 */
	public void printAll(List candidate, String prefix,int length){
		if(prefix.length()==length)
			 System.out.println(prefix);
		for (int i = 0; i < candidate.size(); i++) {
			 List temp = new LinkedList(candidate);
			 printAll(temp, prefix + temp.remove(i),length);
		}
	}

	/**
	 * 测试代码
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		ArrayList<Integer> list=new ArrayList<Integer>();
		ListAllPrint2 lap=new ListAllPrint2();
		lap.createList(3, list);
		lap.printAll(list,"",list.size());
	}
}

 

这样子看上去漂亮多了！

呵呵，相关的project文件如下,这两个class都在一个项目下：

希望能对大家有所帮助！

评论

5 楼 fsead 2012-03-30  

挺不错的 研究一下

4 楼 okjesse 2010-01-23  

package test;
import java.util.Arrays;
public class ListAll {
	static String[] listMe = {"2","1","3","5","7"};
	static int listMeLen = listMe.length;
	public static void list(String insert,String[] inserted) {
		int insertedLen = inserted.length,
			tempInsertedLen = insertedLen + 1;
		String tempInserted[] = new String[tempInsertedLen];
		for (int i = 0; i < tempInsertedLen; i++) {
			System.arraycopy(inserted,0,tempInserted,0,i);
			tempInserted[i] = insert;
			System.arraycopy(inserted,i,tempInserted,i+1,tempInsertedLen - i - 1);
			if (tempInsertedLen == listMeLen)
				System.out.println(Arrays.asList(tempInserted));
			else
				list(listMe[tempInsertedLen],tempInserted);
		}
	}
	public static void main(String[] args) {
		list(listMe[1],new String[]{listMe[0]});
	}
}

照楼主思路也写了下！

3 楼 piao_bo_yi 2010-01-11  

关于全组合输出的，怎么做？？

2 楼 zxxxxz 2010-01-06  

不管有多难 也要学会

1 楼 piao_bo_yi 2009-12-10  

这题挺难的。