java全排列,java全排列去重

本文目錄一覽：

• 1、Java數組的全排列，裡面布爾類型的數組vis[ ]，在遞歸算法里起了什麼作用，遞歸那塊理解不了，求詳細解答
• 2、java怎麼搞全排列
• 3、如何用java輸出一個數組的全排列？不能用遞歸，用遞歸的話，很快就內存溢出了！
• 4、java中，用遞歸方法求n個數的無重複全排列，n=3。

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為未使用狀態

}

}

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輸出一個數組的全排列？不能用遞歸，用遞歸的話，很快就內存溢出了！

我覺得吧，你輸出一個全排列用不了多少內存，怎麼就能溢出呢？

首先，遞歸費不了多少內存，應該可以完成任務。

其次，你遞歸都幹了些什麼？別告訴我每層遞歸把數組複製一遍，你把位置遞歸一下就可以了。

如果不喜歡遞歸，可以自己弄個棧，其實差不多，速度略快，空間略小。

如果還是不明白，把全部源碼貼出來看看。

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();

    }

}

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