本文目录一览:
- 1、java怎么搞全排列
- 2、java全排列递归算法
- 3、java中,用递归方法求n个数的无重复全排列,n=3。
- 4、java实现全排列的问题
- 5、如何用java输出一个数组的全排列?不能用递归,用递归的话,很快就内存溢出了!
- 6、Java数组的全排列,里面布尔类型的数组vis[ ],在递归算法里起了什么作用,递归那块理解不了,求详细解答
java怎么搞全排列
尽量用递归好理解一些,打个断点
public class Permutation {
public static void permulation(int[] list, int start, int length) {
int i;
if (start == length) {
for (i = 0; i length; i++)
System.out.print(list[i] + " ");
System.out.println();
} else {
for (i = start; i length; i++) {
swap(list, start, i);
permulation(list, start + 1, length);
swap(list, start, i);
}
}
}
public static void swap(int[] list, int start, int i) {
int temp;
temp = list;
list = list[i];
list[i] = temp;
}
public static void main(String[] args) {
int length = 3;
int start = 0;
int list[] = new int[length];
for (int j = 0; j length; j++)
list[j] = j + 1;
permulation(list, start, length);
}
}
java全排列递归算法
思路:先有一个起始排列,如1234.从后面扫描,直到找到a[k],a[k]a[k+1];再从后面扫描,直到找到a[j],这里有 a[k]a[j]。交换a[k],a[j].再把a[k+1],...a[n-1]排序(从小到大),即得到了一个排列,再循环下去,直到找出所有的排序。用C语言的,参考下:
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();
}
}
客观来说,非递归的无重复全排列比较简单且高效。
java实现全排列的问题
对 深度优先搜索 先交换 然后递归 再交换回来继续循环下一种情况
如何用java输出一个数组的全排列?不能用递归,用递归的话,很快就内存溢出了!
我觉得吧,你输出一个全排列用不了多少内存,怎么就能溢出呢?
首先,递归费不了多少内存,应该可以完成任务。
其次,你递归都干了些什么?别告诉我每层递归把数组复制一遍,你把位置递归一下就可以了。
如果不喜欢递归,可以自己弄个栈,其实差不多,速度略快,空间略小。
如果还是不明白,把全部源码贴出来看看。
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;iend;i++)
System.out.print(a[i]+" ");//输出序列
System.out.println();
}
else{//序列没有生成时
for(int i=1;iend;i++){
if(vis[i])//i是否在前面使用过
continue;//如果是直接跳过
a=i;//确定start位置的数字,当start为1时就是确定第一位,有10种可能
vis[i]=true;//设置i为已使用状态,避免下一位使用i
dfs(start+1,end,num);//求得确定start位后的全部序列
vis[i]=false;//设置i为未使用状态
}
}