程序如下所示,輸入格式為:
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();
}
}
客觀來說,非遞歸的無重復全排列比較簡單且高效。