将一个排列看作一个长整数，则所有排列对应着一组整数。将这组整数按从小到大的顺序排列排成一个整数，从对应最小的整数开始。按数列的递增顺序逐一列举每个排列对应的每个整数，这能更有效地完成排列的穷举。从一个排列找出对应数列的下一个排列可在当前排列的基础上作部分调整来实现。倘若当前排列为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的下一个排列。如何编程啊？c++的算法我是看明白了，可是我自己写的java的代码老是不对。
/*将一个排列看作一个长整数，则所有排列对应着一组整数。
* 将这组整数按从小到大的顺序排列排成一个整数，从对应最小的整数开始。
* 按数列的递增顺序逐一列举每个排列对应的每个整数，这能更有效地完成排列的穷举。
* 从一个排列找出对应数列的下一个排列可在当前排列的基础上作部分调整来实现。
* 倘若当前排列为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[] numList=new int[len];
for(int i=1; i<=len; i++){
numList[i-1]=i;
}
boolean isFinish=false;
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));
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));
}
}
//把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(5);
System.out.println(p);
System.out.println("共有"+p.numberOf()+"种排列");
}
}F:\java>java Permutation
[12354, 12435, 12453, 12534, 12543, 13245, 13254, 13425, 13452, 13524, 13542, 14235, 14253, 14325, 1
4352, 14523, 14532, 15234, 15243, 15324, 15342, 15423, 15432, 21345, 21354, 21435, 21453, 21534, 215
43, 23145, 23154, 23415, 23451, 23514, 23541, 24135, 24153, 24315, 24351, 24513, 24531, 25134, 25143
, 25314, 25341, 25413, 25431, 31245, 31254, 31425, 31452, 31524, 31542, 32145, 32154, 32415, 32451,
32514, 32541, 34125, 34152, 34215, 34251, 34512, 34521, 35124, 35142, 35214, 35241, 35412, 35421, 41
235, 41253, 41325, 41352, 41523, 41532, 42135, 42153, 42315, 42351, 42513, 42531, 43125, 43152, 4321
5, 43251, 43512, 43521, 45123, 45132, 45213, 45231, 45312, 45321, 51234, 51243, 51324, 51342, 51423,
51432, 52134, 52143, 52314, 52341, 52413, 52431, 53124, 53142, 53214, 53241, 53412, 53421, 54123, 5
4132, 54213, 54231, 54312, 54321, 54321]
共有120种排列
最后一个结果和前面的一个重复了,而第一个12345没有加进去.
5!是正确的结果.我一看是120就以为是正确了.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[] 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));
}
}
//把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(5);
System.out.println(p);
System.out.println("共有"+p.numberOf()+"种排列");
}
}