1

私は現在、0,1,2,3,4,5,6,7,8,9 の 100 万番目の辞書順列を見つけるように求める問題に取り組んでいます。一見すると、O(n^3)程度の複雑さを持つ非常に大雑把なソリューションを思いつきました。 

    public static String permute(char[] a){
        ArrayList<String> array = new ArrayList<String>(); 
        int counter = 1; 
        for (int i = 0; i < a.length; i++){
            array[counter] += a[i];
            for (int j = 0; j < i; j++){
            array[counter] += a[j];
                for(int k = a.length; k > i; k--){
                array[counter] += a[k];}counter++;}
        }
    }

コードは完全ではないかもしれませんが、1 つの数字が選択されてから配列の最後に移動するという考え方です。2 番目の配列は選択した数字の後ろに数字を作成し、3 番目の配列はその後に数字を作成します。これはひどいアルゴリズムのようで、このような過去のアルゴリズムを思い出しました。

    public static HashSet<String> Permute(String toPermute) {
        HashSet<String> set = new HashSet<String>();
        if (toPermute.length() <= 1 )
            set.add(toPermute);
        else {
            for (int i = 0; i < toPermute.length(); i++ )
                for (String s: Permute(toPermute.substring(0,i)+ toPermute.substring(i+1)))
                {
                    set.add(toPermute.substring(i,i+1)+s);}
        }
        return set;
    }

}

問題は、このアルゴリズムが順序付けられていないセットを使用することであり、100 万番目の順列を見つけるのに十分な順序になる方法がわかりません。また、 n回呼び出してからアンスタックするため、O（n ^ 2）である可能性があるという事実以外の複雑さもわかりません。

4

3 に答える 3

0

私には、（1）どの順列が100万分の1であるかは、使用する順序に完全に依存しているように見えます。（2）この種の順列は、再帰の熟した問題です。これを再帰プログラムとして記述し、反復ごとにカウントをインクリメントします。[それはあなたの質問でしたか？質問はあまり見ませんでした...]

于 2013-03-06T20:22:18.263 に答える
0

上記のコードに関する一般的ないくつかのこと：

  1. 具体的なクラスではなく、インターフェイスに実装する必要がありますList<String> array = ...。同様にあなたのSet.
  2. 配列はインデックス 0 から始まり、カウンターはインデックス 1 から始まります。

最後に、あなたの質問に答えるために、力ずくの方法と、数学のいくつかの原則を使用するよりエレガントな方法があります。アプローチを説明しているこのサイトを見てください。

于 2013-03-06T20:23:27.997 に答える