关于组合问题之递归解决

原始字符串是"abc"，打印得到下列所有组合情况：
"a" "b" "c"
"ab" "bc" "ca" "ba" "cb" "ac"
"abc" "acb" "bac" "bca" "cab" "cba"
代码：
public static String str="abc";
   public static void show(int current_recur, String temp) {
         if (current_recur < str.length()) {
            for (int i = 0; i < str.length(); i++) {
                  if (!(temp.contains(str.substring(i, i + 1)))) {
                     System.out.print(temp + str.substring(i, i + 1) + " ");
                     show(current_recur + 1,
                              new String(temp + str.substring(i, i + 1)));
                  }
            }
         }
   }

老二 · 老二

如果把字符串转换成字符数组，应该还有好的解法，更清晰。

老二 · 老二

求大神，给思路

、海 · 、海

看得很累！

老二 · 老二

、海发表于 2014-6-20 21:11
看得很累！

是啊，一些嵌套，几层for循环

java木 · java木

这个我觉得很难，我想了十个小时，尽然还没弄出来。发现用递归来组合，只要超过8个几乎要算很久。

Aron · Aron

给你一个我的方法有注释看你理解不不懂得就问我

//初始化一个字符串
private static String s="abcd";
//把这个字符串中每个字母放入一个数组中
public static void intoArr(String s,String[] array){
for(int i=0;i<s.length();i++){
array[i]=String.valueOf(s.charAt(i));
}
}
private static String[] array =new String[s.length()]; //初始化一个数组
private static ArrayList<String> pp = new ArrayList<String>(); //定义一个集合用来放最后组合的字符数组
public static void main(String[] args)
{
intoArr(s,array); //给array赋值
execute(); //执行
}
//输出和递归调用
public static void execute()
{
ArrayList<String> list = new ArrayList<String>();
//创建包含字符串数组内容的list集合
list.addAll(Arrays.asList(array));
for (int len = 1; len <= array.length; len++)
{
for(String a:pp){
System.out.print(a+" ");
}
if(len!=1){//第一次不换行
System.out.println();
}
pp.clear();
digui(list, "", len);
}
for(String a:pp){
System.out.print(a+" ");
}
}
//递归得到组合
public static void digui(ArrayList<String> list, String result, int len)
{
for (int i = 0; i < list.size(); i++)
{
String str = list.get(i);
result += str;
if (result.length() == len)
{
pp.add(result); //把组合放入pp中
}
else
{
ArrayList<String> copylist = (ArrayList<String>) list.clone();//克隆一个一样的字符串数组
copylist.remove(str);//把这个复制的字符串数组中的str元素去掉
digui(copylist, result, len);//再次调用递归
}
result = result.substring(0, result.length() - 1);//截取掉相对应的字符
}
}

复制代码

这个方法只适合字符串少如果太大 java会运行不了所以如果想实现快速的方法可能要换一种思想

qq474249147 · qq474249147

这么短？我写的是无限长度不重复字符串的全组合

黎志勇 · 黎志勇

本帖最后由黎志勇于 2014-6-21 07:06 编辑

睡前看到这题，睡觉时一直在想，老感觉不舒坦，就起床熬夜写出来了，不写完总睡不着，终于可以安心去睡觉了。

/*思路：
*1.题中所有组合，其实就是带顺序的“3选1”、“3选2”、“3选3”的所有组合；
*2.可以想象abc为三个球，有两个管子，一个用来存已选择的，一个用来存未选择的；
*3.所以可以定义两个字符数组，一个是已被选择的数组selected，一个是待选择的数组toSelect，只要操作这两个数组就OK了；
*4.一开始没选择，已选择数组长度为0，待选择数组长度为3；
*5.选一个字符放进已选择数组，这时已选择数组长度为1，待选择数组长度为2；
*6.每选择一次，打印已选择数组的序列；
*7.重复5、6步，直到未选择数组长度为0；
*
*/
public class Demo {
public static void main(String[] args) {
show("abc");
}
//把“选择”操作封装，使满足打印任意非重复字符串组合
public static void show(String str){
selectChar(new char[0],str.toCharArray());
}
//这个方法是对“选择”这个动作的抽象，对俩数组进行操作
private static void selectChar(char[] selected,char[] toSelect){
if(toSelect.length==0){//如果待选择数组长度为0，则退出选择操作
return;
}
//定义一个新的临时数组，作为新的“已选择数组”，注意新的数组比旧的长度增加1
char[] tempSelected = updateSelectedCharArray(selected);//
char[] tempToSelect;//新的待选择数组
for(int i=0;i<toSelect.length;i++){
tempSelected[tempSelected.length-1]=toSelect[i];//把选择的字符放进新“已选择数组”最后一位
tempToSelect=updateToSelecteCharArray(toSelect, i);//更新“待选择数组”
System.out.println(String.valueOf(tempSelected));//打印“已选择数组”
selectChar(tempSelected, tempToSelect);//重复选择操作
}
}
//这个方法用来更新选择一个字符时，“已选择数组”的内容
private static char[] updateSelectedCharArray(char[] array){
char[] temp = new char[array.length+1];
for(int i =0;i<array.length;i++){
temp[i]=array[i];
}
return temp;
}
//这个方法用来更新选择一个字符后，“待选择数组”的内容
private static char[] updateToSelecteCharArray(char[] array,int index){
char[] temp = new char[array.length-1];
for(int i =0,j=0;i<array.length;i++){
if(i!=index){
temp[j++]=array[i];
}
}
return temp;
}
}

复制代码

老二 · 老二

黎志勇发表于 2014-6-21 06:59
睡前看到这题，睡觉时一直在想，老感觉不舒坦，就起床熬夜写出来了，不写完总睡不着，终于可以安心去睡觉了 ...

嗯嗯，向你学习

黎志勇 · 黎志勇

老二发表于 2014-6-21 11:53
嗯嗯，向你学习

不过没有这个的输出顺序不像题目标的那样，先输出一个的，再输出两个的，最后三个的，不知道有没有要求输出顺序一定要字符个数要从小到大了。

crazystraw · crazystraw

下面的是我的思路，代码和楼主一样

/*
* 思路：
* 题目相当于要求一个字符串的所有子集（元素位置不相同视为不同子集），
* 此时想到了字符串的substring方法，首先要对怎么取子集进行思考。
* 可以先固定其中一个字符，此字符必然是其中一种组合，
* 然后取原字符串的任意一个字符，如果这两个字符不相同，那么这两个字符形成一个字符，也必然是原字符串的子集
* 然后固定这两个字符形成的字符串，再取原字符串的任意一个字符，如果与这两个字符仍然不同，
* 那么固定这两个字符再加上此字符仍然是所求的，继续固定这三个字符，之后继续循环，
* 如果字符长度等于题目所给字符串长度则停止，返回上一层循环。
* 步骤：
* 通过思路可以看出，该程序需要用到循环和递归的方法。
*
*/
public class Text7 {
public static String str = "abc";//定义一个静态的，可供调用的需要打印子集的原始字符串
public static void show(int length,String fixedStr){ //定义接收两个变量的功能函数
//固定的字符串的长度需要小于原始字符串的长度，如果大于，则此循环或者递归中的循环结束，初始固定的字符串视为空
if(length<str.length()){
for(int x = 0;x < str.length();x++){ //x为原字符串一个子集的起始角标位
if(!fixedStr.contains(str.substring(x, x+1))){//如果固定的字符串不含有原字符串的其中一个单元素子集的元素
System.out.println(fixedStr+str.substring(x,x+1));//把固定的字符串加上原字符串的第x个元素合在一起打印
show(length+1,new String(fixedStr+str.substring(x,x+1)));//再把打印的这个元素和它的长度作为变量进行递归操作
}
}
}
}
public static void main(String[] args){
show(0,new String());//可以视为传入一个空字符串，字符串为0长度的参数调用函数打印原始字符串的全字符组合。
}
}

复制代码

老二 · 老二

crazystraw 发表于 2014-6-21 13:22
下面的是我的思路，代码和楼主一样

你的注释多，不错

lwh316658735 · lwh316658735

今天写的可以参考下

import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Set;
import java.util.TreeSet;
class ForTest3 {
public static void main(String[] args) {
StringBuffer str = new StringBuffer("abc");
Set<String> set = new TreeSet<String>();
char[] ch = str.toString().toCharArray();
print(ch, new StringBuffer(), set, 0);
System.out.println();
System.out.println("----------------");
Set<String> set2 =quChongFu(set);
Iterator<String> it2 = set2.iterator();
while (it2.hasNext()) {
System.out.print(it2.next() + ",");
}
}
//去掉集合中重复的元素
/*
* set:需要除去重复字符元素的集合
*/
public static Set<String> quChongFu(Set<String> set) {
Set<String> set2 = new TreeSet<String>();
Map<Character, Integer> map = null;
Iterator<String> it2 = set.iterator();
int count;
while (it2.hasNext()) {
map = new HashMap<Character, Integer>();
count = 1;
boolean flag = false;
String str = it2.next();
char[] ch = str.toCharArray();
for (int i = 0; i < ch.length; i++) {
if (!map.containsKey(ch[i])) {
count = 1;
map.put(ch[i], count);
}
if (map.containsKey(ch[i])) {
map.put(ch[i], count);
count++;
}
}
// System.out.println(map);
for(int j=0;j<ch.length;j++){
if(map.get(ch[j])>1){
flag=false;
//System.out.println("r");
break;
}else
flag=true;
}
if(flag){
// System.out.println("s");
set2.add(str);
}
}
//System.out.println(set2);
return set2;
}
//利用递归打印所有组合
/*
* ch:需要打印在组合的字符数组
* str:子字符串缓存，每个组合临时保存的变量
* set:最后存入的集合
* cout:递归的层数，和ch参数的（长度）相等
*/
public static void print(char[] ch, StringBuffer str, Set<String> set,
int count) {
//递归一层自加一次
count++;
//当递归层数大于字符数组长度时退出
if (count > ch.length) {
return;
}
for (int i = 0; i < ch.length; i++) {
//当前字符添加到缓存变量中
str.append(ch[i]);
//打印所有组合，包括重复的
System.out.print(str.toString() + ",");
//将缓存变量中的数据转换成字符串存入集合中
set.add(str.toString());
//进入下一层，也就是字符数组的下一个字符
print(ch, str, set, count);
//删除上次保存的最后一个字符，避免了字符重复
str.deleteCharAt(str.length() - 1);
}
}
}

复制代码

1017161726

好高深的赶脚。。

帐号		自动登录	找回密码
密码			加入黑马

关于组合问题之递归解决

14 个回复

黑马骑士勋章