n个元素{1,2,……,n}有n!个不同的排列。将这n!个排列按字典序列排列。并编号为0,1,……,n!-1。每个排列的编号为其字典序的值。例如,当n=3是,其字典排序为:123,132,213,231,312,321,这6个数的字典序值分别为0,1,2,3,4,5。现给定任意n,输出字典序为k的排列(0<=k<=n!-1)。
可以采用递归或者非递归方法
public class Zuhe {
public static void zuhe(char[] A, int begin, int
n,StringBuffer sb) {
if(n==0) { System.out.println(sb+"
"); return; }
if(begin==A.length) {
return; } //包含
sb.append(A[begin]); zuhe(A,begin+1,n-1,sb);
sb.deleteCharAt(sb.length()-1); //不包含
zuhe(A,begin+1,n,sb);
} public static void main(String[] args) {
String s="abc"; char []
A=s.toCharArray(); StringBuffer sb=new StringBuffer();
int n=A.length; for(int i=1;i<=n;i++) {
zuhe(A,0,i,sb); } }
}
非递归
public class Feidigyi{
public static void Combine(char[] c) {
if(c==null) return ; int len=c.length;
boolean used[]=new boolean[len]; char cache[]=new
char[len]; int result=len; while(true) { int
index=0; while(used[index]) {
used[index]=false; ++result; if(++index==len)
return; } used[index]=true;
cache[--result]=c[index]; System.out.print(new
String(cache).substring(result)+" ");
}
}
public static void main(String[] args) { String
s="abcd"; char[] c=s.toCharArray();
Combine(c); }
}