Java实现abc字符串排列组合

Java实现abc字符串排列组合

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

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

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

puzXCKeblic 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

buf[len] = chs[i];

per(buf, chs, len-1);

}

}

}

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

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

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

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

public class Arrange {

public static void main(String[] args) {

char[] chs = {'a','b','c'};

arrange(chs, 0, chs.length);

}

public static void arrange(char[]zXCKe chs, int start, int len){

if(start == len-1){

for(int i=0; i

System.out.print(chs[i]);

System.out.println();

return;

}

for(int i=start; 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种组合

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

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

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();

}

}

}

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

buf[len] = chs[i];

per(buf, chs, len-1);

}

}

}

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

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

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

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

public class Arrange {

public static void main(String[] args) {

char[] chs = {'a','b','c'};

arrange(chs, 0, chs.length);

}

public static void arrange(char[]zXCKe chs, int start, int len){

if(start == len-1){

for(int i=0; i

System.out.print(chs[i]);

System.out.println();

return;

}

for(int i=start; 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种组合

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

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

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();

}

}

}

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

System.out.print(chs[i]);

System.out.println();

return;

}

for(int i=start; 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种组合

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

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

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();

}

}

}

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

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种组合

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

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

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();

}

}

}

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

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。