0

文字列順列の実行方法を調べていたところ、以下の解決策が見つかりました。しかし、使用されているロジックを理解するのに本当に苦労しています。特にこの特定の行。for(final String permutation : Permuatations(subList(head,words)))私が言えることから、作成者はそれ自体で関数「Permutations」を呼び出して、その中で subList 関数を実行しています。誰かがこれをもう少し明確にしてもらえますか? どんなガイダンスでも大歓迎です。

public static void main (String [] args)
    {
        for(final String s: Permuatations(Arrays.asList("This ","is ","String ")))
                {
            System.out.println("6. THE FINAL OUTPUT " +s);
                }
    }

    public static List<String> Permuatations(final List<String> words)
    {
        final List<String> perms = new ArrayList<String>();
        if (words.size() == 1)
        {
             perms.add(words.get(0));
             System.out.println("3. permuatations if words " + words);
             System.out.println("4. PERMS LIST " + perms);
        }

        else
        {
            for(final String head : words)
            {
                for(final String permutation : Permuatations(subList(head,words)))
                {
                    perms.add(head + permutation);
                    System.out.println("5 .SubList HEAD " + head + " PERMUATATION " + permutation  + " Word Size " + words.size() );
                }
            }
        }
        return perms;
    }


public static List<String> subList(final String elementToRemove, final List<String> elements)
{
    final List<String> subList = new ArrayList<String>();
    for(final String s : elements)
    {
        //System.out.println(" 1. STRING s " + s + " ELEMENTS " + elements);
        if(!s.equals(elementToRemove))
        {
            System.out.println(" 1. STRING S " + s + " ELEMENTS " + elements);
            subList.add(s);
            System.out.println("2 STRING S " + s + " TO SUBLIST " + subList);
        }


    }

    return subList;
}
4

3 に答える 3

2

これはまさに彼らがやっていることです。これは再帰と呼ばれるもので、最初は理解するのが難しいものです。文字列があると想像してください：

あいうえお

事実上、各文字列を順番に選択し、残りの文字列のすべての順列を見つけて、選択した文字列を先頭に追加します。

Choose A, get all permutations of {B,C,D} and append A. 
Choose B, get all permutations of {A,C,D} and append B. 
Choose C, get all permutations of {A,B,D} and append C. 
Choose D, get all permutations of {A,B,C} and append D.

ここで、非常によく似ているが小さい部分問題があります。それが再帰の核心です。問題を取り上げて、それをより小さなバージョンの問題に変える方法を見つけてください。さて、それが些細なことになるまで、それをより小さな問題に変え続けてください。次に、3 つの文字列の順列を生成する方法を理解する必要があります。

Permute(A B C) 
Choose A, get all permutations of {B,C} and append A.
Choose B, get all permutations of {A,C} and append B.
Choose C, get all permutations of {A,B} and append C.

同じ構造ですが、より小さな問題です。だから、さらに一歩進んでください。permute(AB) のやり方

Permute(A B) 
Choose A, get all permutations of {B} and append A.
Choose B, get all permutations of {A} and append B.

したがって、1 つの文字列を並べ替える必要があります。それは些細なことです。

Permute(A)
A

これで、サイズ 1 の文字列のリストを置換する方法ができました。サイズ N-1 のリストを置換することによって、サイズ N のリストを置換する方法を定義しました。したがって、問題のわずかに小さいバージョンで自分自身を呼び出すことにより、サイズ >= 1 の任意のリストを並べ替えることができます。それが再帰の美しさです。最小の問題を解決する方法と、そのソリューションを使用してより大きなソリューションを構築する方法を定義するだけで、それ自体が構築されます。

于 2013-03-23T15:35:11.790 に答える
0

これは再帰的なアルゴリズムであり、基本的に配列内の各要素を最初の要素として受け取り、その要素なしで自分自身を呼び出した出力を追加します。

3 つの要素 A、B、C を取り、ロジックをウォークスルーして、関数を呼び出しましょうperm。

だから、私たちは欲しい

perm({A, B, C})

これは等しい

A + perm({B, C})
B + perm({A, C})
C + perm({A, B})

再び拡大する

A + B + perm({C})
A + C + perm({B})
B + A + perm({C})
B + C + perm({A})
C + A + perm({B})
C + B + perm({A})

perm({X}) = X私たちが最終的に

A + B + C
A + C + B
B + A + C
B + C + A
C + A + B
C + B + A
于 2013-03-23T15:43:49.607 に答える
0

使用されるスキームは「分割統治」です。その基本的な考え方は、大きな問題を一連の小さな問題に分割し、問題の「原子」レベルに到達するまで同じメカニズムを適用することです。つまり、サイズ n の問題は、サイズ n-1 の n 個の問題に連続的に分割されます。下部には、サイズ 1 (またはその他の定数) の問題を処理する簡単な方法があります。これは通常、すでに指摘した再帰 (Calgar99 など) を使用して行われます。

そのスキームの非常に良い例は、「ハノイの塔」です。それをチェックすると、そのようなアプローチの創意工夫があなたを襲います。

提示されたコードに関して: n 個の単語の順列は、n-1 個の単語の順列と n 個の元の単語のそれぞれを連結したものです。この再帰的な定義は、問題に対する非常に洗練されたソリューションを表しています。

于 2013-03-23T15:44:36.327 に答える