针对如"123456"之类的任意字符序列，输出它们所有的排列组合 .

思想：针对排列问题，应该将每个位置上可能出现的情况列出来，如有四个不同字符(暂时不考虑有相同情况)，那么第一个位置就有四种可能的情况，当第一个位置确定后，第二个位置就只有三种情况，依次类推，最后一个位置只有一种情况，这个对于学过排列组合的人来说，很好理解，关键在于怎样用程序实现呢？

根据上面的分析我们只要挨个把每个位置上出现的字符确定下来，那么这个序列就确定下来了，现在关键是我们针对某个位置出现的情况应该怎样确定呢？比如第一个位置有4种情况，而且每个位置上的字符不相同，那么就可以用整体左移或者右移一位，这样该位置就会出现一种不同的情况，为了要出现四种情况，那么可以用一个循环来控制，直至四种情况都出现。这样该置出现的每种情况也就是确定了这个位置出现的字符。

接下来我们就应该确定第二个位置的字符，第二个位置应该出现三种不同的情况了，也就是从这个位置到最后一个位置上的所有字符作为一个整体向左或右移一位，直至三种情况都出现，也就是有三个位置发生变化，这时会发现这种动作与确定第一个位置使用了相同的方法来确定该位置出现的每种情况，只是少了一位，这就是将一个大的问题转换成一个小一点的问题来解决，那么依次类推，第三个位置的解决办法与第二个位置所使用的方法相同，只是又少移一位(确定的位置不用移动)，也就是只有两个位置发生变化，到了最后一个位置了，也就是只有一个位置在变化了，不过怎么变，这个位置上也就只剩下一种情况了，换句话说，这个位置不变了，所有位置上的字符都确定了，那么这时就该输出所有位置上的字符了。

上面这段解释主要是为了引出递归这个思想，我对递归的理解是：对于一个大的问题，可以将它转换成一个较小的问题，然后将这个较小的问题再转换成一个更小的问题来处理，直到最后那个最小的问题得到确定的答案为止，然后再根据这个答案依次回推，而对每个问题都采用相同的方法来处理。下面这个程序的思路是反过来的，也就是先确定最后一个位置出现的情况，然后再确定倒数第二个位置的情况，直到第一个位置确定后输出：



import java.util.Scanner;

public class Permute {

    static int count = 0;
    public static void main(String[] args) {
        System.out.println("please input a String:");
        Scanner in = new Scanner(System.in);
        String str = in.nextLine();
        Permute p = new Permute();
        System.out.println(str+"出现的所有排列如下：");
        p.permute(str);
        System.out.println();
        System.out.println("总共有"+count+"种排列");
    }

    private void permute(String str) {
        this.permute(str.toCharArray(), 0, str.length() - 1);
    }
//从最后一个位置向前，依次对每个位置上可能出现的字符进行确定(如字符数组是{a,b,c,d},那么最后一个位置可能出现4种情况，确定好第四位置上的字符后，第三个位置可能出现三种情况依次类推)
    private void permute(char[] charArray, int low, int high) {
        int i;
        if (high == low) {//如果是到了第一个位置(low是第一个位置的索引)，或者只有一个字符，那么应该输出此字符串
            String str = "";
            for (i = 0; i < charArray.length; i++) {
                str += charArray[i];
            }
            System.out.print(str+"  ");
            count++;
        } else {
            for (int j = low; j <= high; j++) {//将某个位置上可能出现的字符进行遍历(如最后一个位置可能出现high+1种情况)
                for (i = low; i < high; i++) {//将第low位置上的字符移到第high位置上
                    char temp = charArray[i];
                    charArray[i] = charArray[i + 1];
                    charArray[i + 1] = temp;
                }
                permute(charArray, low, high - 1);//当第high位置上的字符确定后，就应该确定第high-1位置上的字符。
            }
        }
    }
}

评论

2 楼 FLFLFLFLFLS 2012-03-16  

很实用的，
java代码下载了，在eclipse中运行了一下，
很有效果的[size=x-large][/size]

1 楼 FLFLFLFLFLS 2012-03-16  

很实用的，
java代码下载了，在eclipse中运行了一下，
很有效果的[size=x-large][/size]