如何在Java中生成随机排列？

Question

如何生成n个数字的随机排列，哪种方法最好？

例如，假设我有一个数字集合1、2和3（n = 3）

所有可能排列的集合：{123, 132, 213, 231, 312, 321}

现在，如何生成：

• 上述集合中的一个元素（随机选择）
• 像上面显示的整个排列集

换句话说，如果我有一个由n个元素组成的数组，如何将它们随机洗牌？ 请帮助。谢谢。

- Shankar Raju

Answer 1

java.util.Collections.shuffle(List);

Java文档链接：Collections.shuffle

List<Integer> list = new ArrayList<Integer>();
list.add(1);
list.add(2);
list.add(3);
java.util.Collections.shuffle(list);

值得注意的是，有很多算法可以使用。下面是Sun JDK中的实现方式：

public static void shuffle(List<?> list, Random rnd) {
    int size = list.size();
    if (size < SHUFFLE_THRESHOLD || list instanceof RandomAccess) {
        for (int i=size; i>1; i--)
            swap(list, i-1, rnd.nextInt(i));
    } else {
        Object arr[] = list.toArray();

        // Shuffle array
        for (int i=size; i>1; i--)
            swap(arr, i-1, rnd.nextInt(i));

        // Dump array back into list
        ListIterator it = list.listIterator();
        for (int i=0; i<arr.length; i++) {
            it.next();
            it.set(arr[i]);
        }
    }
}

- corsiKa

---

非常感谢。但是API说它在线性时间内工作。我们是否能够以低于O(n)的复杂度实现这一点？ - Shankar Raju

@Shankar：是的 - BlueRaja - Danny Pflughoeft

@Danny 这是可能的，但不切实际。 - corsiKa

@metdos，你能详细说明一下吗？我相信这是Knuth Shuffle算法，他在算法方面写了一本书。真的。 - corsiKa

是的，你说得对。我猜我的问题出在随机生成器上。我创建了一个长度为3的列表，将其洗牌了100000次，结果并不理想（不如我期望的那样接近均匀分布）。 - metdos

Answer 2

你可以尝试使用RubyCollect4J

Ruby.Array.of(1, 2, 3).permutation().toA().sample();

它完全按照你的要求执行了。 顺便说一下，我是这个Java库的作者。

- user3360932

Answer 3

您是在询问排列生成器吗？因为您的排列集合缺少两个数字。无论如何，您可以查看http://www.merriampark.com/perm.htm上的排列生成器。

- bvk256

---

我的错！我改了它。但是，我希望排列随机生成。 - Shankar Raju