java全排列

Question

求一个值得推敲的JAVA全排列算法.
希望不要网上直接粘贴过来.因为我希望大家能给代码的同时教会我怎么
自己理解这个代码,自己能够写出全排列.
==== 希望大家给代码时候,能尽可能耐心的给我讲下全排列实现的思路.每次发100分..分不够了见谅.

Answer 1

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 2

源由： 
將一組數字、字母或符號進行排列，以得到不同的組合順序，例如1 2 3這三個數的排列組合有：1 2 3、1 3 2、2 1 3、2 3 1、3 1 2、3 2 1。  解法： 
排列組合的解法依產生的組合順序，可以分為兩種：一種具有字典順序，一種不具有字典順序，所謂字典順序是指照數字或字母順序來排列，例如ABCD、ABDC、ACBD........，上例的組合順序也是具有字典順序。 無論是字典或非字典順序的排列組合解法，都可以使用遞迴將問題切割為較小的單元進行排列組合，例如1 2 3 4的排列可以分為1 [2 3 4]、2 [1 3 4]、3 [1 2 4]、4 [1 2 3]進行排列。 不具字典順序的排列組合產生比較容易，使用一軸心將數字分為兩個部份，並將軸心左邊與右邊的數字依序交換，並繼續將軸心右邊進行遞迴，例如遞迴最上層的四個交換如下，!表示軸心： 
[1] ! 2 3 4 - > 將軸心右邊進行遞迴 
2 ! [1] 3 4 - > 將軸心右邊進行遞迴 
3 ! 2 [1] 4 - > 將軸心右邊進行遞迴 
4 ! 2 3 [1] - > 將軸心右邊進行遞迴 具有字典順序的排列組合則利用旋轉法，先將旋轉間隔設為0，將最右邊的數字旋轉至最左邊，並逐步增加旋轉的間隔，例如： 
1 2 3 4 -> 旋轉1 -> 繼續將右邊2 3 4進行遞迴處理 
2 1 3 4 -> 旋轉1 2 變為 2 1-> 繼續將右邊1 3 4進行遞迴處理 
3 1 2 4 -> 旋轉1 2 3變為 3 1 2 -> 繼續將右邊1 2 4進行遞迴處理 
4 1 2 3 -> 旋轉1 2 3 4變為4 1 2 3 -> 繼續將右邊1 2 3進行遞迴處理 以上僅解釋遞迴時最上層的部份，您可以將右邊的部份繼續使用遞迴畫出遞迴樹並輸出結果，並配合以下的實作來瞭解演算的過程：  C程式實作（非字典順序）： 
代碼: 
#include <stdio.h> 
#include <stdlib.h> 
#define N 4 
#define SWAP(x,y) {int t; t = x; x = y; y = t;} void perm(int*, int); int main(void) { 
    int num[N+1], i;     for(i = 1; i <= N; i++) 
        num[i] = i;     perm(num, 1);     return 0; 
} void perm(int* num, int i) { 
    int j;     if(i < N) { 
        for(j = i; j <= N; j++) { 
            SWAP(num[i],num[j]);  // 依序交換兩數 
            perm(num, i+1); 
            SWAP(num[i],num[j]); 
        } 
    } 
    else {  // 顯示此次排列 
        for(j = 1; j <= N; j++) 
            printf("%d ", num[j]); 
        printf("\n"); 
    } 
} 
 C程式實作（字典順序）： 
代碼: 
#include <stdio.h> 
#include <stdlib.h> 
#define N 4 void perm(int*, int); int main(void) { 
    int num[N+1], i;     for(i = 1; i <= N; i++) 
        num[i] = i;     perm(num, 1);     return 0; 
} void perm(int* num, int i) { 
    int j, k, tmp;     if(i < N) { 
        for(j = i; j <= N; j++) { 
            tmp = num[j]; 
            for(k = j; k > i; k--) // 旋轉該區段最右邊數字至最左邊 
                num[k] = num[k-1]; 
            num[i] = tmp;             perm(num, i+1);             // 還原 
            for(k = i; k < j; k++) 
                num[k] = num[k+1]; 
            num[j] = tmp; 
        } 
    } 
    else {  // 顯示此次排列 
        for(j = 1; j <= N; j++) 
            printf("%d ", num[j]); 
        printf("\n"); 
    } 
}  

Answer 3

justinavril#1
如果有耐心 希望你能把你的思路剖析下.授人以鱼不如授人以渔...谢谢了

Answer 4

这是一个递归算法，start和end游标控制你要进行递归的位置。我就解释下for循环里的每一句吧：
for(int i=start;i<=end;i++){//从第一个你要全排列的数开始遍历数组，称该元素为起点吧  
                char temp=buf[start];//将起点存到temp变量中  
                  buf[start]=buf[i];//将起点赋值为之后那个元素  
                buf[i]=temp; //起点之后的元素赋值为temp，也就是起点。这样就完成了起点和起点之后元素的交换 
                  
                perm(buf,start+1,end);//从起点之后，递归数组
                  
                temp=buf[start];//将交换后的数组还原  
                buf[start]=buf[i];  
                buf[i]=temp;  
            }  

Answer 5

我想问下这个递归和for循环的运行顺序
比如第一次初始化perm(buf,0,buf.length-1);  
那么下面的for循环就为
for(int i = 0; i <=2; i++){
// 这里进行一次交换(略)
perm(buf,start+1,end);//从起点之后，递归数组.那么这一递归 
//就又重新执行函数了.也就是每次for循环虽然<=2但也就执行了一次
//这样怎么进行的全排列
}

Answer 6

比如我开始start是0，end是数组的最后一位，是5，那么第一次执行时，是perm(buf, 0, 5)，然后交换元素0和元素1，此时执行perm(buf, 0+1, 5)，这个方法里，交换元素1和2（因为start是0+1，也就是1了），然后依次循环下去

Answer 7

其它的排列求法就不贴了.贪多无益。只弄会一个就可以了.n个数据求全排列，递归的思路好多个吧。猴子给的算法算其中的一种。这种递归的思路是：分别求第i个数据排在第一位的时，其它n-1个数据的全排列。求n-1个数据的全排列与求n个数据的全排列求法相同。当只有一个数据时，是递归的出口。

Answer 8

但现在主要是 我没理解 怎么实现的全排列 大伙能不能用 a,b,c这3个数 把那个代码的解析流程给说下

Answer 9

java中有排序方法sorf()自己按首字母顺序数字从小到大

Answer 10

import java.util.ArrayList;   
import java.util.Arrays;   
import java.util.List;   
public class FullSort {   
    //将NUM设置为待排列数组的长度即实现全排列   
    private static int NUM = 3;   
  
    /**  
     * 递归算法：将数据分为两部分，递归将数据从左侧移右侧实现全排列  
     *  
     * @param datas  
     * @param target  
     */  
 
    private static void sort(List datas, List target) {   
        if (target.size() == NUM) {   
            for (Object obj : target)   
                System.out.print(obj);   
            System.out.println();   
            return;   
        }   
        for (int i = 0; i < datas.size(); i++) {   
            List newDatas = new ArrayList(datas);   
            List newTarget = new ArrayList(target);   
            newTarget.add(newDatas.get(i));   
            newDatas.remove(i);   
            sort(newDatas, newTarget);   
        }   
    }   
  
    public static void main(String[] args) {   
        String[] datas = new String[] { "a", "b", "c", "d" };   
        sort(Arrays.asList(datas), new ArrayList());   
    }   
  
}  

Answer 11

    我在做吸血鬼数字的时候，中间用到了全排列的方法。我写的全排列跟1楼的思路一样，排列总数也是对的，但是存在重复的情况。不过，字典序好像就没有重复。
     其实，整数1~n的全排列跟N皇后问题完全一样。不是1~n的整数问题(即字母全排列或非严格的1~n整数)也可以化为1~n进行间接处理。

Answer 12

楼主比我还笨，哈哈，我都看懂了，开心啊~~~
package javabasicgrammar;import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;// 1.================================================================
// 排列组合数字
public class Permutation {
// 方法一
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;
buf[i] = buf[start]; // 将交换后的数组还原
buf[start] = temp;
}
}
} // 方法二
// 可以使用递回将问题切割为较小的单元进行排列组合，例如1 2 3 4的排列可以分为
// 1 [2 3 4],2[1 3 4],3[1 2 4],4[1 2 3]进行排列，利用旋转法，先将旋转间隔设为0，
// 将最右边的数字旋转至最左边，并逐步增加旋转的间隔，例如
// 1 2 3 4 --> 旋转1 --> 继续将右边2 3 4进行递回处理
// 2 1 3 4 --> 旋转1 2 变为 2 1 --> 继续将右边1 3 4 进行递回处理
// 3 1 2 4 --> 旋转1 2 3变为3 1 2 --> 继续将右边1 2 4进行递回处理
// 4 1 2 3 --> 旋转1 2 3 4 变为4 1 2 3 --> 继续将右边1 2 3 进行递回处理
public static void perm(int[] num, int i) { // i为第几层
if (i < num.length) { // 小于总层就旋转,旋转间隔从0开始
for (int j = i; j < num.length; j++) {
int tmp = num[j];
// 旋转该区段最右边的数字到最左边
for (int k = j; k > i; k--) {
num[k] = num[k - 1];
}
num[i] = tmp; perm(num, i + 1); // 还原
for (int k = i; k < j; k++) {
num[k] = num[k + 1];
}
num[j] = tmp;
}
} else { // 最后一层的时候打印
// 显示此次排序
for (int j = 0; j < num.length; j++) {
System.out.print(num[j] + " ");
}
System.out.println();
}
} // 方法三
private static void sort(List datas, List target) {
if (target.size() == 3) { // 这个3表示要对几个字符进行全排列
for (Object obj : target)
System.out.print(obj);
System.out.println();
return;
}
for (int i = 0; i < datas.size(); i++) {
List newDatas = new ArrayList(datas);
List newTarget = new ArrayList(target);
newTarget.add(newDatas.get(i));
newDatas.remove(i);
sort(newDatas, newTarget);
}
} public static void main(String[] args) {
// ==========================================
// int[] num = new int[4 + 1];
// for (int j = 1; j <= num.length - 1; j++) {
// num[j] = j;
// }
// perm(num, 1);
int[] num = { 1, 2, 3 };
perm(num, 0);
// ==========================================
System.out.println();
char buf[] = { 'a', 'b', 'c' };
perm(buf, 0, buf.length - 1);
// ==========================================
System.out.println();
String[] datas = new String[] { "a", "b", "c" };
sort(Arrays.asList(datas), new ArrayList());
}
}