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个数；