我先了半天，没想出来，估计是俺太菜了，不知道哪位高人能给个用简单的数据结构实现的递归求全排列的程序。
另外我自己想了一个算法：把字符串变成对应的字符数组，然后两个for循环这个数组，交换每两个字符的位置，从而产生一个新的不一样的数组，再把这个数组传给String的构造函数，从而实现全排列的目的。import java.util.*;public class StringExchangeChar {
public static Vector exchangeChar (String str){
Vector<String> vector = new Vector<String> ();
vector.add(str);
char[] charArray = str.toCharArray();
for (int i=0; i<str.length(); i++){
for (int j=0; j<str.length(); j++){
if (i != j){
char temp = charArray[j];
charArray[j] = charArray[i];
charArray[i] = temp;
String tempString = new String (charArray);
for (int k=0; k<vector.size(); k++){
if (tempString.equals(vector.get(k))){
break;
}
else if (!(tempString.equals(vector.get(k))) && k == vector.size()-1){
vector.add(tempString);
}
}
}
}
}
return vector;
}
public static void main (String args[]){
String str = "abc";
Vector stringVector = new Vector();
stringVector = exchangeChar(str);
System.out.println("一共有"+ stringVector.size() +"种全排列。分别是：");
Iterator iterator = stringVector.iterator();
while (iterator.hasNext()){
System.out.print(iterator.next() +" ");
}
}
}
一共有5种全排列。分别是：
abc bac cab acb cba 后来看到解果，我才明白这个算法是有缺陷的。没法完全输出全排列...谁给我改进下，还是这个算法就不能实现这个功能？
另外我自己想了一个算法：把字符串变成对应的字符数组，然后两个for循环这个数组，交换每两个字符的位置，从而产生一个新的不一样的数组，再把这个数组传给String的构造函数，从而实现全排列的目的。import java.util.*;public class StringExchangeChar {
public static Vector exchangeChar (String str){
Vector<String> vector = new Vector<String> ();
vector.add(str);
char[] charArray = str.toCharArray();
for (int i=0; i<str.length(); i++){
for (int j=0; j<str.length(); j++){
if (i != j){
char temp = charArray[j];
charArray[j] = charArray[i];
charArray[i] = temp;
String tempString = new String (charArray);
for (int k=0; k<vector.size(); k++){
if (tempString.equals(vector.get(k))){
break;
}
else if (!(tempString.equals(vector.get(k))) && k == vector.size()-1){
vector.add(tempString);
}
}
}
}
}
return vector;
}
public static void main (String args[]){
String str = "abc";
Vector stringVector = new Vector();
stringVector = exchangeChar(str);
System.out.println("一共有"+ stringVector.size() +"种全排列。分别是：");
Iterator iterator = stringVector.iterator();
while (iterator.hasNext()){
System.out.print(iterator.next() +" ");
}
}
}
一共有5种全排列。分别是：
abc bac cab acb cba 后来看到解果，我才明白这个算法是有缺陷的。没法完全输出全排列...谁给我改进下，还是这个算法就不能实现这个功能？
楼主【justinavril】截止到2008-08-01 23:12:29的历史汇总数据(不包括此帖)：
发帖的总数量:11 发帖的总分数:530 每贴平均分数:48
回帖的总数量:133 得分贴总数量:36 回帖的得分率:27%
结贴的总数量:11 结贴的总分数:530
无满意结贴数:0 无满意结贴分:0
未结的帖子数:0 未结的总分数:0
结贴的百分比:100.00% 结分的百分比:100.00%
无满意结贴率:0.00 % 无满意结分率:0.00 %
敬礼!
取消马甲机器人，请点这里：http://www.java2000.net/mycsdn/robotStop.jsp?usern=justinavril
public static void main(String[] args) {
char buf[]={'a','b','c','d'};
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;
}
}
}
}
其实有个O(n)的算法 很简短 更是看不懂啊
另外我把2#的代码加了注释 应该没问题吧public class AllSort{
public static void main(String[] args) {
char buf[]={'a','b','c','d','e','g'}; 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;
}
}
}
}
abcdeg
abcdge
abcedg
abcegd
abcged
abcgde
abdceg
abdcge
abdecg
abdegc
abdgec
abdgce
abedcg
abedgc
abecdg
abecgd
abegcd
abegdc
abgdec
abgdce
abgedc
abgecd
abgced
abgcde
acbdeg
acbdge
acbedg
acbegd
acbged
acbgde
acdbeg
acdbge
acdebg
acdegb
acdgeb
acdgbe
acedbg
acedgb
acebdg
acebgd
acegbd
acegdb
acgdeb
acgdbe
acgedb
acgebd
acgbed
acgbde
adcbeg
adcbge
adcebg
adcegb
adcgeb
adcgbe
adbceg
adbcge
adbecg
adbegc
adbgec
adbgce
adebcg
adebgc
adecbg
adecgb
adegcb
adegbc
adgbec
adgbce
adgebc
adgecb
adgceb
adgcbe
aecdbg
aecdgb
aecbdg
aecbgd
aecgbd
aecgdb
aedcbg
aedcgb
aedbcg
aedbgc
aedgbc
aedgcb
aebdcg
aebdgc
aebcdg
aebcgd
aebgcd
aebgdc
aegdbc
aegdcb
aegbdc
aegbcd
aegcbd
aegcdb
agcdeb
agcdbe
agcedb
agcebd
agcbed
agcbde
agdceb
agdcbe
agdecb
agdebc
agdbec
agdbce
agedcb
agedbc
agecdb
agecbd
agebcd
agebdc
agbdec
agbdce
agbedc
agbecd
agbced
agbcde
bacdeg
bacdge
bacedg
bacegd
bacged
bacgde
badceg
badcge
badecg
badegc
badgec
badgce
baedcg
baedgc
baecdg
baecgd
baegcd
baegdc
bagdec
bagdce
bagedc
bagecd
bagced
bagcde
bcadeg
bcadge
bcaedg
bcaegd
bcaged
bcagde
bcdaeg
bcdage
bcdeag
bcdega
bcdgea
bcdgae
bcedag
bcedga
bceadg
bceagd
bcegad
bcegda
bcgdea
bcgdae
bcgeda
bcgead
bcgaed
bcgade
bdcaeg
bdcage
bdceag
bdcega
bdcgea
bdcgae
bdaceg
bdacge
bdaecg
bdaegc
bdagec
bdagce
bdeacg
bdeagc
bdecag
bdecga
bdegca
bdegac
bdgaec
bdgace
bdgeac
bdgeca
bdgcea
bdgcae
becdag
becdga
becadg
becagd
becgad
becgda
bedcag
bedcga
bedacg
bedagc
bedgac
bedgca
beadcg
beadgc
beacdg
beacgd
beagcd
beagdc
begdac
begdca
begadc
begacd
begcad
begcda
bgcdea
bgcdae
bgceda
bgcead
bgcaed
bgcade
bgdcea
bgdcae
bgdeca
bgdeac
bgdaec
bgdace
bgedca
bgedac
bgecda
bgecad
bgeacd
bgeadc
bgadec
bgadce
bgaedc
bgaecd
bgaced
bgacde
cbadeg
cbadge
cbaedg
cbaegd
cbaged
cbagde
cbdaeg
cbdage
cbdeag
cbdega
cbdgea
cbdgae
cbedag
cbedga
cbeadg
cbeagd
cbegad
cbegda
cbgdea
cbgdae
cbgeda
cbgead
cbgaed
cbgade
cabdeg
cabdge
cabedg
cabegd
cabged
cabgde
cadbeg
cadbge
cadebg
cadegb
cadgeb
cadgbe
caedbg
caedgb
caebdg
caebgd
caegbd
caegdb
cagdeb
cagdbe
cagedb
cagebd
cagbed
cagbde
cdabeg
cdabge
cdaebg
cdaegb
cdageb
cdagbe
cdbaeg
cdbage
cdbeag
cdbega
cdbgea
cdbgae
cdebag
cdebga
cdeabg
cdeagb
cdegab
cdegba
cdgbea
cdgbae
cdgeba
cdgeab
cdgaeb
cdgabe
ceadbg
ceadgb
ceabdg
ceabgd
ceagbd
ceagdb
cedabg
cedagb
cedbag
cedbga
cedgba
cedgab
cebdag
cebdga
cebadg
cebagd
cebgad
cebgda
cegdba
cegdab
cegbda
cegbad
cegabd
cegadb
cgadeb
cgadbe
cgaedb
cgaebd
cgabed
cgabde
cgdaeb
cgdabe
cgdeab
cgdeba
cgdbea
cgdbae
cgedab
cgedba
cgeadb
cgeabd
cgebad
cgebda
cgbdea
cgbdae
cgbeda
cgbead
cgbaed
cgbade
dbcaeg
dbcage
dbceag
dbcega
dbcgea
dbcgae
dbaceg
dbacge
dbaecg
dbaegc
dbagec
dbagce
dbeacg
dbeagc
dbecag
dbecga
dbegca
dbegac
dbgaec
dbgace
dbgeac
dbgeca
dbgcea
dbgcae
dcbaeg
dcbage
dcbeag
dcbega
dcbgea
dcbgae
dcabeg
dcabge
dcaebg
dcaegb
dcageb
dcagbe
dceabg
dceagb
dcebag
dcebga
dcegba
dcegab
dcgaeb
dcgabe
dcgeab
dcgeba
dcgbea
dcgbae
dacbeg
dacbge
dacebg
dacegb
dacgeb
dacgbe
dabceg
dabcge
dabecg
dabegc
dabgec
dabgce
daebcg
daebgc
daecbg
daecgb
daegcb
daegbc
dagbec
dagbce
dagebc
dagecb
dagceb
dagcbe
decabg
decagb
decbag
decbga
decgba
decgab
deacbg
deacgb
deabcg
deabgc
deagbc
deagcb
debacg
debagc
debcag
debcga
debgca
debgac
degabc
degacb
degbac
degbca
degcba
degcab
dgcaeb
dgcabe
dgceab
dgceba
dgcbea
dgcbae
dgaceb
dgacbe
dgaecb
dgaebc
dgabec
dgabce
dgeacb
dgeabc
dgecab
dgecba
dgebca
dgebac
dgbaec
dgbace
dgbeac
dgbeca
dgbcea
dgbcae
ebcdag
ebcdga
ebcadg
ebcagd
ebcgad
ebcgda
ebdcag
ebdcga
ebdacg
ebdagc
ebdgac
ebdgca
ebadcg
ebadgc
ebacdg
ebacgd
ebagcd
ebagdc
ebgdac
ebgdca
ebgadc
ebgacd
ebgcad
ebgcda
ecbdag
ecbdga
ecbadg
ecbagd
ecbgad
ecbgda
ecdbag
ecdbga
ecdabg
ecdagb
ecdgab
ecdgba
ecadbg
ecadgb
ecabdg
ecabgd
ecagbd
ecagdb
ecgdab
ecgdba
ecgadb
ecgabd
ecgbad
ecgbda
edcbag
edcbga
edcabg
edcagb
edcgab
edcgba
edbcag
edbcga
edbacg
edbagc
edbgac
edbgca
edabcg
edabgc
edacbg
edacgb
edagcb
edagbc
edgbac
edgbca
edgabc
edgacb
edgcab
edgcba
eacdbg
eacdgb
eacbdg
eacbgd
eacgbd
eacgdb
eadcbg
eadcgb
eadbcg
eadbgc
eadgbc
eadgcb
eabdcg
eabdgc
eabcdg
eabcgd
eabgcd
eabgdc
eagdbc
eagdcb
eagbdc
eagbcd
eagcbd
eagcdb
egcdab
egcdba
egcadb
egcabd
egcbad
egcbda
egdcab
egdcba
egdacb
egdabc
egdbac
egdbca
egadcb
egadbc
egacdb
egacbd
egabcd
egabdc
egbdac
egbdca
egbadc
egbacd
egbcad
egbcda
gbcdea
gbcdae
gbceda
gbcead
gbcaed
gbcade
gbdcea
gbdcae
gbdeca
gbdeac
gbdaec
gbdace
gbedca
gbedac
gbecda
gbecad
gbeacd
gbeadc
gbadec
gbadce
gbaedc
gbaecd
gbaced
gbacde
gcbdea
gcbdae
gcbeda
gcbead
gcbaed
gcbade
gcdbea
gcdbae
gcdeba
gcdeab
gcdaeb
gcdabe
gcedba
gcedab
gcebda
gcebad
gceabd
gceadb
gcadeb
gcadbe
gcaedb
gcaebd
gcabed
gcabde
gdcbea
gdcbae
gdceba
gdceab
gdcaeb
gdcabe
gdbcea
gdbcae
gdbeca
gdbeac
gdbaec
gdbace
gdebca
gdebac
gdecba
gdecab
gdeacb
gdeabc
gdabec
gdabce
gdaebc
gdaecb
gdaceb
gdacbe
gecdba
gecdab
gecbda
gecbad
gecabd
gecadb
gedcba
gedcab
gedbca
gedbac
gedabc
gedacb
gebdca
gebdac
gebcda
gebcad
gebacd
gebadc
geadbc
geadcb
geabdc
geabcd
geacbd
geacdb
gacdeb
gacdbe
gacedb
gacebd
gacbed
gacbde
gadceb
gadcbe
gadecb
gadebc
gadbec
gadbce
gaedcb
gaedbc
gaecdb
gaecbd
gaebcd
gaebdc
gabdec
gabdce
gabedc
gabecd
gabced
gabcde
bac，因此j=2时交换bc，产生cab，加入vector。第二个循环，cab，j=0时不等于i=1，交换ca，产生acb，加入vector，j=2时交换cb，产生abc，重复，不加入vector，这里算法就有冗余了，chaArray变回abc第三个循环，abc,j=0时不等于i=2，交换ac，产生cba，加入vector，j=1时交换cb，产生cab，重复，不加入vector，又重复一次循环结束，vector里面就是abc,bac,cab,acb,cba如果按这个思路修改，只能把所有新产生字符串都做全字符交换，比如第一个产生的bac，就要再交换ac。。否则你的算法从逻辑上也最多只能出现str.lenth平方的组合数，也就是说4字符串最多只有16种，5字符串最多只有25种，远远少于实际的全排列数字。
{
//char s[] = "abcdefghijklmnopqrstuvwxyz0123456789";
for(int i=1;i<=n;i++)
printf("%c",s[x[i]-1]);
printf("\n");
d++;
}
void makepass(int n,int r)
{
DWORD d=0;
int *p = new int[r+1];
int i , end = 0;
for(i = 1; i<=r; i++)
p[i]=1;
execute(p,r,d);
d++;
while(!end)
{
p[r]++;
for(i=r;i>0;i--)
if(p[i]==n+1)
{
p[i] = 1;
p[i-1]++;
}
execute(p,r,d);
d++;
end =1;
for(i=r;i>0;i--)
if(p[i]!=n)
{
end=0;
break;
}
}
printf("%d",d);
}非递归的～～～～～～～～～～～～～～～可自定宽度和密码位数