-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");
    }
}

但是我在理解代码和指令流程方面有一个小问题。我想念的是当这两条线被调用时

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

permute(..)正如我所见，在到达它们之前有一个递归函数！

4

2 回答 2

2

首先尝试了解permute () 函数的作用。它处理两个向量：unvisited和visited。在permute () 的执行中，该函数将从unvisited中获取一个元素并将其移动到visited。将其视为“构建”一个排列。

例如：

Unvisited: 1, 5, 8
visited:

我们将元素从未访问移动到已访问

Unvisited:  5, 8
visited: 1

现在要构建以 1 开头的其余排列，我们需要找到unvisited或 {5,8} 的排列。所以我们递归调用permute()来找到其余的。

那么做什么

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

做 ？

在构建每个排列时，该函数正在修改统一/通用/共享的数据源：向量。随着元素从unvisited转移到visited ，它们会不断被修改。但是，我们需要重置这些向量以找到其余的排列。在上面的示例中，我们需要将1放回unvisited find以5或8开头的排列。所以我们：

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 调用，它检查我们是否完成（未访问为空）并最终到达permute(unvisited,visited); 线。

此时permute()的第一次运行被暂停，第二次运行接管，直到第 n 次运行，它发现 unvisited 是空的并且运行完成。

当第 n 次运行结束时，第 n-1 次运行开始执行，然后执行您询问的两行（applepie 解释过），然后完成，将控制权返回给第 n-2 次，依此类推，直到所有运行完成.

于 2012-07-07T01:16:42.940 回答