选择一个随机子集的一般算法实现

假设我们要从大小为n的总集合中选择一个大小为m的随机子集。由于总集合中的每个元素都可以使用来自S = {0, 1, 2, ..., (n - 1)}的唯一索引来标识。该问题相当于从S中随机选择m不同的元素。选择一个随机子集的一般算法实现

一个简单的算法会重复地调用一个伪随机数生成器rand来从S生成随机数。如果之前已经生成了号码，只需再试一次。该算法终止，直到生成不同的数字为m。该算法的最佳空间复杂度为O(1)，但可能会调用rand多于m次。

我更关心的是时间复杂性而不是空间复杂性，如果合理的话，我会很乐意为时间交易空间。所以我实现了以下算法。它调用rand完全是min{m, (n - m)}次，但以O(n)增加的空间复杂度为代价。（原代码，可以发现here）

template <typename Clock = std::chrono::high_resolution_clock> 
auto tick_count() { 
    return Clock::now().time_since_epoch().count(); 
} 

template <typename OutIt, typename RAND = std::minstd_rand, 
      typename Uint = typename RAND::result_type> 
void random_subset(std::size_t m, std::size_t n, OutIt it, RAND&& rand = 
        RAND(static_cast<Uint>(tick_count()))) { 
    assert(n - 1 <= rand.max()); 
    assert(m <= n); 
    if (m == 0) return; 
    auto swapped = false; 
    auto tmp = n - m; 
    if (tmp < m) { 
    m = tmp; 
    swapped = true; 
    } 
    std::vector<std::size_t> indices(n); 
    std::iota(indices.begin(), indices.end(), static_cast<std::size_t>(0)); 
    auto back_it = indices.end(); 
    for (std::size_t i = 0; i < m; ++i) { 
    auto idx = rand() % (n - i); 
    std::swap(indices[idx], *--back_it); 
    } 
    swapped ? std::copy(indices.begin(), back_it, it) : 
      std::copy(back_it, indices.end(), it); 
}

我不知道是否该算法可以在性能方面得到进一步提高。对通用实现的改进也是受欢迎的。

来源

2016-01-30 Lingxi

为什么不使用['std :: uniform_int_distribution']（http://en.cppreference.com/w/cpp/numeric/random/uniform_int_distribution）？ –

@πάνταῥεῖ因为我从'0 ..（n - 1）'生成随机数。基本的URNG就足够了。 – Lingxi

@Lingxxi你能设置n的限制吗？你能预先指定范围n可以是[n_min，n_max]吗？ – 4pie0

也许你可以使用Fisher-Yates algorithm的一个非常小的变型随机洗牌，特别是second variant of the Durstendfeld version：

-- To shuffle an array a of n elements (indices 0..n-1): 
for i from 0 to n−2 do 
    j ← random integer such that 0 ≤ j < n-i 
    exchange a[i] and a[i+j]

刚刚从n将循环终止 - 2到你所需要的。

在证明中，循环不变是一旦索引我已被传递，直到它的数组是一个随机洗牌。因此，您可能会提前终止所需的结果。

来源

2016-01-30 12:06:28

选择一个随机子集的一般算法实现

回答

相关问题