您的位置:

java全排列,java全排列递归算法

本文目录一览:

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为未使用状态

}

}