java全排列演算法遞歸演算法

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

程序如下所示，輸入格式為：

5
31212

第一行是數字個數，第二行有n個數，表示待排列的數，輸入假設待排序的數均為非負數。

importjava.io.File;
importjava.io.FileNotFoundException;
importjava.util.Arrays;
importjava.util.Scanner;

publicclassMain{
staticfinalintmaxn=1000;
intn;//數組元素個數
int[]a;//數組

boolean[]used;//遞歸過程中用到的輔助變數，used[i]表示第i個元素是否已使用
int[]cur;//保存當前的排列數

//遞歸列印無重復全排列，當前列印到第idx位
voidprint_comb(intidx){
if(idx==n){//idx==n時，表示可以將cur輸出
for(inti=0;i<n;++i){
if(i>0)System.out.print("");
System.out.print(cur[i]);
}
System.out.println();
}

intlast=-1;//因為要求無重復，所以last表示上一次搜索的值
for(inti=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;
}
}
}

publicvoidgo()throwsFileNotFoundException
{
Scannerin=newScanner(newFile("data.in"));

//讀取數據並排序
n=in.nextInt();
a=newint[n];
for(inti=0;i<n;++i)a[i]=in.nextInt();
Arrays.sort(a);

//初始化輔助變數並開始無重復全排列
cur=newint[n];
used=newboolean[n];
for(inti=0;i<n;++i)used[i]=false;
print_comb(0);
in.close();
}

publicstaticvoidmain(String[]args)throwsFileNotFoundException{
newMain().go();
}
}

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

Ⅱ java 排列：list 這四個字母有多少中排列組合方式變成列印出來

package com.syj.csdn;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
* <p>
* Title:全排列演算法橡橡
* </p>
*
* <p>
* Copyright: http://blog.csdn.net/sunyujia/
* </p>
*
* @author 孫鈺佳
* @main [email protected]
* @date 2009-04-25 23:57:23 PM
*/
public class FullSort {
//將NUM設置為梁芹旁待排列數組的長度即實現全排列
private static int NUM = 5;

/**
* 遞歸演算法：將數據分為兩部分，遞歸將數據從左側移右側實現全排首臘列
*
* @param datas
* @param target
*/
private static void sort(List datas, List target) {
if (target.size() == NUM) {
for (Object obj : target)
System.out.print(obj);
System.out.println();
return;
}
for (int i = 0; i < datas.size(); i++) {
List newDatas = new ArrayList(datas);
List newTarget = new ArrayList(target);
newTarget.add(newDatas.get(i));
newDatas.remove(i);
sort(newDatas, newTarget);
}
}

public static void main(String[] args) {
String[] datas = new String[] { "a", "b", "c", "1","2" };
sort(Arrays.asList(datas), new ArrayList());
}

}

Ⅲ java中遞歸演算法是什麼怎麼算的

一、遞歸演算法基本思路：

Java遞歸演算法是基於Java語言實現的遞歸演算法。遞歸演算法是一種直接或者間接調用自身函數或者方法的演算法。遞歸演算法實質是把問題分解成規模縮小的同類問題的子問題，然後遞歸調用方法表示問題的解。遞歸往往能給我們帶來非常簡潔非常直觀的代碼形式，從而使我們的編碼大大簡化，然而遞歸的思維確實跟我們的常規思維相逆的，通常都是從上而下的思維問題，而遞歸趨勢從下往上的進行思維。

二、遞歸演算法解決問題的特點：

【1】遞歸就是方法里調用自身。

【2】在使用遞歸策略時，必須有一個明確的遞歸結束條件，稱為遞歸出口。

【3】遞歸演算法代碼顯得很簡潔，但遞歸演算法解題的運行效率較低。所以不提倡用遞歸設計程序。

【4】在遞歸調用的過程中系統為每一層的返回點、局部量等開辟了棧來存儲。遞歸次數過多容易造成棧溢出等，所以一般不提倡用遞歸演算法設計程序。

【5】在做遞歸演算法的時候，一定把握出口，也就是做遞歸演算法必須要有一個明確的遞歸結束條件。這一點是非常重要的。其實這個出口就是一個條件，當滿足了這個條件的時候我們就不再遞歸了。

三、代碼示例：

publicclassFactorial{

//thisisarecursivefunction

intfact(intn){

if(n==1)return1;

returnfact(n-1)*n;

}}

publicclassTestFactorial{publicstaticvoidmain(String[]args){

//TODOAuto-generatedmethodstub

Factorialfactorial=newFactorial();

System.out.println("factorial(5)="+factorial.fact(5));

}
}

代碼執行流程圖如下：

此程序中n=5就是程序的出口。

Ⅳ JAVA遞歸演算法，1^2+2^2+3^2+....+n^2

publicclassDigui{//遞歸演算法:publicstaticdoubledigui(intn){doublesum=0.0;if(n==1){sum=1;}else{if(n%2==0){sum=1.0/n+digui(n-1);}else{sum=-1.0/n+digui(n-1);}}returnsum;}//非遞歸演算法：publicstaticdoublefeidigui(intn){doublecount=0.0;StringBuffersb=newStringBuffer();for(doublei=1;i<=n;i++){if(i==1){count=1;sb.append("n!="+n+"!=1");}else{if(i%2==0){count=count+1/i;sb.append("+1/"+(int)i);}else{count=count-1/i;sb.append("-1/"+(int)i);}}}System.err.println(sb.toString());returncount;}publicstaticvoidmain(String[]args){intn=10;doubledigui=feidigui(n);doublefeidigui=digui(n);System.out.println("遞歸演算法："+n+"!="+digui);System.out.println("非遞歸演算法："+n+"!="+feidigui);}}運行結果如下：n!=10!=1+1/2-1/3+1/4-1/5+1/6-1/7+1/8-1/9+1/10遞歸演算法：10!=1.3543650793650797非遞歸演算法：10!=1.3543650793650797

Ⅳ java全排列遞歸演算法一個小問題

是真心沒看懂你再說什麼
什麼沒拆猜叫先輸入枯型要求輸入的字元個數？ 你御老這原題 或者 原需求是什麼 你寫出來我給你CODE

Ⅵ java 1-5隨機排列，求所有不同排列，怎麼用遞歸方式實現

//需要三個參數，k表示當前的數，m表示數的個數
Perm(char*pszStr,intk,intm)
{
if(k==m)
{
staticints_i=1;
cout<<」第」塌兄<<s_i++<<」個排列」<<pszStr<<endl;
}
運巧團悄襲else
{
for(inti=k;i<=m;i++)//第i個數分別與它後面的數字交換就能得到新的排列
{
Swap(pszStr+k,pszStr+i);
Perm(pszStr,k+1,m);
Swap(pszStr+k,pszStr+i);
}
}
}

Ⅶ Java數組的全排列，裡面布爾類型的數組vis[ ]，在遞歸演算法里起了什麼作用，遞歸那塊理解不了，求詳細解答

不要急於看代碼，你心理要知道全排列的思路，不注重思路是很多程序員易犯的錯誤。
全排列演算法：
如果我求得固定第一位後的排列，那麼全部排列就可以求出，固定第一位有10種可能，可以循環求得。
如果我求得固定第二位後的排列，固定第一位後的排列就可以求出，固定第二位有9種可能，可以循環求得。
。。。
如果我求得固定第10位後的排列，固定第9位後的排列就可以求出，固定第10位有1種可能，可以循環求得。
這很明顯是遞歸的演算法。
static void dfs(int start,int end,int num){//為全部排列的集合，start為數字的位置,end為最後一位，num多餘的
if(start==end){//當前的數字位置為最後一位時，說明，一個序列已經生成
for(int i=1;i<end;i++)
System.out.print(a[i]+" ");//輸出序列
System.out.println();
}
else{//序列沒有生成時
for(int i=1;i<end;i++){
if(vis[i])//i是否在前面使用過
continue;//如果是直接跳過
a[start]=i;//確定start位置的數字，當start為1時就是確定第一位，有10種可能
vis[i]=true;//設置i為已使用狀態，避免下一位使用i
dfs(start+1,end,num);//求得確定start位後的全部序列
vis[i]=false;//設置i為未使用狀態
}
}

Ⅷ java全排列遞歸演算法

不會JAVA只能是寫個搜胡信C的了
#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=0;i<n;i++)
{
printf("%d ",ans[i]);
}
puts("");
return ;
}
for(i=0;i<n;i++)
{
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=0;i<n;i++)
{
scanf("%d",&a[i]);
}

DFS(0);
return 0;
}

Ⅸ 關於全排列遞歸演算法

這個演算法，是把每一個數與末尾的數逐一交換，
k>m 說明已交換完畢，就輸出了，這是遞歸的結束條件。
要學到一定的基本功才能明白。
---------------------------------------------------------------------------
我這個程序，我也編過，放在西祠C++BUILDER論壇里。
你先要掌握，排列的方法才能看懂這個程序。
在這知道里，也答過兩次。
為了增加可理解性，我略改了一下方法，我的方法
與你的方法遞歸方向不同。
http://www.xici.net/d190786398.htm
此演算法為遞歸法顯示排列數，沒發現比這更簡單、明了的遞
歸演算法。此演算法只要練智商的作用，沒有其它實用價值，階
乘級的佔用時間、空間，數一大，堆棧很快暴了。
演算法的要點：
1.列N個數的排列，可化為N個的N-1階排列：
最末一個數是 D[n-1]，把這個位置的N個數的可能性列出，
就是每一個數 與末尾逐一交換位置，就是N種情況，每一種
情況再求N-1的全排列，就是遞歸調用了；
交換位置後，就調用自已，但必須恢復剛才的交換，以便下一次
交換；
2.當階數遞歸到1時，就直接輸出這N個數；