-1

私はこのコードをインターネットからコンピューターへの特定のベクトルのすべての可能な順列を見つけました。

import java.util.Vector;

class Permute {
    static int count = 0;

    public static void permute(Vector unvisited, Vector visited) {
    if ( unvisited.isEmpty() ) {
        System.out.println("Permutation: "+visited);
        count++;
    }
    else { 
        //System.out.println("Trace: "+visited+" "+unvisited);
        int l = unvisited.size();
        for(int i = 0; i<l; i++) {
        String next = String.valueOf(unvisited.remove(i));
        visited.add(next);
        permute(unvisited,visited);
        unvisited.add(i,next);
        visited.remove(next);
        }
    }
    }

    public static void main(String[] args) {    
    Vector objects = new Vector();

    objects.add(1);
    objects.add(5);
    objects.add(8);

    permute(objects, new Vector() );
        System.out.println(count+" Permutationen gefunden");
    }
}

Buコードと命令の流れを理解するのに小さな問題があります。私が見逃しているのは、これらの2つの行が呼び出されたときです

    unvisited.add(i,next);
    visited.remove(next);

permute(..)私が見るように、それらに到達する前に再帰関数があります！

4

2 に答える 2

2

まず、 permute（）関数が何をするのかを理解してみてください。それは2つのベクトルをジャグリングします：未訪問と訪問済み。permute （）の実行では、関数は未訪問から要素を取得し、それを訪問済みに移動します。それを順列を「構築する」と考えてください。

例えば：

Unvisited: 1, 5, 8
visited:

要素を未訪問から訪問済みに移動します

Unvisited:  5, 8
visited: 1

ここで、1で始まる残りの順列を作成するには、未訪問の順列、つまり{5,8}を見つける必要があります。したがって、残りを見つけるためにpermute（）を再帰的に呼び出します。

では、何をしますか

unvisited.add(i,next);
visited.remove(next);

行う ？

各順列が構築されると、関数はデータの統合/共通/共有ソースであるベクトルを変更します。要素が未訪問から訪問済みにシフトするにつれて、それらは絶えず変更されています。ただし、残りの順列を見つけるには、これらのベクトルをリセットする必要があります。上記の例では、 5または8で始まる順列を未訪問の場所に戻すために1を戻す必要があります。だから私たちは：

unvisited.add(i,next); //add it back to unvisited in its original position

と

visited.remove(next); //remove it from visited.
于 2012-07-07T00:55:24.887 に答える
0

再帰について覚えておくべきことは、メソッドが再度呼び出されると、その呼び出しが満たされるまで次の行は実行されないということです。

この場合、permute（）は最初にmainによって呼び出され、完了したかどうかを確認し（unvisitedが空）、最終的にpermute（unvisited、visited）に到達します。ライン。

この時点で、permute（）の最初の実行が保留になり、2番目の実行が引き継がれ、n番目の実行でunvisitedが空であることが検出され、実行が完了します。

n番目のランニングが終了すると、nth-1のランニングがピックアップされ、質問した2行（アップルパイが説明）を実行して完了し、すべてのランニングが完了するまで制御をnth-2に戻します。 。

于 2012-07-07T01:16:42.940 に答える