一个算法问题，求思路和解答

今天碰到一个问题：排列问题，想了很久没思路，网上只找到组合的，没找到排列的，求解答！问题如下：
有3个数字：1  2  3 ，编写程序，打印出以上3个数字任意多个组成的任意排列。打印出来的结果应当如下：
1  2  3
12  13  23  21  31  32
123  132  213  231  312  321
小弟实在没有什么思路，求思路，最好能附上代码，感激不尽！

Alan_Kwan · Alan_Kwan

对于这道题我只会一路for。。这样毫无扩展性的代码。。

毅心缘 · 毅心缘

楼主请看

package cm.heima;
public class Demo {
// -----中间方法
public static String[] mid(String[] str, String[] middle) {
// 原来已经复制过了，现在要定义剩下的数组，以便接下来复制
String[] end = new String[(middle.length * (str.length - middle[0]
.length()))];
// 定义end指针pp
int pp = 0;
// 双重for 循环赋值
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)];
// 定义end 下标指针从0开始复制
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;
}
/**
* 打印数组
*
* @param str
*/
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[] str1 = { "1", "2", "3" };
// System.out.println("count=" + Test8.count(str1.length));
// 转换
show(turn(str1));
}
}

复制代码

肖德茂 · 肖德茂

毅心缘发表于 2014-6-24 18:32
楼主请看

好的，回头慢慢看~~~强大~~~~~~~~~~~~

_qishiwobusha_ · _qishiwobusha_

黑马有一个基础测试题  和这个题目类似

楼主你看看，参考一下。

/**
* 第7题  编程列出一个字符串的全字符组合情况，原始字符串中没有重复字符。
* 例如：原始字符串是"abc"，打印得到下列所有组合情况：
*"a" "b" "c"
*"ab" "bc" "ca" "ba" "cb" "ac"
*"abc" "acb" "bac" "bca" "cab" "cba"
* @author Administrator
*/
/**
* 思路是先求字符串的所有组合情况，再把每一种的组合情况的所有排列情况求出
*/
public class Test7 {

public static ArrayList<char[]> list =new ArrayList<char[]>();//保存字符串的所有组合情况
public static ArrayList<String> list2 = new ArrayList<String>();//保存字符串的全字符组合
public static void main(String[] args) {
String str = "abc";
Stack<Character> s = new Stack<Character>();
selectChar(str.toCharArray(),0,str.length(),s);
for(int i = 0;i<list.size();i++){
char[] c = list.get(i);
permutation(c,0,c.length - 1);
}
for(int j = 0;j<list2.size();j++){
System.out.println(list2.get(j));
}
}
/**
* 获得字符串 str 的全部组合情况
* 例如 "abc"  ---> "abc" "ab"  "a"  "ac"  "bc" "b" "c"
* 并把全部组合情况保存到 ArrayList list中
* @param str
* @param begin
* @param m
* @param select
*/
public static void selectChar(char[] str,int begin,int m,Stack<Character>select){
if(m == 0){
Object[] Ochars = select.toArray();
char []chars = new char[Ochars.length];
for(int i = 0;i < Ochars.length;i++){
chars[i] = (Character)Ochars[i];
}
list.add(chars);
return;
}
select.push(str[begin]);
selectChar(str,begin + 1,m - 1,select);
select.pop();
selectChar(str,begin + 1  ,m - 1,select);
}
public static void swap(char[]str,int i,int j){
char temp = str[i];
str[i] = str[j];
str[j] = temp;
}
/**
   * 求一个字符串的所有排列情况
   * @param str
   * @param begin
   * @param end
   */
public static void permutation(char[] str,int begin,int end){
if(begin == end){
list2.add(new String(str));
return;
}
for(int j=begin;j<=end;j++){
swap(str,begin,j);
permutation(str,begin + 1,end);
swap(str,begin,j);
}

}
}

火线风 · 火线风

简单的实现方法可以用递归思想，还需要代码的话回复一下

caohaikuan · caohaikuan

学习了！

fantacyleo · fantacyleo

本帖最后由 fantacyleo 于 2014-6-26 00:39 编辑

写了一个深度优先搜索的算法，效率不高，但正确性可以保证，希望对楼主有帮助。

public class Permute {
static int[] used; // 记录某个下标是否已经在排列中
static char[] chars; // 用户输入的字符串拆成单个字符，保存于此
static char[] result; // 保存一个排列结果
public static void main(String[] args) {
if(args.length != 1) // 要求在命令行输入一个字符串
System.out.println("Usage: java Permute abc");
else
calPermutation(args[0]);
}
static void calPermutation(String s) {
chars = s.toCharArray();
int i;
for(i = 1; i <= chars.length; i++) {
used = new int[chars.length];
result = new char[i];
deepFirstSearch(i, 0);
System.out.println();
}
}
static void deepFirstSearch(int len, int index) {
if(len == index) // 达到排列长度要求，打印一次排列的结果
{
int i;
for(i = 0; i < result.length; i++)
System.out.print(result[i]);
System.out.print(" ");
}
else
{
int i;
for(i = 0; i < chars.length; i++) // chars数组下标
{
if(used == 0) // 如果该下标尚未使用过
{
used[i] = 1; // 标记为已使用
result[index] = chars[i]; // 将字符放入结果数组
deepFirstSearch(len, index + 1); // 递归完成余下的排列
used[i] = 0; // 回溯
}
}
}
}
}

复制代码

fantacyleo · fantacyleo

上面的代码可以接收任何长度的字符串（当然太长了会很慢:lol ）。以"123"为例，预期结果：
1  2  3
12  13  23  21  31  32
123  132  213  231  312  321

思路是：
1. calPermute方法中的循环每次输出一行的结果
2. 每一行的排列由deepFirstSearch方法算出。例如要输出123，(1)把1放入结果数组，标记为已使用，递归 (2)递归再从1开始，由于1已经使用，就看2，2尚未使用，于是标记并放入结果数组，再次递归 (3) 递归发现1，2均已使用，3未使用，于是将3放入结果数组，此时排列长度达到要求，输出此排列。

零下_1° · 零下_1°

fantacyleo 发表于 2014-6-26 00:29
写了一个深度优先搜索的算法，效率不高，但正确性可以保证，希望对楼主有帮助。

高手啊！

肖德茂 · 肖德茂

fantacyleo 发表于 2014-6-26 00:29
写了一个深度优先搜索的算法，效率不高，但正确性可以保证，希望对楼主有帮助。

好的~~~~谢谢谢谢！！！！

肖德茂 · 肖德茂

_qishiwobusha_ 发表于 2014-6-25 16:55
黑马有一个基础测试题和这个题目类似

楼主你看看，参考一下。

很好，谢谢谢谢！！！！！

科篮 · 科篮

刚好也遇到这题，受教了

黄梁梦想享 · 黄梁梦想享

晕了.........

Sakuratossi · Sakuratossi

找了一下网上的代码，感觉这个代码算是稍微简单明了的了。。。但还是看的云里雾里的，分享一下给有同疑问的们：
public class Test0718 {
static char[] chars="abcd".toCharArray();
public static void main(String[] args) {
      for(int i=0;i<chars.length;i++){
         //取得每一个字符
         List<Integer> list=new ArrayList<Integer>();
         list.add(i);
         play(list);
      }
}
//使用递归，每次加上列表中不存在的一个字符
private static void play(List<Integer> list){
      print(list);
      for(int i=0;i<chars.length;i++){
         if(!list.contains(i)){
            List<Integer> temp=new ArrayList<Integer>(list);
            temp.add(i);
            play(temp);
         }
      }
}
//打印列表内容
private static void print(List<Integer> list){
      for(Integer i:list)
         System.out.print(chars[i]+"");
      System.out.println();
}
}

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

一个算法问题，求思路和解答

16 个回复

点评

黑马骑士勋章