溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
利用Java如何實現全排列算法和遞歸？很多新手對此不是很清楚，為了幫助大家解決這個難題，下面小編將為大家詳細講解，有這方面需求的人可以來學習下，希望你能有所收獲。
全排列：
從n個不同元素中任取m（m≤n）個元素，按照一定的順序排列起來，叫做從n個不同元素中取出m個元素的一個排列。當m=n時所有的排列情況叫全排列。
例如：
1 、2 、3三個元素的全排列為：
{1，2，3}，{1，3，2}，{2，1，3}，{2，3，1}，{3，1，2}，{3，2，1}。
------------------------------------------------------
解法1（遞歸）
如下圖：要對1、2、3、4進行排序，第一個位置上的元素有四種可能：1或2或3或4，假如已經確定了第一個元素為4，剩下的第二個位置上可以是1、2、3，很顯然這具有遞歸結構，如果原始要排列的數組順序為1、2、3、4，現在只要分別交換1、2，1、3，1、4然后對剩下的3個元素進行遞歸的排列。
代碼：
-----------------------------------------------
public void Permutation(char chs[],int start )
{
if(start==chs.length-1)
{
Arrays.toString(chs);
//如果已經到了數組的最后一個元素，前面的元素已經排好，輸出。
}
for(int i=start;i<=chs.length-1;i++)
{
//把第一個元素分別與后面的元素進行交換，遞歸的調用其子數組進行排序
Swap(chs,i,start);
Permutation(chs,start+1);
Swap(chs,i,start);
//子數組排序返回后要將第一個元素交換回來。
//如果不交換回來會出錯，比如說第一次1、2交換，第一個位置為2，子數組排序返回后如果不將1、2
//交換回來第二次交換的時候就會將2、3交換，因此必須將1、2交換使1還是在第一個位置
}
}
public void Swap(char chs[],int i,int j)
{
char temp;
temp=chs[i];
chs[i]=chs[j];
chs[j]=temp;
}遞歸方法會對重復元素進行交換比如使用遞歸對{1，1}進行全排序會輸出：{1，1}，{1，1}兩個重復的結果。要在排序的時候去掉重復結果，可以修改一下代碼如下：
public static void Permutation(char chs[],int start)
{
if(start==end)
{
list.add(new String(chs));
}
for(int i=start;i<=chs.length-1;i++)
{
if(i==start||chs[i]!=chs[start])
{
//在排列的時候進行判斷如果后面的元素與start相同時就不進行排序。
//這樣就可以避免對重復元素進行排序
Swap(chs,i,start);
Permutation(chs,start+1);
Swap(chs,i,start);
}
}
}解法2（字典序法）
字典序法
對給定的字符集中的字符規定了一個先后關系，在此基礎上規定兩個全排列的先后是從左到右逐個比較對應的字符的先后。
列如：對a、b、c進行排序的結果是{a,b,c}、{a,c,b}、{b,a,c}、{b,c,a}、{c,a,b}、{c,b,a}
字典序法的優點是排列的結果按照順序輸出并且對于重復的元素不進行重復排序。
字典排序法的思想：
例如：對元素1，2，3，4進行排序，假設默認的數組順序為{1，2，3，4}，先輸出第一個排列：1、2、3、4。然后從右向左找到第一個非遞增的數，4，3，因為3比4小，交換3、4，并且對3后面的數進行逆序排列，第二個排列為{1，2，4，3}，再從右向左3，4，2，發現2比4小，交換從右向左第一個比2大的數，交換后{1，3，4，2}再對3后面的數進行逆序排列第三個序列為：{1，3，2，4}
依次循環直到數組成為完全遞減數組結束1、2、3、4字典排序的最大序列為{4，3，2，1}。
--------------------------------------------
代碼
-------------------------------------------
public void PermutationWithDictionary(char chs[])
{
Arrays.sort(chs);
//先對數組的元素進行依次排序
while(true)
{
System.out.println(chs);
int j=chs.length-1;
int index=0;
for(j=chs.length-2;j>=0;j--)
{
if(chs[j]<chs[j+1])
{
index=j;
break;
//從右向左找到第一個非遞增的元素
}
else if(j==0){
return;
}
}
for(j=chs.length-1;j>=0;j--)
{
if(chs[j]>chs[index])
break;
//從右向左找到第一個比非遞增元素大的元素
}
Swap(chs,index,j);
//交換找到的兩個元素
Reverse(chs,index+1);
//對非遞增元素位置后面的數組進行逆序排列
}
}
public static void Reverse(char chs[],int i)
{
int k=i,j=chs.length-1;
while(k<j)
{
Swap(chs,k,j);
k++;
j--;
}
}
public static void Swap(char chs[],int i,int j)
{
char temp;
temp=chs[i];
chs[i]=chs[j];
chs[j]=temp;
}看完上述內容是否對您有幫助呢？如果還想對相關知識有進一步的了解或閱讀更多相關文章，請關注億速云行業資訊頻道，感謝您對億速云的支持。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
