高分 急求！！！！
将Ｍ个Ａ和Ｎ个Ｂ，组合成一个长度为（Ｍ+Ｎ）的字符串，每个新组成的字符串中都包含Ｍ个Ａ和Ｎ个Ｂ，现在要输出组合的全部字符串，怎么编程实现？有一定难度哦，望高手解决一下，谢谢。
[解决办法]
public class Permutations {
public static void perm(String s) { perm( " ", s); }
private static void perm(String prefix, String s) {
int N = s.length();
if (N == 0) System.out.println(prefix);
else {
for (int i = 0; i < N; i++)
perm(prefix + s.charAt(i), s.substring(0, i) + s.substring(i+1, N));
}
}
private static void swap(char[] a, int i, int j) {
char c;
c = a[i]; a[i] = a[j]; a[j] = c;
}
private static String builder(char c, int i){
StringBuilder sb = new StringBuilder();
for(int j = 0; j < i; j++)
sb.append(c);
return sb.toString();
}
public static void main(String[] args) {
char A,B;
int M,N;
A = 'a ';
B = 'b ';
M = 2;
N = 3;
String aString = builder(A,M);
String bString = builder(B,N);
perm(aString + bString);
}
}
哈，作业没写完来玩这个。
[解决办法]
int m=5;
int n=4;
String A= "A ";// 0
String B= "B ";// 1
for(int i=0;i <Math.pow(2,m+n);i++){
String str = Integer.toBinaryString(i);
if(str.replaceAll( "0 ", " ").length()==n){
str=str.replaceAll( "0 ", "A ").replaceAll( "1 ", "B ");
for(int j=str.length();j <m+n;j++)
str= "A "+str;
System.out.println(str);
}
}
[解决办法]
package test01;
public class Test01 {
private static int get(int m, int n) {// 返回2的m+n次
int add = 1;
for (int i = 1; i <= (m + n); i++)
add = add * 2;
return add;
}
private static int[] covert(int m, int n, int a) {// 把a转为2进制
int AB[] = new int[m + n];
int aa = a;
for (int i = 1; i <= m + n; i++) {
a = aa % 2;
if (aa != 1) {
if (a != 0)
AB[i - 1] = 1;
else
AB[i - 1] = 0;
}
if (aa == 1) {
AB[i - 1] = 1;
break;
}
aa = aa / 2;
}
return AB;
}
public static void main(String[] args) {
int m = 3, n = 2, a;// m表示M个A，n表示N个B；
a = get(m, n);
for (int j = 0; j < a; j++) {
int AB[] = new int[m + n];
int mn = 0;
AB = covert(m, n, j);
for (int i = 0; i < m + n; i++) {
mn = mn + AB[i];
}
if (mn == m) {
StringBuffer s = new StringBuffer();
for (int i = 0; i < m + n; i++) {
if (AB[i] == 1)
s.append( 'A ');
else
s.append( 'B ');
}
System.out.println(s.toString());
}
}
}
}
用最简单的方法写了个，m表示M个A，n表示N个B；
无重复。。。写的很丑陋。。。高手表扔砖啊。。。
没有问题请结帖。呵呵。
用SET可以实现，但估计初学者不懂。。。比如我。。。
[解决办法]
奋斗了半天终于搞出来个算法....
但愿楼主能看的明白...
shan1119(大天使，卐～解！) 的方法虽然简单...但是m,n值一大就不行了...
注意,以下方法能运行,结果也正确,就是写的有点乱...应该还能再简化
import java.util.*;
public class Test {
public static long countNum = 0;
public static void main(String[] args) {
Long startTime = System.currentTimeMillis();
int n = 5;
int m = 14;
Test t = new Test(m,n);
int[] a = {n};
t.array[1].add(a);
t.split(a);
for(int k=1; k <=n; k++) {
boolean[] ab = new boolean[m+1];
for(int i=0; i <k; i++) {
ab[i] = true;
}
t.choice(ab, k);
}
System.out.println(countNum);
Long endTime = System.currentTimeMillis();
System.out.println( "Totle time is " + (endTime - startTime) + " milliseconds ");
}
public static void print(boolean[] ab) {
for(int i=0; i <ab.length; i++) {
if(ab[i] == true)
System.out.print( "1 ");
else
System.out.print( "0 ");
}
}
public Test(int m, int n) {
array = new ArrayList[n+1];
for(int i=0; i <n+1; i++) {
array[i] = new ArrayList();
}
}
private ArrayList[] array;
public void split(int[] a) {
int last = a[a.length-1];
if(last!=1) {
for(int i=1; i <last; i++) {
int[] aSplit = new int[a.length+1];
System.arraycopy(a, 0, aSplit, 0, a.length-1);
aSplit[a.length-1] = last-i;
aSplit[a.length] = i;
array[a.length+1].add(aSplit);
split(aSplit);
}
}
}
public void choice(boolean[] ab, int num) {
do {
for(int i=0; i <array[num].size(); i++) {
int[] ai = (int[])array[num].get(i);
int n = 0;
for(int j=0; j <ab.length; j++) {
if(ab[j] != false) {
print(ai[n]);
n++;
}
if(j != ab.length-1) System.out.print( "A ");
}
System.out.println();
countNum++;
}
} while(this.has1to0Change(ab));
}
public void print(int n) {
for(int i=0; i <n; i++) {
System.out.print( "B ");
}
}
public boolean has1to0Change(boolean[] ab) {
boolean result = false;
int count = 0;
boolean privious = false;
for(int i=0; i <ab.length; i++) {
boolean current = ab[i];
if((current == false) && (privious == true)) {
result = true;
ab[i] = true;
for(int k=0; k <i; k++) {
if(k < count-1) ab[k] = true;
else ab[k] = false;
}
break;
}
privious = current;
if(current == true) count++;
}
return result;
}
}
result:
11628
Totle time is 1442 milliseconds
[解决办法]
修改了下代码~速度有本质提高
import java.util.*;
public class Test {
public static long countNum = 0;
public static void main(String[] args) {
Long startTime = System.currentTimeMillis();
int n = 5;
int m = 14;
Test t = new Test(m,n);
int[] a = {n};
t.array[1].add(a);
t.split(a);
String[][][] s1 = new String[n+1][][];
for(int i=1; i <=n; i++) {
int length = t.array[i].size();
s1[i] = new String[length][];
for(int j=0; j <length; j++) {
int[] ai = (int[])t.array[i].get(j);
s1[i][j] = new String[i];
for(int k=0; k <i; k++) {
StringBuilder sb = new StringBuilder( " ");
for(int p=0; p <ai[k]; p++)
sb.append( 'A ');
s1[i][j][k] = sb.toString();
}
}
}
for(int i=1; i <=n; i++) {
for(int j=0; j <s1[i].length; j++) {
for(int k=0; k <s1[i][j].length; k++) {
System.out.print(s1[i][j][k] + ", ");
}
System.out.println();
}
}
/*for(int i=1; i <=n; i++) {
for(int j=0; j <t.array[i].size(); j++) {
int[] ai = (int[])t.array[i].get(j);
for(int k=0; k <ai.length; k++) {
System.out.print(ai[k] + ", ");
}
System.out.println();
}
}*/
for(int k=1; k <=n; k++) {
int[] ab = new int[m+1];
for(int i=0; i <k; i++) {
ab[i] = 1;
}
t.choice(ab, k, s1);
}
System.out.println(countNum);
Long endTime = System.currentTimeMillis();
System.out.println( "Totle time is " + (endTime - startTime) + " milliseconds ");
}
public Test(int m, int n) {
array = new ArrayList[n+1];
for(int i=0; i <n+1; i++) {
array[i] = new ArrayList();
}
s = new StringBuilder( " ");
for(int i=0; i <m; i++)
s.append( 'B ');
}
private ArrayList[] array;
private StringBuilder s;
public void split(int[] a) {
int last = a[a.length-1];
if(last!=1) {
for(int i=1; i <last; i++) {
int[] aSplit = new int[a.length+1];
System.arraycopy(a, 0, aSplit, 0, a.length-1);
aSplit[a.length-1] = last-i;
aSplit[a.length] = i;
array[a.length+1].add(aSplit);
split(aSplit);
}
}
}
public void choice(int[] ab, int num, String[][][] s1) {
do {
int[] ai = new int[num];
int count = 0;
for(int i=0; i <ab.length; i++) {
if(ab[i] == 1) {
ai[count] = i;
//System.out.print(ai[count] + ", ");
count++;
}
}
//System.out.println();
for(int j=0; j <s1[num].length; j++) {
StringBuilder sb = new StringBuilder(s);
for(int i=0; i <ai.length; i++) {
sb.insert(ai[i], s1[num][j][i]);
}
System.out.println(sb);
countNum++;
}
} while(this.has1to0Change(ab));
}
public boolean has1to0Change(int[] ab) {
boolean result = false;
int count = 0;
int privious = 0;
for(int i=0; i <ab.length; i++) {
int current = ab[i];
if((current == 0) && (privious == 1)) {
result = true;
ab[i] = 1;
for(int k=0; k <i; k++) {
if(k < count-1) ab[k] = 1;
else ab[k] = 0;
}
break;
}
privious = current;
if(current == 1) count++;
}
return result;
}
}
11628
Totle time is 219 milliseconds
