選擇一個隨機子集的一般算法實現

假設我們要從大小爲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

選擇一個隨機子集的一般算法實現

回答

相關問題