用java数组实现全排列的每种情况
在数学中,排列组合问题是一个很常见的问题。下面我们举一个很常见的全排列问题:
有A、B、C、D四个人排成一条队,请问有多少种排法?
这个答案显而易见是:
讯享网
而这24种情况分别是:
ABCD ABDC ACBD ACDB ADBC ADCB
BACD BADC BCAD BCDA BDAC BDCA
CABD CADB CBAD CBDA CDAB CDBA
DABC DACB DBAC DBCA DCAB DCBA
而我们亲自手写罗列这24种情况就已经有点厌烦了,更别说罗列ABCDE五个人排成一条队有120种情况,甚至ABCDEF六个人排成一条队有720种情况。
所以下面我们用java数组实现全排列的每种情况
1、首先,我们得要知道一共有多少种情况(便于建立一个数组来存放这些所所有情况)
String string="ABCD"; int num=1; for(int i=1;i<=string.length();i++)//计算全排列的所有结果的数量num num=num*i;
讯享网
原理(即求n的阶乘):
2、创建一个num个数量级的字符串数组——用来存放全排列的妹子种情况
讯享网String s[]=new String[num];
3、计算求出每一种情况:
概念图如下:
A、B、C、D四个人排成一队,即一条队有四个空位来给这四个人来站。

A、B、C、D都会站到每个位置,也即A、B、C、D都会站到第一个位置
我们先假设第一个位置站A,然后第二位置可能站B、C、D(三种情况)
然后假设第二个位置站的是B,那第三个位置可能站C、D(两种情况)
再假设第三个位置站的是C,那第四个位置站的就只剩下D(只有一种情况)
之后我们就可以得出第一种情况:ABCD
由前面的假设,第三个位置有两种情况,
假设第一个位置站A第二个位置站的是B第三个位置站的是C的情况已经解决了
我们再假设第三个位置是D,又得出一种情况:ABDC
第三个位置的两个情况已经解决了,
我们再假设第二个位置站C,那第三个位置可能站B、D…再以及类推

这样我们把第一个位置站A的所有情况都解决了,然后就继续以此类推将第一个位置站B的所有情况解决,再将第一个位置站C的所有情况解决…
代码:

String string="ABCD"; int num=1; String s[]=new String[num]; for(int i=1;i<=string.length();i++)//计算全排列的所有结果的数量num num=num*i; int k=0;//k用于表示字符串数组s[]的下标 for(int i=0;i<string.length();i++) {
s[k]=""+string.charAt(i); String s2=string.replace(string.charAt(i)+"", "");//用String类的replace方法实现删除string的某个特定字符 k=permutation(s2,s,k);//递归调用permutation函数,传入新的字符串s2,字符串数组s[]以及字符串数组s[]的下标k k++; }
s[k]=""+string.charAt(i); 第一次执行即s[0]=""+string.charAt(0)
即s[0]=“A”
String s2=string.replace(string.charAt(i)+"", “”);
第一次执行即s2=string.replace(string.charAt(0)+"", “”)
即s2=“BCD”
然后permutation()函数代码如下:
讯享网public static int permutation(String string,String s[],int k) {
String head=s[k];//用于记录前面的假设的情况 for(int i=0;i<string.length();i++) {
s[k]=head; s[k]=s[k]+string.charAt(i); String s2=string.replace(string.charAt(i)+"", "");//用String类的replace方法实现删除string的某个特定字符 k=permutation(s2,s,k); if(i!=string.length()-1) k++; } return k;//通过返回k来实现k的共用 }
注:String head=s[k];解释如下:
例:
当到递归调用到倒数第三次时:
s[0]=“AB” 再调用两次后s[0]=“ABCD”
然后返回上两层层函数(即倒数第三次递归时)执行 k++;
此时s[1]=""是空的,
所以需要提前记录head=s[0](“AB”)并赋值给s[1]
可以使得s[1]="AB"然后执行下一种情况(第三个位置假设站D)
就可以得到s[1]="ABD"再继续递归最后得到s[1]=“ABDC”
if(i!=string.length()-1)
k++;
解释如下:
已经执行到最后一次时,如果k++,则返回上一层的时候已经执行完了一个k=permutation(s2,s,k); 若再次k++会导致字符串数组s[]遗漏
k=permutation(s2,s,k); if(i!=string.length()-1) k++;
完整代码如下:
讯享网 public class 全排列 {
//罗列出全排列的所有情况 public static String[] Full_permutation(String string) {
int num=1,k=0;//k用来记录字符串数组s[]的下标 //计算全排列的所有结果的数量num for(int i=1;i<=string.length();i++) num=num*i; String s[]=new String[num];//用num创建一维数组来存放所有情况 for(int i=0;i<string.length();i++) {
s[k]=""+string.charAt(i); String s2=string.replace(string.charAt(i)+"", "");//用String类的replace方法实现删除string的某个特定字符 k=permutation(s2,s,k); k++; } return s;//返回字符串数组 } //递归调用该函数 public static int permutation(String string,String s[],int k) {
String head=s[k]; for(int i=0;i<string.length();i++) {
s[k]=head; s[k]=s[k]+string.charAt(i); String s2=string.replace(string.charAt(i)+"", ""); k=permutation(s2,s,k); if(i!=string.length()-1) k++; } return k;//通过返回k来实现k的共用 } public static void main(String []args) {
String string="ABCD"; String s[]= Full_permutation(string); for(int i=0;i<s.length;i++) System.out.println(s[i]); } }
以上仅是我个人(代码菜鸟一枚)的理解看法,如有不当请各位大佬提出!谢谢!
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容,请联系我们,一经查实,本站将立刻删除。
如需转载请保留出处:https://51itzy.com/kjqy/76198.html