java - StackOverflowError and random numbers

Question

I have a collection: [1, 2, 3, 4, 5, 6, 7, 8, 9] from which I need to generate a random number of unique elements e.g. 5, 3, 7, 9, next time: 4, 8. My function works well but sometimes throws StackOverflowError because of recursive call on a function that generates random numbers and checks if there is no duplicates already. I wonder how I can prevent this from happening.

Answer 1

One solution is to use iteration (a for or while loop) rather than recursion.

Another solution is to start by making a mutable copy of your collection, and whenever you select an element from it, remove that element so that there's no risk of re-selecting it. (But be sure you're making an actual copy of your collection, e.g. new ArrayList<Integer>(originalCollection), so that you aren't removing elements from the original.)

Answer 2

您可能应该在不使用递归的情况下执行此操作。可能会更好的算法的粗略草图：

1. 创建一个空列表
2. 遍历源数组并将每个元素以 50% 的概率添加到列表中
3. 将列表转换为数组
4. 在数组上使用 Arrays.shuffle() 随机重新排序元素

那应该做的工作。

Answer 3

完整列表中的每个元素在特定元素集合中存在或不存在。这告诉我们使用二进制。

0b000000000映射到 [ ] 即所有数字都不存在。

0b111111111映射到 [1, 2, 3, 4, 5, 6, 7, 8, 9] 即所有数字。

两者之间的任何数字（被视为二进制）都将映射到整个集合的子集。

0b001010101映射到 [3, 5, 7, 9]

范围内的每个二进制数都将映射到一个唯一的子集。您的示例暗示排序可能很重要。如果是，那么您将不得不单独处理它。此方法最多可为您提供 2^9 = 512 种不同的组合。