當前位置:成語大全網 - 新華字典 - java中,用遞歸方法求n個數的無重復全排列,n=3。

java中,用遞歸方法求n個數的無重復全排列,n=3。

程序如下所示,輸入格式為:

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();

}

}

客觀來說,非遞歸的無重復全排列比較簡單且高效。