在Java中生成随机且唯一的序列

Question

我有一个数字数组，例如：

[1, 3, 5, 7, 9]

可以生成5！即120个不同的数字序列。例如：

1 3 5 7 9
5 1 3 9 7
7 3 9 5 1
1 7 9 5 3
... and so forth

我需要随机生成10个这样的序列，且不能重复。有任何建议将不胜感激。

- David Weng

---

这个10个数必须是唯一的吗？还是允许有重复的可能性？ - Jodaka

@Jokada 是的，我需要它们是唯一的。 - David Weng

如果你必须确保它是唯一的，那么你就无法确保它是真正随机的... - jball

你在现实世界中初始数组长度是多少？ - jball

@jball，听起来像是一个很酷的引用，但一个基本的算法可以生成随机序列并丢弃重复的序列，直到你有10个唯一的序列。你还认为这不能被视为随机吗？ - David Weng

至少，它允许预测算法不会产生什么。这肯定减少了对需要最大程度随机性的应用程序输出的有用性。随机性也很棘手，因为（如果我记得正确 - 也许更深入研究的专家可以提供来源），伪随机数的伪随机抽样实际上可能导致输出中更多的可预测性。 - jball

Answer 1

List<Integer> template = Arrays.asList(1, 3, 5, 7, 9);
Set<List<Integer>> seen = new HashSet<List<Integer>>();
for (int i = 0; i < 10; ++i) {
    List<Integer> items = new ArrayList<Integer>(template);
    do {
        Collections.shuffle(items);
    } while (!seen.add(items));
    System.out.println(items);
}

:-)

- C. K. Young

---

@Amir：这个答案太“企业化”了，不能作为作业提交哦。;-) - C. K. Young

当然，算法的问题在于它总是相同的10个序列！因此，如果您希望每次运行都获得不同的数字集，请考虑使用递归。 - Amir Raminfar

@Amir，有人将它标记为作业，但不是原作者，除此之外没有人提到过作业，所以虽然可能是作业，也可能只是一个好奇的程序员提出的问题 :) - jball

@Amir：不会的。Java会根据需要自动种子化你的RNG。:-P - C. K. Young

是的，我改正了。每次运行洗牌都会不同。知道这点很好。 - Amir Raminfar

Answer 2

你想要生成一个给定数组的n个随机排列。有一个简单的算法可以生成一个随机排列，这在wikipedia上有很好的解释。但你仍然需要检查唯一性。

在Java中:

Random rand = new Random();

int[] generateRandomPermutation(int n) {
    int[] res = new int[n];
    for (int i = 0; i < n; i++) {
        int d = rand.nextInt(i+1);
        res[i] = res[d];
        res[d] = i;
    }
    return res;
}

另一个解决方案是使用排列编号方案（此处介绍），并生成n个随机且不同整数的相应排列（从0到s！-1，其中s是数组的大小）。

- barjak

---

简单、便携和高效！ - Hartok