Java实现abc字符串排列组合

时间:2021-08-03 06:22:52

1.可重复排列:abc三个字符组成的所有长度为3的字符串,aaa,aab,aac......ccc 一共27种

利用递归的思想,第一个字符可以从abc中选择一个,三种选择,之后问题转化为abc组成长度为2的字符的情况,循环递归后可以求出所有的可能。控制好循环退出条件即可。

利用递归可以处理,不知道字符长度的情况下,即通用处理。如果知道长度,只需要利用多层循环,也可以得出结论。

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class permutation {
 public static void main(string[] args) {
  char[] chs = {'a','b','c'};
  per(new char[3], chs, 3-1);
 }
 public static void per(char[] buf, char[] chs, int len){
  if(len == -1){
   for(int i=buf.length-1; i>=0; --i)
    system.out.print(buf[i]);
   system.out.println();
   return;
  }
  for(int i=0; i<chs.length; i++){
   buf[len] = chs[i];
   per(buf, chs, len-1);
  }
 }
}

可重复选择,一共27种情况,结果如下图所示

Java实现abc字符串排列组合

2.全排列:还是abc三个字符,全排列即字符不能重复。最后 3*2 =6种结果

可以利用1中的方法,只要判断3个字符是否相等,都不相等的才是需要的全排列里的一个。这样的时间复杂度为n^n,而全排列的种类为n!所以需要设计一种n!的算法。

也可以利用递归,第一个字符串一共有n种选择,剩下的变成一个n-1规模的递归问题。而第一个字符的n种选择,都是字符串里面的。因此可以使用第一个字符与1-n的位置上进行交换,得到n中情况,然后递归处理n-1的规模,只是处理完之后需要在换回来,变成原来字符的样子。

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class arrange {
 public static void main(string[] args) {
  char[] chs = {'a','b','c'};
  arrange(chs, 0, chs.length);
 }
 public static void arrange(char[] chs, int start, int len){
  if(start == len-1){
   for(int i=0; i<chs.length; ++i)
    system.out.print(chs[i]);
   system.out.println();
   return;
  }
  for(int i=start; i<len; i++){
   char temp = chs[start];
   chs[start] = chs[i];
   chs[i] = temp;
   arrange(chs, start+1, len);
   temp = chs[start];
   chs[start] = chs[i];
   chs[i] = temp;
  }
 }
}

运行结果如下图所示,一共6种组合

Java实现abc字符串排列组合

3.组合:abc三个字符的所有组合

求所有组合也就是abc各个位是否选取的问题,第一位2中可能,第二位2种。。。所以一共有2^n种。用0表示不取,1表示选取,这样可以用110这样的形式表示ab。abc一共的表示形式从0到2^3-1。然后按位与运算,如果结果为1就输出当前位,结果0不输出。

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class comb {
 public static void main(string[] args) {
  char[] chs = {'a','b','c'};
  comb(chs);
 }
 
 public static void comb(char[] chs) {
  int len = chs.length;
  int nbits = 1 << len;
  for (int i = 0; i < nbits; ++i) {
   int t;
   for (int j = 0; j < len; j++) {
    t = 1 << j;
    if ((t & i) != 0) { // 与运算,同为1时才会是1
     system.out.print(chs[j]);
    }
   }
   system.out.println();
  }
 }
}

输出结果如下,第一行为空,表示一个都不取

Java实现abc字符串排列组合

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持服务器之家。

原文链接:http://blog.csdn.net/Tredemere/article/details/52815965