#include<stdio.h>
#include<string.h>
const int MAX=10
int n
bool used[MAX]={false}
int a[MAX]
int ans[MAX]
void DFS(int deep)
{
int i
if(deep==n)
{
for(i=0i<ni++)
{
printf("%d ",ans[i])
}
puts("")
return
}
for(i=0i<ni++)
{
if(used[i])continue
used[i]=true
ans[deep]=a[i]
DFS(deep+1)
used[i]=false
}
}
int main()
{
int i
scanf("%d",&n)
for(i=0i<ni++)
{
scanf("%d",&a[i])
}
DFS(0)
return 0
}
程序如下所示，输入格式为：
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()
}
}
客观来说，非递归的无重复全排列比较简单且高效。
给你个思路：函数内判断
if (元素个数==2){
打印结果：元素1，元素2；
打印结果：元素2，元素1；
} else {
打印结果：元素1，递归本函数(其他元素)；
打印结果：递归本函数(其他元素)，元素1；
}
