挑选从集合随机子集最好的方法？(best way to pick a random subset f

我有一组在一个矢量对象从中我想选择的随机子集（例如100个项目回来;挑5随机地）。 在我的第一（很草率）通过我做了一个非常简单的，也许过于聪明的解决方案：

Vector itemsVector = getItems();

Collections.shuffle(itemsVector);
itemsVector.setSize(5);

虽然这具有很好的和简单的优势，我怀疑它不会规模非常好，即Collections.shuffle（）必须是（3）至少（N）。 我不太聪明的选择是

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())));
}

更好的办法任何建议，以绘制出从集合随机子集？

Answer 1:

乔恩·本特利讨论这两种“编程珠玑”或“更多的编程珍珠”。 你需要注意你的m个选择的过程中N，但我认为所示的代码工作正常。 而不是随意打乱所有的项目，你可以做随机洗牌洗牌只有第N个位置 - 这是一个有用的节省当N << M。

克努特还讨论了这些算法的 - 我相信这将是第3卷“排序和搜索”，但我的集合包装未决房屋的举动，所以我不能正式确认。

Answer 2:

@Jonathan，

我相信这是你在谈论的解决方案：

void genknuth(int m, int n)
{    for (int i = 0; i < n; i++)
         /* select m of remaining n-i */
         if ((bigrand() % (n-i)) < m) {
             cout << i << "\n";
             m--;
         }
}

这是由乔恩·本特利编程珠玑的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";
}

这是基于这样的思想：“......我们需要洗牌只有数组的第m个元素......”

Answer 3:

如果你想从n的列表中选择k个不同的元素，你上面给的方法将是O（N）或O（KN），因为从Vector移除元素将导致arraycopy所有单元上下移动。

既然你问的最佳方式，它取决于你允许你输入列表做什么。

如果这是可以接受修改输入列表，如你的例子，那么你可以简单地交换ķ随机元素的列表的开头和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）的溶液中。

但是，如果您不能修改输入列表中的所有，k是大于n（如5 100）少得多，这将是更好不要每次删除选定的元素，但只需选择每一个元素，如果你有机会重复，折腾出来，并重新选择。 这会给你O（KN /（NK）），它仍然是接近O（K）当n主导ķ。 （例如，如果k小于N / 2，然后将其降低到O（k））的。

如果K不被n为主，而不能修改的列表，你还不如复制原始的列表，并使用你的第一个解决方案，因为为O（n）将是多么的O（k）的一样好。

正如其他人指出，如果根据随机性强，每一个子表是可能的（偏），你一定会需要比更强烈的东西java.util.Random 。 见java.security.SecureRandom 。

Answer 4:

我写了一个高效的实现这个几个星期前。 这是在C＃中，但转换到Java是微不足道的（本质上是相同的代码）。 有利的一面是，它也完全公正的（其中一些现有的答案都不是） - 一种方式来测试就在这里 。

它是基于一个Durstenfeld执行费雪耶茨洗牌。

Answer 5:

您使用随机挑选元素的第二个解决方案似乎是合理，但是：

• 根据您的数据是多么敏感，我建议使用某种散列法的争夺随机数种子。 对于一个很好的案例研究，请参见我们如何学会在网上扑克作弊 （但是此链接是404的2015年12月18日）。 替代的URL（通过对双引号文章标题谷歌搜索找到）包括：

  • 我们如何学会在网上扑克作弊 -显然原来的出版商。
  • 我们如何学会在网上扑克作弊
  • 我们如何学会在网上扑克作弊
    

• Vector是同步的。 如果可能的话，使用ArrayList，而不是提高性能。

Answer 6:

多少成本去掉？ 因为如果需要的阵列重写一个新的内存块，然后你做O（5N）的第二个版本，而不是为O（n），你之前想要的操作。

你可以创建设置为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。 这样的话，你必须为O（n）的建设整数数组的成本，另一个为O（n）在洗牌，但没有来自内部的冲突，而检查不到的潜在O（5N）是去除可能成本。

Answer 7:

我最好的个人选择您最初的实施：非常简洁。 性能测试将显示它扩展有多好。 我实现了一个非常类似的代码块在一个体面被虐方法，它足够的推广。 的特定代码依赖于含有> 10,000项目以及阵列。

Answer 8:

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));
}

Answer 9:

这是一个计算器非常类似的问题。

总结从该页面（从用户凯尔弗斯特一个）我最喜欢的答案：

• 为O（n）的解决方案 ：通过迭代您的列表，并复制出的元素的概率（#needed / #remaining）（或参考于此）。 例如：如果k = 5和n = 100时，则采取与概率5/100的第一个元素。 如果复制了一个，就选择下一个与概率4/99; 但如果你没有走第一个，概率是5/99。
• O（ķ日志K）或O（K ^2）：构建ķ指数的排序列表（在数字{0，1，...，N-1}）由随机选择的数<n，则随机选择一个数<N-1等，在每个步骤中，你需要recallibrate你的选择，以避免冲突，保持概率均匀。 作为一个例子，如果k = 5和n = 100，和你的第一选择是43，您的下一个选择是在范围[0，98]，以及如果它是> = 43，那么你把它加1。 所以，如果你的第二个选择是50，那么你把它加1，你有{43} 51。 如果你的下一个选择是51加2，把它拿到{43，51，53}。

下面是一些pseudopython -

# 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, n-i)                 # May be 0, must be < n-i
    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数K），因为这取决于你如何快速搜索并插入到你的的集装箱。 如果s是一个正常的列表，这些操作的一个是线性的，你会得到K ^ 2。 但是，如果你愿意建立S作为平衡二叉树，你可以走出Ô（K数k）的时间。

Answer 10:

两种解决方案，我不认为出现在这里 - 的对应是相当长的，并包含一些链接，但是，我不认为所有的职位都涉及选择K的SUBST的问题elemetns出一组N个元素的。 [通过“设置”，我指的是数学术语，即所有的元素出现一次，顺序并不重要。

索尔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）的运行时间。

另一个解决方案是使用一些数学：考虑数组索引作为Z_n所以可随机选择2号中，X是互质到n，即chhose GCD（X，N）= 1，和另一个，一个，这是“起点” - 然后串联：一个％N，A + X％N，A + 2 * x％的N，...一个+（K-1）×x％的n是不同的号码（一个序列，只要ķ<= N）。

文章来源: best way to pick a random subset from a collection?