[历史归档] 本文原发布于 cstriker1407.info 个人博客，内容为历史存档，仅供参考。
发布时间： 2013-11-19　｜　标题：算法学习笔记：java排列和随机的实现　｜　分类： 编程 / java / 数据结构与算法　｜　标签： java · 算法 · 排列 · 随机

备忘 Java 实现全排列和随机排列的简单思路。

全排列

通过递归 + 跳过已选下标的方式实现全排列打印：

static long idx = 1;
public static void printArrange(String arr[], Set<Integer> skip, String before) {
    for (int i = 0; i < arr.length; i++) {
        if (skip.contains(i)) continue;
        skip.add(i);
        printArrange(arr, skip, before + arr[i] + "->");
        skip.remove(i);
    }
    if (skip.size() == arr.length) {
        System.out.print("" + idx++ + "\t");
        System.out.println(before);
    }
}

调用方式：

String arr[] = new String[]{"A", "B", "C", "D"};
printArrange(arr, new HashSet<Integer>(), "");

随机排列

通过随机选取下标 + 记录已出现序列的方式生成不重复的随机排列：

public static void printRandom(String arr[], int times) {
    Random random = new Random();
    int size = arr.length;
    Set<String> before = new HashSet<String>(); // 已打印过的序列 key
    for (int j = 0; j < times; j++) {
        int idx = 0;
        Set<Integer> skip = new HashSet<Integer>();
        StringBuilder sb = new StringBuilder();  // 序列 key
        StringBuilder str = new StringBuilder(); // 待打印序列
        for (int i = 0; i < size; i++) {
            do {
                idx = random.nextInt(size);
            } while (skip.contains(idx));
            skip.add(idx);
            sb.append(idx);
            str.append(arr[idx] + "->");
        }
        if (!before.contains(sb.toString())) {
            System.out.println(str.toString());
            before.add(sb.toString());
        }
    }
}

调用方式：

String arr[] = new String[]{"A", "B", "C", "D"};
printRandom(arr, 100);

备注

代码实现较简单，仅作为基本思路参考，后续可根据特定需求进行修改。