黑马程序员技术交流社区

标题: 一个编程的题目，，求高手指点 [打印本页]

作者: awkflf11 时间: 2014-5-4 14:47
标题: 一个编程的题目，，求高手指点

编程列出一个字符串的全字符组合情况，原始字符串中没有重复字符,
例如：原始字符串是"abc"，

打印得到下列所有组合情况：

"a" "b" "c"
"ab" "bc" "ca" "ba" "cb" "ac"
"abc" "acb" "bac" "bca" "cab" "cba"

作者: skill20 时间: 2014-5-4 15:16
本帖最后由 skill20 于 2014-5-4 16:37 编辑

//取子串就可以了。

<div class="blockcode"><blockquote>String st = "asdsfds";
for (int a = 0; a < st.length() ; a++)
{
for (int x = 0 ,y = st.length()-a; y != st.length() + 1 ; x++ ,y++ )
{
String s = st.substring(x,y);
}
}

复制代码

作者: Lin0411 时间: 2014-5-4 16:13

skill20 发表于 2014-5-4 15:16
//取子串就可以了。

这也行？

作者: Lin0411 时间: 2014-5-4 16:14

这个函数只给出了打出固定字符串的所有排列。
public class test
{
public static void main(String[] args)
{
perm("abc".toCharArray(), 0);
}
public static void perm(char[] chs,int k)
{
if(k == chs.length)
{
for(int i=0; i<chs.length; i++)
{
System.out.print(chs[i]);
}
System.out.print(" ");
}
else
{
for(int i=k; i<chs.length; i++)
{
swap(chs, i, k);
perm(chs, k+1);
swap(chs, i, k);
}
}
}
public static void swap(char[] chs,int i,int j)
{
char tem = chs[i];
chs[i] = chs[j];
chs[j] = tem;
}
}

复制代码

作者: skill20 时间: 2014-5-4 16:33

Lin0411 发表于 2014-5-4 16:13
这也行？

试试嘛。

作者: Lin0411 时间: 2014-5-4 16:42

skill20 发表于 2014-5-4 16:33
试试嘛。

如果是输出s的话貌似不对啊

作者: skill20 时间: 2014-5-4 16:50

Lin0411 发表于 2014-5-4 16:42
如果是输出s的话貌似不对啊

咋不对了？你先给 S打印下嘛，看看能不能取出子串，可与的话弄个返回值就哦了。

作者: Lin0411 时间: 2014-5-4 17:10

这下应该完整了。
public class test
{
public static void main(String[] args)
{
showPermString("abcd");
}
public static void showPermString(String str)
{
for(int i=1; i<=str.length(); i++)
{
List<String> list = new ArrayList<String>();
perm(list, str.toCharArray(), 0, i);
System.out.println(list);
}
}
public static void perm(List<String> list,char[] chs,int k,int len)
{
if(k == chs.length)
{
String string = String.valueOf(chs, 0, len);
if(!list.contains(string))
list.add(string);
}
else
{
for(int i=k; i<chs.length; i++)
{
swap(chs, i, k);
perm(list,chs, k+1,len);
swap(chs, i, k);
}
}
}
public static void swap(char[] chs,int i,int j)
{
char tem = chs[i];
chs[i] = chs[j];
chs[j] = tem;
}
}

复制代码

作者: Lin0411 时间: 2014-5-4 17:13

skill20 发表于 2014-5-4 16:50
咋不对了？你先给 S打印下嘛，看看能不能取出子串，可与的话弄个返回值就哦了。 ...

它是要输出所有排列。小子愚钝，能够给个完整代码。

作者: skill20 时间: 2014-5-4 17:15

Lin0411 发表于 2014-5-4 17:13
它是要输出所有排列。小子愚钝，能够给个完整代码。

:L看错了，以为要子串，我错了。

作者: 刘晶 时间: 2014-5-4 20:39
import java.util.*;
public class Test{
      static int n,count = 0;
      static char[] array = { 'a', 'b', 'c' };
      static LinkedList <char[]> list = new LinkedList<char[]> ();
      static int[] indexs = new int[3];
      static int len = array.length;

      public static void main(String[] args){
                              getSub ();

               for ( char[] cs : list )    //遍历list
               {
                     //n++;
                     // if(n%3!=0)

                  System.out.println(cs);
                     // else System.out.println(cs);
            }
         }

         private static LinkedList<char[]> getSub ()    //获取
         {
               while (count <= len){
                  recursionSub (-1);
                  count++;
               }
               return list;
         }

         private static LinkedList <char[]> recursionSub ( int start )
         {
                           start++;

                           if (start > count - 1)
                                 {
                                 return null;
                                 }
                           for ( indexs[start] = 0; indexs[start] < len; indexs[start]++ )
                                 {
                                          recursionSub (start);
                                          if (start == count - 1)
                                                   {
                                                         char[] temp = new char[count];
                                                         for ( int i = count - 1; i >= 0; i-- )
                                                                  {
                                                                           temp[start - i] = array[indexs[start - i]];
                                                                  }
                                                         boolean flag = true;
                                                         for ( int i = 0; i < temp.length; i++ )
                                                                  {
                                                                           for ( int j = i+1; j < temp.length; j++ )
                                                                                 {
                                                                                          if (temp[i] == temp[j])
                                                                                                   {
                                                                                                         flag = false;
                                                                                                         break;
                                                                                                   }
                                                                                 }
                                                                  }
                                                         if (flag)
                                                         {
                                                                  list.add (temp);
                                                         }
                                                   }
                                 }
                           return list;
      }

}

可以共同探讨一下，这个也不是很完美

作者: 李维奥 时间: 2014-5-4 21:17

public class StringDemo {

/**
   * @param args
   */
public static void main(String[] args) {
String s = "abcdefg";
char[] ch = s.toCharArray();
turn(ch);

}

public static void turn(char[] ch) {
int len = ch.length;
for (int k = 0; k < len; k++) {
for (int i = 1; i <= len; i++) {
for (int j = k; j < i; j++) {
System.out.print(ch[j]);
}
System.out.print("  ");
}
System.out.println();
}

}
}
做出来了但是思维有些混乱，就没有写注释

作者: 李维奥 时间: 2014-5-4 21:28

李维奥发表于 2014-5-4 21:17
public class StringDemo {

/**

不好意思我看错题了。。。。

作者: awkflf11 时间: 2014-5-4 23:20

李维奥发表于 2014-5-4 21:17
public class StringDemo {

/**

首先多谢了，
但答案不完全对
如果是abc

结果是
a  ab  abc
  b  bc
c
少 bca,bac, cab,cab

作者: Lin0411 时间: 2014-5-4 23:29

李维奥发表于 2014-5-4 21:17
public class StringDemo {

/**

貌似不对啊。

作者: 赵小豪 时间: 2014-5-5 00:05

public class Test_02 {
public static void main(String[] args) {
char ch[] = { 'a', 'b', 'c' };
for (int i = 0; i < ch.length; i++) {
System.out.print("" + ch[i] + '\t');
for (int j = 0; j < ch.length; j++) {
if (i != j) {
System.out.print("" + ch[i] + ch[j] + "\t");
}
for (int k = 0; k < ch.length; k++) {
if (i != j && i != k && j != k) {
System.out.print(ch[i] + "" + ch[j] + ch[k] + "\t");
}
}
}
}
}
}

复制代码

作者: ς高眼光の目标 时间: 2014-5-5 02:28
看看递归就会明白了其他的自己领悟去这样对你才有好处

作者: fei_xiong 时间: 2014-5-5 08:06

public class Test8 {
public static void main(String[] args)
{
//建立需要排列的字符串
String str = "abc";
//建立一个集合用于存储所排列的字符串，因为不要重合的，所以用Set集合
TreeSet<String> tsSet=new TreeSet<String>();
//将字符串转换为字符数组传入要进行递归的方法中。
permutation(tsSet,str.toCharArray(),0);
//在递归完成后，集合中已经有了所有的排列，打印。
System.out.println(tsSet.toString());
}
public static void permutation(Set<String> s,char[] str, int x) {
//定义递归的完结条件
if (x >= str.length)
return;
//用于对递归中取到的排列进行存储
if (x == str.length - 1) {
s.add(new String(str));
} else {
//建立一个循环，进行循环读取
for (int y = x; y < str.length; y++) {
//在循环到第二次的时候，开始转换首字母，以便递归
char temp = str[y];
str[y] = str[x];
str[x] = temp;
//将变换了首字母的字符数组传入，进行递归，取得与与原字符串相同长度的所有排列
permutation(s,str, x + 1);
//去掉首字母进行递归，取得长度减一的字符串的所有排列，
//因为不断递归，所以最终会取到单一的字符为止，如此则取到了所有的排列
permutation(s,Arrays.copyOfRange(str, 1, str.length),0);
//将字符数组变回原样，保证每次递归时，都会变换首字母（x和y转换）
temp = str[y];
str[y] = str[x];
str[x] = temp;
}
}
}
}

复制代码

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

[a, ab, abc, ac, acb, b, ba, bac, bc, bca, c, ca, cab, cb, cba]

思考：可以首先将以a开头的所有排列找出，然后在找出以b开头的排列...如此可以用到递归的方法。

欢迎光临黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2