面白いアルゴリズム-文字列の全配列

1461 ワード

一、テーマ
文字列を入力し、その文字列のすべての配列を印刷します.例えば、文字列abcを入力します.文字a,b,cで並べられるすべての文字列abc,acb,bac,bca,cab,cbaが印刷される.
二、問題を解く構想
1つの文字列を2つの部分から構成されていると見なします.第1の部分はその最初の文字で、第2の部分は後ろのすべての文字です.
文字列全体の配列を求めると、2つのステップと見なすことができます.まず、最初の位置に現れる可能性のあるすべての文字、すなわち、最初の文字と後ろのすべての文字を交換することを求めます.このとき、後ろのすべての文字を2つの部分に分けます.後ろの文字の最初の文字と、この文字の後のすべての文字です.
これは実は典型的な再帰的な考え方です.
三、解題コード
public class Test {
    /**
     *   :       ,               。       abc。
     *        a、b、c             abc、acb、bac、bca、cab cba。
     *
     * @param chars         
     */
    public static void permutation(char[] chars) {
        //     
        if (chars == null || chars.length < 1) {
            return;
        }
        //       
        permutation(chars, 0);
    }

    /**
     *         
     *
     * @param chars        
     * @param begin        
     */
    public static void permutation(char[] chars, int begin) {
        //           ,       
        if (chars.length - 1 == begin) {
            System.out.print(new String(chars) + " ");
        } else {
            char tmp;
            //                ,                  
            for (int i = begin; i < chars.length; i++) {
                //           
                tmp = chars[begin];
                chars[begin] = chars[i];
                chars[i] = tmp;

                //        
                permutation(chars, begin + 1);
            }
        }
    }
}