最好的方式随机挑选一个子集，从一个收藏？

StackOverflow https://stackoverflow.com/questions/136474

题

我有一个集中的对象一个矢量由哪我想随机选择一个子集(例如100项目来回；挑选5随机).在我第一次(非常草率)通过我做了一个非常简单，也许是过于巧妙解决方案：

Vector itemsVector = getItems();

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

虽然这具有的优点是简单好，我怀疑它是不会来的规模非常好，即集合。shuffle()必须O(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())));
}

任何建议上更好的方法来绘制出一个随机的子从一个收藏？

有帮助吗？

解决方案

Jon Bentley在'Programming Pearls'或'More Programming Pearls'中讨论了这个问题。您需要小心N的M选择过程，但我认为显示的代码可以正常工作。而不是随机地随机播放所有项目，你可以进行随机随机播放只改组前N个位置 - 当N <！> lt; <！> lt时，这是一个有用的保存;微米。

Knuth还讨论了这些算法 - 我相信这将是Vol 3 <！>“排序和搜索<！>”，但是我的设置被打包等待移动房子，所以我无法正式检查。

其他提示

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

这是由Jon Bentley撰写的Programming Pearls的第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 元素进行洗牌...... <！>

如果你试图从n列表中选择k个不同的元素，你上面给出的方法将是O（n）或O（kn），因为从Vector中删除元素将导致arraycopy转移所有元素向下。

由于您要求最佳方式，这取决于您对输入列表的允许操作。

如果修改输入列表是可以接受的，就像在你的例子中一样，那么你可以简单地将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）解决方案。

但是，如果您根本无法修改输入列表且k远小于n（如100中的5），那么最好不要每次都删除所选元素，而只需选择每个元素，如果你得到一份副本，扔掉并重新选择。这将给你O（kn /（n-k））当n支配k时仍然接近O（k）。 （例如，如果k小于n / 2，则它减少为O（k））。

如果k不是由n控制，并且你不能修改列表，你也可以复制原始列表，并使用你的第一个解决方案，因为O（n）将与O（k）一样好。

正如其他人所指出的那样，如果你依赖于强大的随机性，每个子列表都是可能的（并且没有偏见），你肯定需要比java.util.Random更强的东西。见java.security.SecureRandom。

我写了这个有效实施几个星期前。它在C＃中，但对Java的翻译是微不足道的（基本上是相同的代码）。好的一面是，它也完全没有偏见（现有的一些答案都没有） - 测试的方法就在这里。

这是基于Durstenfeld实施的Fisher-Yates shuffle。

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

移除费用多少钱？因为如果需要将数组重写为新的内存块，那么你已经在第二个版本中完成了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），您会在该随机数生成器上获得更多冲突。在这种情况下，我会创建一个大整数列表的整数列表，然后对整数列表进行洗牌，然后从中取出第一个元素以得到（非碰撞）个别值。这样，你在构造整数数组时有O（n）的成本，而在shuffle中有另一个O（n），但是没有来自内部的检查器和小于可能消耗的潜在O（5n）的冲突。

我个人选择初步实施：非常简洁。性能测试将显示它的扩展程度。我已经在一个体面的滥用方法中实现了一个非常相似的代码块，并且它已经足够扩展。特定代码依赖于包含<！> gt; 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));
}

此 是一个非常类似的问题在计算器.

来总结一下我最喜欢的答案，从该网页(弗斯特的一个从用户凯尔):

  • O(n)解决方案:迭代过你的名单，并复制了一个元素(或参考其)与率(#需要/#剩余).例如：如果k=5和n=100，然后你把第一个元素与prob5/100.如果你复制那个，然后你选择一个与prob4/99;但如果你没拿第一，问题是5/99.
  • O(k日志k)或O(k2):建立一个排列的k指数(数字{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

我想说的是(k2) 或 O(k日志k)因为它取决于如何很快你可以搜索和中插入你的容器。如果是正常的列表，这些行动是线性的，并且你得到k^2.但是，如果你愿意建立s作为一个平衡的二进制树，你可以得到的O(k日志k)的时间。

我认为这里没有出现两个解决方案 - 对应很长，并且包含一些链接，但是，我不认为所有的帖子都与选择一组K elemetns的问题有关N个元素。 [By <！> quot; set <！> quot;，我指的是数学术语，即所有元素都出现一次，顺序并不重要。“

Sol 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，另一个是a，它是<！>的起点< ！> QUOT; - 然后是系列：a％n，a + x％n，a + 2 * x％n，... a +（k-1）* x％n是不同数字的序列（只要k <！> LT; = N）

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top