程序如下所示,输入格式为:
53 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()
}
}
客观来说,非递归的无重复全排列比较简单且高效。