`
pengmj
  • 浏览: 24596 次
  • 性别: Icon_minigender_1
  • 来自: 杭州
社区版块
存档分类
最新评论

java编写字符串全组合输出

JavaCC++C#Exchange 
阅读更多
如“abc”输出结果为：“abc”,“acb”,“bac”,“bca”,“cab”,“cba”

public class AllCombString {
public static int t;//组合个数

public static void main(String[] args) {
  String str = "123";
  char[] c = str.toCharArray();
  println(c)
  t++;
  allCombString(c,0);
  System.out.println(t);
}
public static void allCombString(char[] c,int s){
  int l = c.length;
  if(l-s==2){
   char temp = c[l-1];
   c[l-1] = c[l-2];
   c[l-2] = temp;
   println(c);
   t++;
  }
  else{
   for(int i=s;i<l;i++){
    moveToHead(c,i,s);
    char ct[] = new char[l];
    System.arraycopy(c, 0, ct, 0, l);//保持其他元素位置不变
    allCombString(ct,s+1);
   }
  }
}

public static void moveToHead(char[] c,int id,int s){
  if(id>s&&id<c.length){
   char temp = c[id];
   for(int i=id;i>s;i--){
    c[i] = c[i-1];
   }
   c[s] = temp;
   println(c);
   t++;
  }
}

public static void println(char[] c){
  System.out.println(new String(c));
}
}
输出结果：

123
132
213
231
321
312
6

设计思路：

1、n个字符，顺序选取其中第1个；

2、在剩下的n-1个字符中，再选取其中的第1个；

3、若剩余的字符只剩下2个，则这两个字符交换位置；若不是，则继续第2步。

4、这是一个典型的递归，无论有多少个字符，到最后只需交换最后两个字符即可。

5、为了能按顺序选取字符（因为递归之后会影响字符的顺序，如：“abcd”经过第一轮递归之后变成“adbc”,这时再执行第2步的话，取到的字符是“d”，而不是“b”），所以这里使用了数组拷贝，for循环不受递归的影响。（这个问题想了老半天，暂时只能用这种方法，即使效率比较低）。

6、组合的个数是字符个数的阶层，如“abc”,组合个数为3!=6

不知道大家有没有更好的方式
分享到：
| 文件上传组件前台+后台
评论
8 楼 pengmj 2010-12-10  
楼上那个也太不灵活了吧；）
7 楼 jkhere 2010-12-10  
public class CopyOfAllCombString
{
public static int t;//组合个数
//Java程序的主入口函数
public static void main(String[] args)
{
String str = "ABCDE";

char[] c = str.toCharArray();


for(int j=5;j>0;j--){//5是长度
EX(c,j,5);
for(int i=4; i>0; i--){//4是后4位
EX(c,i,4);
F1(c);
EX(c,4-i,4);EX(c,1,3);
   }
EX(c,5,j);
}

/* int l = c.length;
for(int s=0; s<l-5;s++){
for(int x=l-s;x>0;x--){
EX(c,x,l-s);

for(int k=6;k>0;k--){
EX(c,k,6);
for(int j=5;j>0;j--){//5是长度
EX(c,j,5);
for(int i=4; i>0; i--){//4是后4位
EX(c,i,4);
F1(c);
EX(c,4-i,4);EX(c,1,3);
   }
EX(c,5,j);
}
EX(c,6,k);
}
EX(c,l-s,x);
}
}  */
  println(c);//测试


System.out.println(t);

}





private static void EX(char[] c, int i, int j) {
// TODO Auto-generated method stub
                        int l = c.length;
  if(i>0&&j>0){
char temp=c[l-i];
    c[l-i]=c[l-j];
    c[l-j]=temp;
  }
}








private static void F1(char[] c) {
// TODO Auto-generated method stub
  int l = c.length;
  println(c);
  exchange(c);
   
char temp=c[l-1];
    c[l-1]=c[l-3];
    c[l-3]=temp;
    exchange(c);
    exchange(c);
   
    temp=c[l-2];
    c[l-2]=c[l-3];
    c[l-3]=temp;
    exchange(c);
    exchange(c);
   
}
private static void exchange(char[] c) {
// TODO Auto-generated method stub
int l = c.length;

char temp=c[l-1];
    c[l-1]=c[l-2];
    c[l-2]=temp;
    println(c);
  
}




private static void println(char[] c) {
// TODO Auto-generated method stub
System.out.println(new String(c));//System.out.print("  ");
t++;
}

}
6 楼 lansuiyun 2010-12-06   
package month11;

import java.util.LinkedList;

public class QuanPaiXu {

	private String input;

	public QuanPaiXu(String input1) {
		this.input = input1;
	}

	public LinkedList<LinkedList<Character>> insert(
			LinkedList<LinkedList<Character>> list, char inserChar) {
		LinkedList<LinkedList<Character>> reValue = new LinkedList<LinkedList<Character>>();
		LinkedList<Character> temp1;
		LinkedList<Character> temp2;
		for (int i = 0; i < list.size(); i++) {
			temp1 = list.get(i);
			for (int j = 0; j <= temp1.size(); j++) {
				temp2 = (LinkedList<Character>) temp1.clone();
//				temp2 = copy(temp1);
				temp2.add(j, inserChar);
				reValue.add(temp2);
			}
		}
		return reValue;
	}

	public LinkedList<LinkedList<Character>> paixu() {
		char[] inputChar = this.input.toCharArray();
		LinkedList<LinkedList<Character>> ini = new LinkedList<LinkedList<Character>>();
		LinkedList<LinkedList<Character>> reValue = new LinkedList<LinkedList<Character>>();
		LinkedList<Character> temp = new LinkedList<Character>();
		temp.add(inputChar[0]);
		ini.add(temp);
		for (int i = 1; i < inputChar.length; i++) {
			ini = insert(ini, inputChar[i]);
			if(i==inputChar.length-1)
				reValue.addAll(ini);
		}
		return reValue;
	}
	

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		QuanPaiXu q = new QuanPaiXu("abc");
		LinkedList<LinkedList<Character>> reValue = q.paixu();
		for (int i = 0; i < reValue.size(); i++) {
			System.out.println("第"+(i+1)+"个");
			LinkedList<Character> temp1 = reValue.get(i);
			for (int j = 0; j < temp1.size(); j++) {
				System.out.print(temp1.get(j));
			}
			System.out.println();
		}
	}

}

思路：插空位，比如abc，初始a，后边的按顺序插入，b插入则有ba,ab,c在插入则有cba,bca,bac,cab,acb,abc

不清楚效率比其他的方法如何
5 楼 zzhonghe 2010-12-04  
楼主写的有点复杂了，我也来贴一个吧： 

public static List<String> getStringSorts(String input){   
    List<String> allSortedList=new ArrayList<String>();   
    char leftChar=input.charAt(0);   
    if(input.length()>1){   
        String rightString=input.substring(1,input.length());   
        List<String> rightStringSortedList=getStringSorts(rightString);   
        for(String rightStringTmp:rightStringSortedList){   
            for(int i=0;i<rightStringTmp.length()+1;i++){   
                allSortedList.add(new StringBuffer(rightStringTmp).insert(i, leftChar).toString());   
            }   
        }   
    }else{   
        allSortedList.add(String.valueOf(leftChar));   
    }   
    return allSortedList;   
}
4 楼 pengmj 2010-12-03  
cai3178940 写道

楼主的代码看的我蛋疼，最后还是看明白了。
顺着楼主的思路我帮你改了下代码，不需要复制数组，而且更容易理解了。
楼主这个算法是自己想出来的吗，很厉害，我肯定想不出来。。。 
public class AllCombString {
	public static int t=0;// 组合个数

	public static void main(String[] args) {
		String str = "123";
		char[] c = str.toCharArray();
		//println(c);
		//t++;
		allCombString(c, 0);
		System.out.println(t);
	}

	public static void allCombString(char[] c, int s) {
		int len = c.length;
		if (s == len-1) {
			println(c);
			t++;
		} else {
			for (int i = s; i < len; i++) {
				moveToHead(c, i, s);
				//char ct[] = new char[l];
				//System.arraycopy(c, 0, ct, 0, l);// 保持其他元素位置不变
				allCombString(c, s + 1);
				moveBack(c, i, s);  //既然改变了位置，那就再改回来
			}
		}
	}

	public static void moveToHead(char[] c, int id, int s) {
		if (id > s && id < c.length) {
			char temp = c[id];
			for (int i = id; i > s; i--) {
				c[i] = c[i - 1];
			}
			c[s] = temp;
			//println(c);
			//t++;
		}
	}
	public static void moveBack(char[] c, int id, int s) {
		if (id > s && id < c.length) {
			char temp = c[s];
			for (int i = s; i < id; i++) {
				c[i] = c[i+1];
			}
			c[id] = temp;
			//println(c);
			//t++;
		}
	}

	public static void println(char[] c) {
		System.out.println(new String(c));
	}
}

这是我在一次上机笔试时遇到的题目，当时没想出来，后来回家想了一个晚上才写出来，呵呵。
你改的不错！
3 楼 cai3178940 2010-12-03  

楼主的代码看的我蛋疼，最后还是看明白了。
顺着楼主的思路我帮你改了下代码，不需要复制数组，而且更容易理解了。
楼主这个算法是自己想出来的吗，很厉害，我肯定想不出来。。。 
public class AllCombString {
	public static int t=0;// 组合个数

	public static void main(String[] args) {
		String str = "123";
		char[] c = str.toCharArray();
		//println(c);
		//t++;
		allCombString(c, 0);
		System.out.println(t);
	}

	public static void allCombString(char[] c, int s) {
		int len = c.length;
		if (s == len-1) {
			println(c);
			t++;
		} else {
			for (int i = s; i < len; i++) {
				moveToHead(c, i, s);
				//char ct[] = new char[l];
				//System.arraycopy(c, 0, ct, 0, l);// 保持其他元素位置不变
				allCombString(c, s + 1);
				moveBack(c, i, s);  //既然改变了位置，那就再改回来
			}
		}
	}

	public static void moveToHead(char[] c, int id, int s) {
		if (id > s && id < c.length) {
			char temp = c[id];
			for (int i = id; i > s; i--) {
				c[i] = c[i - 1];
			}
			c[s] = temp;
			//println(c);
			//t++;
		}
	}
	public static void moveBack(char[] c, int id, int s) {
		if (id > s && id < c.length) {
			char temp = c[s];
			for (int i = s; i < id; i++) {
				c[i] = c[i+1];
			}
			c[id] = temp;
			//println(c);
			//t++;
		}
	}

	public static void println(char[] c) {
		System.out.println(new String(c));
	}
}
2 楼 tq02ksu 2010-12-03  
pengmj 写道
如“abc”输出结果为：“abc”,“acb”,“bac”,“bca”,“cab”,“cba”

public class AllCombString {
public static int t;//组合个数

public static void main(String[] args) {
  String str = "123";
  char[] c = str.toCharArray();
  println(c)
  t++;
  allCombString(c,0);
  System.out.println(t);
}
public static void allCombString(char[] c,int s){
  int l = c.length;
  if(l-s==2){
   char temp = c[l-1];
   c[l-1] = c[l-2];
   c[l-2] = temp;
   println(c);
   t++;
  }
  else{
   for(int i=s;i<l;i++){
    moveToHead(c,i,s);
    char ct[] = new char[l];
    System.arraycopy(c, 0, ct, 0, l);//保持其他元素位置不变
    allCombString(ct,s+1);
   }
  }
}

public static void moveToHead(char[] c,int id,int s){
  if(id>s&&id<c.length){
   char temp = c[id];
   for(int i=id;i>s;i--){
    c[i] = c[i-1];
   }
   c[s] = temp;
   println(c);
   t++;
  }
}

public static void println(char[] c){
  System.out.println(new String(c));
}
}
输出结果：

123
132
213
231
321
312
6

设计思路：

1、n个字符，顺序选取其中第1个；

2、在剩下的n-1个字符中，再选取其中的第1个；

3、若剩余的字符只剩下2个，则这两个字符交换位置；若不是，则继续第2步。

4、这是一个典型的递归，无论有多少个字符，到最后只需交换最后两个字符即可。

5、为了能按顺序选取字符（因为递归之后会影响字符的顺序，如：“abcd”经过第一轮递归之后变成“adbc”,这时再执行第2步的话，取到的字符是“d”，而不是“b”），所以这里使用了数组拷贝，for循环不受递归的影响。（这个问题想了老半天，暂时只能用这种方法，即使效率比较低）。

6、组合的个数是字符个数的阶层，如“abc”,组合个数为3!=6

不知道大家有没有更好的方式

楼主C/C++程序员出身.
鉴定完毕
1 楼 printf 2010-12-03  
这个叫排列吧。。。
有很多现成的全排列生成算法，网上一搜一大把
发表评论

您还没有登录,请您登录后再发表评论

相关推荐

Magicbox
Global site tag (gtag.js) - Google Analytics