编程列出一个字符串的全字符组合情况串中

田磊阳

本帖最后由官珺伟于 2014-1-7 18:23 编辑

编程列出一个字符串的全字符组合情况，原始字符串中没有重复字符
例如：
原始字符串是"abc"，打印得到下列所有组合情况
"a" "b" "c"
"ab" "bc" "ca" "ba" "cb" "ac"
"abc" "acb" "bac" "bca" "cab" "cba"

午夜b'Boy · 午夜b'Boy

这题有难度，用到递归算法，

class TurnStr
{
public static String[] mid(String[] str,String[] middle) //-----中间方法
{
String[] end =new String[(middle.length*(str.length-middle[0].length()))];
int pp=0;
for (int i=0;i<middle.length;i++)
{
for (int ii=0;ii<str.length;ii++)
{
if (middle[i].indexOf(str[ii])<0)
{
end[pp++]=middle[i]+str[ii];
}
}
}
return end;
}
public static String[] turn(String[] str) //-------------主方法
{
String[] end=new String[count(str.length)];
int pp=0;
System.arraycopy(str,0,end,pp,str.length);
pp+=str.length;
String[] middle =str;
for (int i=0;i<str.length-1;i++)
{
middle=mid(str,middle);
System.arraycopy(middle,0,end,pp,middle.length);
pp+=middle.length;
}
return end;
}
public static int count(int length) //---------------计数返回数组维数
{
if (length>1)
return length+length*count(length-1);
else
return 1;
}
public static void show(String[] str) //------------打印数组
{
for (String i : str)
{
System.out.print(i+"\t");
}
System.out.println();
}
public static void main(String[] args)
{
//String[] str={"A","B","C"};
String[] str1={"A","B","C","D"};
//TurnStr.show(TurnStr.turn(str));
System.out.println(TurnStr.count(str1.length)+"--------------------------------------");
show(turn(str1));
}
}

复制代码

小悠久 · 小悠久

import java.util.Scanner;
import java.util.TreeSet;

public class Test12 {
      public static void main(String[] args) {
            Scanner s = new Scanner(System.in);

            String str = s.next();
            System.out.println(str);

            s.close();
            show(str);


      }
      /**
      * 打印各种可能
      * @param str       str是给定的字符串
      */
      private static void show(String str) {
            TreeSet<String> set = saveInSet(new StringBuilder(str),0,new StringBuilder(),new TreeSet<String>());
            for (String s : set) {
                     System.out.println(s);
            }
      }
      /**
      * 返回集合，集合包含字符串所有字符的可能组合
      * @param str       给定字符串转换成的StringBuilder对象，主要是为了操作字符方便
      * @param count       计数，对第count进行排列组合
      * @param buff       暂存放某种可能
      * @param set       集合，去除重复元素，例如"aab"以第一个a开头会有aba，以第二个a开头也会有aba
      * @return             返回TreeSet集合
      */
      private static TreeSet<String> saveInSet(StringBuilder str, int count, StringBuilder buff, TreeSet<String> set) {
            for (int i = 0,len = str.length(); i < len; i++) {
                     //获取字符
                     char c = str.charAt(i);
                     //去掉原字符串的某个字符（保证某个字符不被重复利用）
                     str.deleteCharAt(i);
                     //缓存添加该字符
                     buff.append(c);
                     //将该种可能组合存入集合
                     set.add(buff.toString());

                     //str仍包含字符，则递归调用，开始取第二位字符
                     //若还有第三位则继续递归……以此类推
                     if (str.length() != 0) {
                              //count用于记录目前在进行排列组合的第count位
                              count++;
                              //递归
                              saveInSet(str,count,buff,set);
                              //第n位递归结束后，需要继续对n-1位排列，位数-1
                              count--;
                     }

                     //递归结束后，需要继续对n-1位排列，因此清除第n位的记录
                     buff.deleteCharAt(count);
                     //删除的字符插回str
                     str.insert(i, c);
            }
            //返回集合
            return set;

      }

}
这有详细的注释，你看下。

宋大人-专注 · 宋大人-专注

好好学习一下

沉默的爱 · 沉默的爱

这题真有点难啊！想了好久还是没想出来，为了进黑马，借鉴一下了！

LeaonButcher · LeaonButcher

这是我的解题思路，大致方向还是迭代。
public class Test6 {
private String originalStr; //从输入流中读取的字符串

/**
   * 获得集合，使用迭代进行
   * @param list
   */
private void getCollection(String strCollection){
//当迭代到子字符串和原始字符串相同长度时，迭代结束，返回
if(strCollection.length() == originalStr.length()){
return;
}else{
for(int i=0;i<originalStr.length();i++){ //循环遍历整个原始数组
if(strCollection.contains(String.valueOf(originalStr.charAt(i)))){ //判断子字符串是否宝海下标为i的原始字符串的字符，如果是就继续循环；没有执行else操作
continue;
}else{
strCollection +=originalStr.charAt(i); //将子字符串中没有的字符添加到子字符串中
System.out.println(strCollection); //打印输出
getCollection(strCollection); //进行下一轮迭代
strCollection = strCollection.substring(0, strCollection.length()-1); //将刚添加到子字符串中的字符去掉。注：我一开始没有考虑到这一步，一直出错
}
}
}
}

public static void main(String[] args) {
Scanner in = new Scanner(System.in);
Test6 test = new Test6();
test.originalStr = in.next();
test.getCollection("");
}

}

亲亲 · 亲亲

z这道题还真难，好好学习～！

郑众杰 · 郑众杰

谢谢，有收获

DSY · DSY

还没看到集合代码看的很辛苦

静水流华 · 静水流华

我也遇到这道题，来着看看

杜工 · 杜工

小悠久发表于 2014-1-6 17:41
import java.util.Scanner;
import java.util.TreeSet;

虽然列出了所有的组合，但是打印出来的有点凌乱。可以在show方法里面用for循环控制下打印的格式，当set中的String长度等于1、2、3时换行，另外再加上双引号就完美了。。。

15225159271

我试了一下，楼主的做法有点问题

马塔非耶 · 马塔非耶

String s = "def";
TreeSet<String> set = new TreeSet<>(new Comparator<String>() { //双列集合去重复
public int compare(String s1,String s2) {
int num = s1.length() - s2.length(); //先以长度判断,小的在前
return num == 0 ? s1.compareTo(s2) : num; //在以字典顺序判断;
}
});
for (int i = 0; i < s.length(); i++) { //第一位数
for (int j = 0; j < s.length(); j++) { //第二位数
for (int j2 = 0; j2 < s.length(); j2++) { //第三位数
set.add(s.charAt(j2) + ""); //将单个字符存进集合,它会自己去重复.
if(s.charAt(j2) == s.charAt(j) | s.charAt(j2) == s.charAt(i) | s.charAt(i) == s.charAt(j)) { //判断三个不能重复
continue; //重复就跳出
}else {
set.add(s.charAt(i) + "" + s.charAt(j)); //否则将两个字符的组合加进集合,它会自己去重复
set.add(s.charAt(j) + "" + s.charAt(j2) + s.charAt(i)); //将三个字符的组合加进集合,它会自己去重复
}

}
}
} //遍历集合
for (String string : set) {
System.out.print(string + " ");
}
}
}

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

编程列出一个字符串的全字符组合情况串中

评分

12 个回复

评分

评分