java全排列,java全排列去重

发布时间：2023-01-09

本文目录一览：

  1. [Java数组的全排列，里面布尔类型的数组vis[ ]，在递归算法里起了什么作用，递归那块理解不了，求详细解答](#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) {
    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])
                continue;
            a[i] = i;
            vis[i] = true;
            dfs(start + 1, end, num);
            vis[i] = false;
        }
    }
}

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[start];
        list[start] = 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();
    }
}

客观来说，非递归的无重复全排列比较简单且高效。

推荐文章