谁能给个全排列的算法

Question

尽量高效，代码易读些的。要加上详细的注释和原理的阐述。谢谢。我想用递归实现不难，但还有点小bug，基本思想是：S(abc)=aS(bc)+bS(ac)+cS(ab)这样的递归，S(bc)是指b 、c的全排列。

Answer 1

import java.util.LinkedHashSet;
　　import java.util.Set;
　　public class Permutation { 
　　private static Set<String> set = new LinkedHashSet<String>();
　　private static void perm(int[] arr, int k, int m) {
　　if (k == m) {//递归
　　StringBuffer sb = new StringBuffer();
　　for (int i = 0; i <= m; i++)
　　sb.append(arr[i]);
　　set.add(sb.toString());
　　} else {
　　for (int i = k; i <= m; i++) {
　　arr[k] = (arr[k] + arr[i]) - (arr[i] = arr[k]); //交换arr[k] <-> arr[i]
　　perm(arr, k + 1, m);
　　arr[k] = (arr[k] + arr[i]) - (arr[i] = arr[k]); //交换arr[k] <-> arr[i]
　　}
　　}
　　}
　　public static String[] getPerm(int[] arr, int k, int m) {
　　perm(arr, k, m);
　　return set.toArray(new String[set.size()]);
　　}
　　public static void main(String[] args) {
　　int[] test = { 1, 2, 3 };
　　String[] perms = getPerm(test, 0, test.length - 1);
　　for (String s : perms)
　　System.out.println(s);
　　}
　　}抄的

Answer 2

应该没问题啊，sabc求以s开头，abc的全排列，递归调用，求以a开头bc的全排列，递归求以b开头c的全排列和以c开头B的全排列

Answer 3

第一种，看我的博客上的。
第二种。http://topic.csdn.net/u/20090828/11/ffe01c94-e190-42dc-8ddc-1de0738c350d.html?57546我在32楼上的回复。
第三种。
也是以前回复一个贴子中的算法，算法是别人给的，我写的代码：
import java.util.*;
/*将一个排列看作一个长整数，则所有排列对应着一组整数。
* 将这组整数按从小到大的顺序排列排成一个整数，从对应最小的整数开始。
* 按数列的递增顺序逐一列举每个排列对应的每个整数，这能更有效地完成排列的穷举。
* 从一个排列找出对应数列的下一个排列可在当前排列的基础上作部分调整来实现。
* 倘若当前排列为1，2，4，6，5，3，并令其对应的长整数为124653。
* 要寻找比长整数124653更大的排列，可从该排列的最后一个数字顺序向前逐位考察，
* 当发现排列中的某个数字比它前一个数字大时，如本例中的6比它的前一位数字4大，
* 这说明还有对应更大整数的排列。但为了顺序从小到大列举出所有的排列，
* 不能立即调整得太大，如本例中将数字6与数字4交换得到的排列126453就不是排列124653的下一个排列。
* 为了得到排列124653的下一个排列，应从已经考察过的那部分数字中选出比数字大，
* 但又是它们中最小的那一个数字，比如数字5，与数字4交换。
* 该数字也是从后向前考察过程中第一个比4大的数字。
* 5与4交换后，得到排列125643。在前面数字1，2，5固定的情况下，还应选择对应最小整数的那个排列，
* 为此还需将后面那部分数字的排列顺序颠倒，如将数字6，4，3的排列顺序颠倒，
* 得到排列1，2，5，3，4，6，这才是排列1，2，4，6，5，3的下一个排列。
*//**类Pernutation 可以构造从1~n的数字的全排序。
*
*/
class Permutation{
private int len;
private ArrayList<String> resultList=new ArrayList<String>();

/**构造方法,n表示要要构造的全排序是数字1~n的全排列。
*/
Permutation(int n){
len=n;
generate();
}
/**产生全排列的方法，完全按楼主的算法描述来的
*  由于要交换好多元素，所以大部分操作都在一个int数组numList上进行。
*  每一种结果，再转为一个字符串，加到resultList中。
*/
private void generate(int no){ int[] numList=new int[len];
for(int i=1; i<=len; i++){
numList[i-1]=i;
}
boolean isFinish=false;
resultList.add(intArrayToString(numList));   //add this line . while(!isFinish){
int index=numList.length-1;
while(index>0&&numList[index-1]>numList[index]){
index--;
}
if(index==0){
isFinish=true;
//resultList.add(intArrayToString(numList)); //delete this line.
continue;
}
index--;
int tempIndex=index+1;
while(tempIndex<len&&numList[tempIndex]>numList[index]){
tempIndex++;
} 
int temp=numList[index];
numList[index]=numList[tempIndex-1];
numList[tempIndex-1]=temp;
reverse(numList,index+1);
resultList.add(intArrayToString(numList)); if(count==no){
System.out.println(intArrayToString(numList));
}
}
}

//把int数组arr，从start开始以后的元素反转。
//
private void reverse(int[] arr,int start){
int temp=0;
for(int i=start,j=arr.length-1;i<j;i++,j--){
temp=arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
}

//把一个int数组arr转为字符串返回。
//
private String intArrayToString(int[] arr){
StringBuilder sb=new StringBuilder();
for(int i : arr){
sb.append(i);
}
return sb.toString();
}

/**把全排列返回。
*/
public String toString(){
return ""+resultList;
}

/**返回全排列的数目。
*/
public long numberOf(){
return resultList.size();
}

/**返加全排列。
*/
public ArrayList<String> getPernutation(){
return resultList;
}

public static void main(String[] args){
Permutation p=new Permutation(7);
System.out.println(p);
System.out.println("共有"+p.numberOf()+"种排列");

}}这三种算法都是非递归的，第一种实用性强，第二，三种只适用于数字，但可以改为其它字符（比如先排出数字的来，再替换为字符，或者把数字做为字符数据的下标，或者把数字和字符映射起来等。）

Answer 4

网上很多啊public class SubString {
public static void listAllSequence(String str) {
   char[] chs = str.toCharArray();
   int len = str.length();
   listAll(chs, 0, len - 1);
} private static void listAll(char[] c, int p, int r) {
   if (p >= r) {
    for (char i : c)
     System.out.print(i);
    System.out.println();
   } else {
    for (int i = p; i <= r; i++) {
     char temp = c[p];
     c[p] = c[i];
     c[i] = temp;
     listAll(c, p + 1, r);
     c[i] = c[p];
     c[p] = temp;
    }
   }
} public static void main(String[] args) {
   listAllSequence("sample");
}}

Answer 5

http://blog.csdn.net/bigbug9002/archive/2009/07/24/4377889.aspx我博客上的这种效率应该是非常高的了。

Answer 6

四楼的代码，把
             if(count==no){
                System.out.println(intArrayToString(numList));
            }
这几行，和参数int no去掉。原来是为了求第no个排序设的，没有用了。

Answer 7

public class SubString {
    public static void listAllSequence(String str) {
       char[] chs = str.toCharArray();
       int len = str.length();
       listAll(chs, 0, len - 1);
    }    private static void listAll(char[] c, int p, int r) {
       if (p >= r) {
            for (char i : c)
                System.out.print(i);
            System.out.println();
       } else {
            for (int i = p; i <= r; i++) {
                 char temp = c[p];
                 c[p] = c[i];
                 c[i] = temp;
                 listAll(c, p + 1, r);
                 c[i] = c[p];
                 c[p] = temp;
            }
       }
    }    public static void main(String[] args) {
       listAllSequence("sample");
    }}希望对楼主有用

Answer 8

参考这个看看，以前总结的
JAVA里实现一个数组全排列的方法，就是获得数组的所有排列顺序

Answer 9

我自己写的递归也调通了，效率还可以，10个字母，300多W组合，不到2秒。各位写的高效率的，我有时间再拜读。public class MyVersion {
    private static int count;
    public static void main(String[] args) {
        String str="abcdefghij";
        fullSort(str,"");
        System.out.println("count = "+count);
    }    public static void fullSort(String toSort,String  prefix){
      if (toSort.length()==2){
          System.out.println(prefix.toString().concat(toSort.charAt(0)+"").concat(toSort.charAt(1)+""));  
          System.out.println(prefix.toString().concat(toSort.charAt(1)+"").concat(toSort.charAt(0)+""));
          count+=2;
          return;
      }        for (int i = 0; i < toSort.length(); i++) {
            String left="";
            if (i==0){
                left=toSort.substring(1);
            } else if (i==toSort.length()-1){
                left=toSort.substring(0,toSort.length()-1);
            }else{
                left=toSort.substring(0,i)+toSort.substring(i+1);
            }            fullSort(left, prefix.concat(toSort.charAt(i)+""));
      }
    }
}

Answer 10

public class AllSort{  
    public static void main(String[] args) {  
        char buf[]={'a','b','c'};          perm(buf,0,buf.length-1);  
    }  
    public static void perm(char[] buf,int start,int end){  
        if(start==end){//当只要求对数组中一个字母进行全排列时，只要就按该数组输出即可  
            for(int i=0;i<=end;i++){  
                System.out.print(buf[i]);  
            }  
            System.out.println();     
        }  
        else{//多个字母全排列  
            for(int i=start;i<=end;i++){  
                char temp=buf[start];//交换数组第一个元素与后续的元素  
                buf[start]=buf[i];  
                buf[i]=temp;  
                  
                perm(buf,start+1,end);//后续元素递归全排列  
                  
                temp=buf[start];//将交换后的数组还原  
                buf[start]=buf[i];  
                buf[i]=temp;  
            }  
        }  
    }  
}本文来自CSDN博客，转载请标明出处：http://blog.csdn.net/justinavril/archive/2008/08/02/2758636.aspx

Answer 11

你这个程序是我见过 的创建对象最少，最简练的程序了，你能讲讲原理是什么吗，授人以鱼不如授人以渔。贴出来。import java.util.Arrays;   
  
/**  
 * 获得数组全排列的一个实现算法  
 *   
 * @author 老紫竹的家(laozizhu.com)  
 *   
 */   
public class Test {   
  static String[] array = { "x", "y", "z" };   
  
  public static void main(String[] args) {   
    getAllOrder(0, array.length - 1);   
  }   
  
  public static void getAllOrder(int begin, int end) {   
    if (begin == end) {   
      check();   
    } else {   
      for (int i = begin; i <= end; i++) {   
        // 交换数据   
        swap(begin, i);   
        getAllOrder(begin + 1, end);   
        swap(i, begin);   
      }   
    }   
  }   
  
  public static void swap(int from, int to) {   
    // 这里应该加上各种防止无效交换的情况   
    // 比如位置相同，或者2个位置的数据相同   
    if (from == to) {   
      return;   
    }   
    String tmp = array[from];   
    array[from] = array[to];   
    array[to] = tmp;   
  }   
  
  public static void check() {   
    // 排列拿到了，可以进行你的判断了。   
    System.out.println(Arrays.toString(array));   
  }   
}  

Answer 12

你好，你博客上的程序，我用10个字母来全排列的时候：java.lang.OutOfMemoryError: Java heap space了。
而且，没怎么看懂原理。

Answer 13

是第30行：myList.add(new String(strChars));
这个造成的，你把原理讲讲可以吗？
下面的基本看不懂了：
在上一个模式中，容易发现，其交换下标k的序列为（设其下标是从左到右，而且从1开始）：          3 2 1 3 1 2 3 1 3 2 1 3 1 2 3 1 3 2 1 3 1 2 3      容易看到：对元素个数为n的集合S，其交换下标k的序列有如下规律：      1）：开始时从n-1减少1
      2）：当减少到1或增加到n-1时，k值发生突变：若前一个k是1，则变为n-1；若前一个k为n-1，则变为1。
      3）：k值突变后，发生反向增长，即：下一次k的增长规律反向。
      4）：k值突变后的交换下标的序列是突变后前的序列关于突变位置的”镜像“
                如前7个交换下标：3 2 1  3 1 2 3  加粗的位置为突变位置，显然，突变位置后的1 2 3是突变前的3 2 1"镜像"

Answer 14

如果之前的能看懂,原理基本就可以知道了.                1234    1324   3124   3214   2314   2134
                1243    1342   3142   3241   2341   2143
                1423    1432   3412   3421   2431   2413
                4123    4132   4312   4321   4231   4213看这个的时候，要从第一列开始，从上到下，第二列，从下到上，第三列，从上到下，，，，3 2 1   3   1 2 3   1    3 2 1   3   1 2 3   1   3 2 1    3    1 2 3 
这一串数字，就是上面的序列中，前一个序列变为后一个序列时，交换位置的规律。
3表示把1234-->1243时要把34交换。
2表示把1243-->1423时要把24交换
1表示把1423-->4123时要把14交换
3表示把4123-->4132时要把23交换
1表示把4132-->1432时要把14交换
2表示把1432-->1342时要把43交换
3表示把1342-->1324时要把42交换
1表示把1324-->3124时要把13交换
3表示把3124-->3142时要把24交换。
。