15

这个问题有一个额外的限制。

我愿意允许不统一的选择，只要它不是片面的。

鉴于“集合通常实现为二叉搜索树”并且我希望它们将包含某种深度或大小信息以进行平衡，我希望您可以对树进行某种加权随机游走。但是我不知道有任何远程便携的方式来做到这一点。

编辑：约束不适用于摊销时间。

4

5 回答 5

6

引入大小等于集合的数组。使数组元素保存集合中每个元素的地址。生成以数组/集合大小为界的随机整数R，在数组的元素中选择地址R并取消引用它以获得集合的元素。

于 2011-11-28T21:10:09.540 回答
3

我不知道如何使用 just std::set，因此您可能需要不同的数据结构。就像 Victor Sorokin 说的，你可以把一个集合和一个向量结合起来。而不是set<T>，使用map<T, size_t>，加vector< map<T, size_t>::iterator >。每个键的值是向量的索引，向量的每个元素都指向映射元素。向量元素没有特定的顺序。添加元素时，请将其放在向量的末尾。当您删除一个元素并且它不是向量中的最后一个元素时，将最后一个元素移动到已删除元素的位置。

于 2011-11-29T00:00:04.217 回答
1

如果您知道集合中元素的分布，则可以随机选择 key（具有相同分布）并使用std::set::lower_bound. 不过，这有很多。

int main() {
    std::set<float> container;
    for(float i=0; i<100; i += .01)  
        container.insert(i);
    //evenish distribution of 10000 floats between 0 and 100.
    float key = std::rand() *10000f / RAND_MAX; //not random, sue me
    std::set<float>::iterator iter = container.lower_bound(key); //log(n)
    std::cout << *iter;
    return 0;
}
于 2011-11-28T22:01:39.157 回答
0

对于std::unordered_set<int> s：

R1 ）随机抽取min(s)..max(s)

2）如果R在s：返回R

3)

newIter = s.insert(R).first;
newIter++;
if (newIter == s.end()) {
    newIter = s.begin();
}
auto result = *newIter;
s.erase(R);
return result;

对于有序集（std::set），概率取决于元素之间的距离。unordered_set 通过散列随机化。

我希望这会有所帮助。

PS转换std::set<V>成std::set<std::pair<int, V>>（其中第一个元素是第二个的散列）使该方法适用于任何可散列的V。

于 2014-02-11T13:24:00.987 回答
0

您可以使用此构造函数制作地图的随机排序副本

template <class InputIterator>
set(InputIterator f, InputIterator l,
    const key_compare& comp)

..并传递一个比较键的哈希值（或其他确定性扩展函数）的比较器。然后根据这个新映射获取“最小”键。

您可以构建一次映射并在多个“随机”元素请求中分摊成本。

于 2011-11-28T21:05:40.143 回答