从集合中挑选一个随机子集的最佳方法？
我在Vector中有一组对象，我想从中select一个随机子集（例如，返回100个项目，随机选取5个）。 在我第一次（非常草率）的传球中，我做了一个非常简单的或者是非常聪明的解决scheme：
Vector itemsVector = getItems(); Collections.shuffle(itemsVector); itemsVector.setSize(5); 虽然这有好处和简单的好处，我怀疑它不会很好地扩展，即Collections.shuffle（）至less必须是O（n）。 我不太聪明的select是
Vector itemsVector = getItems(); Random rand = new Random(System.currentTimeMillis()); // would make this static to the class List subsetList = new ArrayList(5); for (int i = 0; i < 5; i++) { // be sure to use Vector.remove() or you may get the same item twice subsetList.add(itemsVector.remove(rand.nextInt(itemsVector.size()))); }
任何关于更好的方法从一个集合中抽取一个随机子集的build议？
Jon Bentley在“Programming Pearls”或“More Programming Pearls”中对此进行了讨论。 你需要小心你的Mselect过程的N，但我认为显示的代码工作正常。 而不是随机洗牌所有的项目，你可以做随机洗牌只洗牌的前N个职位 – 这是一个有用的保存时，N << M.
Knuth还讨论了这些algorithm – 我相信这将是第3卷“sorting和search”，但我的集合是等待搬家的房屋，所以我不能正式检查。
@Jonathan，
我相信这是你正在谈论的解决scheme：
void genknuth(int m, int n) { for (int i = 0; i < n; i++) /* select m of remaining ni */ if ((bigrand() % (ni)) < m) { cout << i << "\n"; m--; } }
这是Jon Bentley编程珍珠的第127页，是基于Knuth的实现。
编辑：我刚才看到第129页上的进一步修改：
void genshuf(int m, int n) { int i,j; int *x = new int[n]; for (i = 0; i < n; i++) x[i] = i; for (i = 0; i < m; i++) { j = randint(i, n-1); int t = x[i]; x[i] = x[j]; x[j] = t; } sort(x, x+m); for (i = 0; i< m; i++) cout << x[i] << "\n"; }
这是基于“…我们需要洗牌arrays中的前m个元素…”的想法。
如果你想从n的列表中selectk个不同的元素，你上面给出的方法将是O（n）或O（kn），因为从Vector中移除一个元素将导致arraycopy将所有元素向下移动。
既然你要求最好的方法，这取决于你可以做什么你的input列表。
如果修改input列表是可以接受的，就像在你的例子中一样，那么你可以简单地把k个随机元素交换到列表的开头，然后像O（k）那样返回它们：
public static <T> List<T> getRandomSubList(List<T> input, int subsetSize) { Random r = new Random(); int inputSize = input.size(); for (int i = 0; i < subsetSize; i++) { int indexToSwap = i + r.nextInt(inputSize - i); T temp = input.get(i); input.set(i, input.get(indexToSwap)); input.set(indexToSwap, temp); } return input.subList(0, subsetSize); }
如果列表必须以相同的状态开始，则可以跟踪交换的位置，然后在复制所选子列表之后将列表返回到其原始状态。 这仍然是一个O（K）解决scheme。
但是，如果你根本不能修改input列表，并且k比n小得多（比如100中的5），那么最好不要每次删除选定的元素，而是简单地select每个元素，如果你得到一个副本，抛出并重新select。 这会给你O（kn /（nk）），当n支配k时，它仍然接近O（k）。 （例如，如果k小于n / 2，则它减less到O（k））。
如果k不是由n决定的，并且你不能修改列表，那么你可以复制你的原始列表，并使用你的第一个解决scheme，因为O（n）和O（k）一样好。
正如其他人所指出的那样，如果您依赖于每个子列表都可能（而且没有偏见）的强随机性，那么您肯定会需要比java.util.Random更强大的东西。 请参阅java.security.SecureRandom 。
几个星期前我写了一个有效的实现 。 它是用C＃编写的，但是对Java的翻译是微不足道的（本质上是相同的代码）。 好的一面是它也完全没有偏见（现有的一些答案不是） – 一种testing方法就在这里 。
它基于Fisher-Yates shuffle的Durstenfeld实现。
然而，使用随机选取元素的第二个解决scheme看起来很合理：
-
根据数据的敏感程度，我build议使用某种哈希方法来扰乱随机数种子。 对于一个很好的案例研究，请参阅我们如何学习在线扑克 （但这个链接是2015年12月18日的404）。 其他url（通过Googlesearch在双引号中的文章标题中find）包括：
- 我们如何学习在线扑克 – 显然是最初的出版商。
- 我们如何学习在线扑克
- 我们如何学习在线扑克
-
vector是同步的。 如果可能，请使用ArrayList来提高性能。
多less去除成本？ 因为如果需要将数组重写为新的内存块，那么你在第二个版本中完成了O（5n）操作，而不是之前想要的O（n）。
你可以创build一个设置为false的布尔值数组，然后：
for (int i = 0; i < 5; i++){ int r = rand.nextInt(itemsVector.size()); while (boolArray[r]){ r = rand.nextInt(itemsVector.size()); } subsetList.add(itemsVector[r]); boolArray[r] = true; }
如果您的子集比您的总规模小很多，则此方法可行。 随着这些尺寸彼此接近（即，尺寸的1/4），您将在该随机数发生器上碰到更多的碰撞。 在这种情况下，我会列出整数大小的数组，然后洗刷整数列表，并从中获取您的第一个元素（非冲突）的indeces。 这样一来，在构build整数数组中，O（n）的成本是O（n），而在检查器中没有来自内部的冲突，并且小于可能的O（5n）。
我个人select你的初步实施：非常简洁。 性能testing将显示它的规模。 我已经在一个体面的滥用方法中实现了一个非常类似的代码块，并充分扩展。 特定的代码依赖于包含> 10,000项的数组。
Set<Integer> s = new HashSet<Integer>() // add random indexes to s while(s.size() < 5) { s.add(rand.nextInt(itemsVector.size())) } // iterate over s and put the items in the list for(Integer i : s) { out.add(itemsVector.get(i)); }
这是在stackoverflow上非常类似的问题。
总结我最喜欢的答案（从用户Kyle furst）：
- O（n）解决scheme ：遍历您的列表，并以概率（＃需要/＃剩余）复制出一个元素（或其引用）。 例如：如果k = 5，n = 100，那么第一个元素的概率是5/100。 如果你复制那一个，那么你select下一个概率为4/99; 但如果你没有拿第一个，那么概率是5/99。
- O（k log k）或O（k 2 ） ：通过随机select一个数字<n，构buildk个索引（{0,1，…，n-1中的数字）的sorting列表，然后随机select一个数字<n-1等。在每一步，您都需要重新进行select以避免碰撞并保持概率。 举个例子，如果k = 5，n = 100，你的第一个select是43，你的下一个select是在[0，98]的范围内，如果它大于43，那么你加1。 所以，如果你的第二select是50，那么你加1，你有{43,51}。 如果你的下一个select是51，你可以加2来得到{43,51,53}。
这是一些伪python –
# Returns a container s with k distinct random numbers from {0, 1, ..., n-1} def ChooseRandomSubset(n, k): for i in range(k): r = UniformRandom(0, ni) # May be 0, must be < ni q = s.FirstIndexSuchThat( s[q] - q > r ) # This is the search. s.InsertInOrder(q ? r + q : r + len(s)) # Inserts right before q. return s
我的意思是时间复杂度是O（k 2 ） 或 O（k log k），因为它取决于你可以多快search并插入到你的容器中。 如果s是一个正常的列表，那么这些操作之一是线性的，你得到k ^ 2。 但是，如果您愿意将s构build为平衡二叉树，则可以获得O（k log k）时间。
两个解决scheme我不认为出现在这里 – 对应是相当长的，并包含一些链接，但是，我不认为所有的post都涉及从一组N元素中selectK元素的子问题。 [通过“设置”，我指的是math术语，即所有元素出现一次，顺序不重要]。
溶胶1：
//Assume the set is given as an array: Object[] set ....; for(int i=0;i<K; i++){ randomNumber = random() % N; print set[randomNumber]; //swap the chosen element with the last place temp = set[randomName]; set[randomName] = set[N-1]; set[N-1] = temp; //decrease N N--; }
这看起来与丹尼尔给出的答案类似，但实际上却非常不同。 它是O（k）运行时间。
另一种解决方法是使用一些math运算：考虑数组索引作为Z_n，因此我们可以随机select2个数字，x是与n互质的，即chhose gcd（x，n）= 1，另一个是a “开始点” – 那么这个序列：a％n，a + x％n，a + 2 * x％n，… a +（k-1）* x％n是一系列不同的数字（只要ķ<= N）。
