`
pengmj
  • 浏览: 24313 次
  • 性别: 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  
这个叫排列吧。。。
有很多现成的全排列生成算法，网上一搜一大把
发表评论

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

相关推荐

    输入一个字符串，输出所有该字符串的组合情况

    NULL 博文链接：https://gaoquanyang.iteye.com/blog/1522697

    Java语言程序设计(第3版)第06章-字符串.pptx

    6.1.1 字符串基本操作 Java语言程序设计(第3版) 问题描述 编写一个方法判断字符串是否是回文串。 public static boolean isPalindrome(String s) 思路：取出字符串的第一个和最后一个比较，若不相同，程序结束，...

    编写一个JAVA程序，定义一个Student类

    方法public String toString（），把Student类的对象的所有属性信息组合成一个字符串以便输出显示。编写一个Java Application程序，创建Student类的对象，调用上述方法进行验证并实现相应输出。

    积分java源码-JavaCalculus:用于字符串表达式、符号微分、符号积分以及代数和函数组合(FoG)的Java微积分数学包

    表达式接口：获取字符串方程的值。 最初取自 StackOverflow。 由 StackOverflow 用户编写的代码：Boann 和 由 StackOverflow 用户编写的代码：Mike Scholtes Boann 的代码是免费的 但被我广泛修改。 输入：Java 字符...

    Java开发技术大全(500个源代码).

    ArrayString.java 字符串数组 assignTwoDime.java 为二维数组赋值 getMaxElem.java 获取数组中的最大元素 incCapicity.java 演示StingBuffer的容量增长 SortDemo.java 排序示例 travelTwoDime.java 遍历二维...

    java初学者必看

    5.1.3 StringBuffer创建字符串 5.2 连接字符串 5.2.1 与字符串的连接 5.2.2 与其他数据类型的连接 5.3 String字符串操作 5.3.1 基本操作 5.3.2 比较 5.3.3 转化 5.3.4 查找 5.3.5 截取拆分 5.3.6 替换或...

    实验03 Java面向对象编程1.doc

    ○4创建public型的toString方法，把该类的各域信息（学号，姓名，性别和年龄）组合成一个字符串，如：“141308008，小明，男，20岁”； ○5创建Student类的子类CollegeStudent类（大学生类），添加域：专业，静态域...

    JAVA语言程序设计【高清版】.pdf

    107 6.1　数组　107 6.1.1　数组说明和初始化　107 6.1.2　数组的使用　114 6.2　容器和字符串　118 6.2.1　容器　118 6.2.2　字符串　119 习题　123 第7章　Java语言中的异常　126 7.1　异常示例　126 7.2　异常...

    JAVA基础课程讲义

    字符串（java.lang.String类）的使用 90 字符串相等的判断 92 思考作业 93 上机作业 94 第四章 异常机制 95 导引问题 95 异常（Exception）的概念 96 异常分类 96 Error 97 Error和Exception的区别 97 Exception 97 ...

    JAVA入门1.2.3：一个老鸟的JAVA学习心得 PART1（共3个）

    9.2.6 在字符串中查找子字符串或字符 226 9.2.7 替换字符串中的内容 226 9.2.8 String对象——磐石刻字 227 9.3 String类的最佳拍档——StringBuffer类 227 9.3.1 StringBuffer：专业操纵字符 228 9.3.2 String...

    Java优化编程（第2版）

    4.2.2 字符串的length()方法与性能优化 4.2.3 tochararray()方法与性能优化 4.2.4 字符串转化为数字 4.3 系统i/o类 4.3.1 java语言中输入/输出流 4.3.2 通过系统缓冲流类提高i/o操作效率 4.3.3 通过自定制缓冲区提高...

    Java入门1·2·3：一个老鸟的Java学习心得.PART3（共3个）

    9.2.6 在字符串中查找子字符串或字符 226 9.2.7 替换字符串中的内容 226 9.2.8 String对象——磐石刻字 227 9.3 String类的最佳拍档——StringBuffer类 227 9.3.1 StringBuffer：专业操纵字符 228 9.3.2 String...

    Java开发实战1200例(第1卷).(清华出版.李钟尉.陈丹丹).part3

    实例074 将字符串的每个字符进行倒序输出 94 实例075 获取字符串中汉字的个数 94 实例076 批量替换某一类字符串 95 实例077 把异常与错误信息显示到窗体中 97 实例078 从字符串中分离文件路径、 文件名及扩展名 98 ...

    Java2核心技术.part5

    12．4．2字符串记号处理器和带分隔符的文本 12．4．3读取带允隔符的输入 12．4．4 StringBuilder类 12．4．5随机存取流 12．5对象流 12．5．1存储可变类型的对象 12．5．2理解对象序列化文件格式 12．5．3...

    Java面试宝典-经典

    3、编写一个截取字符串的函数，输入为一个字符串和字节数，输出为按字节截取的字符串，但要保证汉字不被截取半个，如“我ABC”，4，应该截取“我AB”，输入“我ABC汉DEF”，6，应该输出“我ABC”，而不是“我ABC+汉...

    Java面试宝典2010版

    3、编写一个截取字符串的函数，输入为一个字符串和字节数，输出为按字节截取的字符串，但要保证汉字不被截取半个，如“我ABC”，4，应该截取“我AB”，输入“我ABC汉DEF”，6，应该输出“我ABC”，而不是“我ABC+汉...

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