Question

java中，用递归方法求n个数的无重复全排列，n=3。

求给程序最好有注释，涉及的类和功能模块及其算法说明，类之间的关系。谢谢大神

Answer 1

程序如下所示，输入格式为：

5
3 1 2 1 2

第一行是数字个数，第二行有n个数，表示待排列的数，输入假设待排序的数均为非负数。

import java.io.File;
import java.io.FileNotFoundException;
import java.util.Arrays;
import java.util.Scanner;

public class Main {
    static final int maxn = 1000;
    int n;            // 数组元素个数
    int[] a;        // 数组
    
    boolean[] used;    // 递归过程中用到的辅助变量，used[i]表示第i个元素是否已使用
    int[] cur;        // 保存当前的排列数
    
    // 递归打印无重复全排列，当前打印到第idx位
    void print_comb(int idx) {
        if(idx == n) {    // idx == n时，表示可以将cur输出
            for(int i = 0; i < n; ++i) {
                if(i > 0) System.out.print(" ");
                System.out.print(cur[i]);
            }
            System.out.println();
        }
        
        int last = -1;                            // 因为要求无重复，所以last表示上一次搜索的值
        for(int i = 0; i < n; ++i) {
            if(used[i]) continue;
            
            if(last == -1 || a[i] != last) {    // 不重复且未使用才递归下去
                last = a[i];
                cur[idx] = a[i];
                
                // 回溯法
                used[i] = true;
                print_comb(idx + 1);
                used[i] = false;
            }
        }
    }
    
    public void go() throws FileNotFoundException
    {
        Scanner in = new Scanner(new File("data.in"));

        // 读取数据并排序
        n = in.nextInt();
        a = new int[n];
        for(int i = 0; i < n; ++i) a[i] = in.nextInt();
        Arrays.sort(a);
        
        // 初始化辅助变量并开始无重复全排列
        cur = new int[n];
        used = new boolean[n];
        for(int i = 0; i < n; ++i) used[i] = false;
        print_comb(0);
        in.close();
    }
    
    public static void main(String[] args) throws FileNotFoundException{
        new Main().go();
    }
}

客观来说，非递归的无重复全排列比较简单且高效。