C++向量隨機隨機洗牌的一部分

Question

什麼是洗牌向量中的一定比例的元素的最佳方式。假設我想要10％或90％的載體改組。 不一定是第一個10％，但只有10％全線。

TIA

Answer 1

將Fisher-Yates shuffle修改爲不對數組中10％的指數做任何事情。

這是我發佈（來自維基百科）和修改的java代碼，但我認爲你可以將它翻譯成C++，因爲這更像是一個算法問題而不是語言問題。

public static void shuffleNinetyPercent(int[] array) 
{ 
    Random rng = new Random();  // java.util.Random. 
    int n = array.length;   // The number of items left to shuffle (loop invariant). 
    while (n > 1) 
    { 
     n--;       // n is now the last pertinent index 
     if (rng.nextDouble() < 0.1) continue; //<-- ADD THIS LINE 
     int k = rng.nextInt(n + 1); // 0 <= k <= n. 
     // Simple swap of variables 
     int tmp = array[k]; 
     array[k] = array[n]; 
     array[n] = tmp; 
    } 
} 

Answer 2

單程可使用，性病:: random_shuffle（），通過控制輸入範圍控制％....

Answer 3

爲什麼不執行隨機選擇的位置處，其中，N由下式確定N個互換百分比？

因此，如果我有100個元素，10％洗牌將執行10次交換。每次交換隨機選取數組中的兩個元素並切換它們。

Answer 4

您可以使用shuffle bag算法來選擇數組的10％。然後在該選擇上使用正常的隨機播放。

Answer 5

如何編寫自己的隨機迭代器，並使用random_shuffle，這樣的事情：（沒有經過充分測試，只是爲了得到一個想法）

template<class T> 
class myRandomIterator : public std::iterator<std::random_access_iterator_tag, T> 
{ 
public: 
    myRandomIterator(std::vector<T>& vec, size_t pos = 0): myVec(vec), myIndex(0), myPos(pos) 
    { 
     srand(time(NULL)); 
    } 

    bool operator==(const myRandomIterator& rhs) const 
    { 
     return myPos == rhs.myPos; 
    } 

    bool operator!=(const myRandomIterator& rhs) const 
    { 
     return ! (myPos == rhs.myPos); 
    } 

    bool operator<(const myRandomIterator& rhs) const 
    { 
     return myPos < rhs.myPos; 
    } 

    myRandomIterator& operator++() 
    { 
     ++myPos; 
     return fill(); 
    } 

    myRandomIterator& operator++(int) 
    { 
     ++myPos; 
     return fill(); 
    } 

    myRandomIterator& operator--() 
    { 
     --myPos; 
     return fill(); 
    } 

    myRandomIterator& operator--(int) 
    { 
     --myPos; 
     return fill(); 
    } 



    myRandomIterator& operator+(size_t n) 
    { 
     ++myPos; 
     return fill(); 
    } 

    myRandomIterator& operator-(size_t n) 
    { 
     --myPos; 
     return fill(); 
    } 


    const T& operator*() const 
    { 
     return myVec[myIndex]; 
    } 

    T& operator*() 
    { 
     return myVec[myIndex]; 
    } 



private: 
    myRandomIterator& fill() 
    { 
     myIndex = rand() % myVec.size(); 
     return *this; 
    } 

private: 
    size_t myIndex; 
    std::vector<T>& myVec; 
    size_t myPos; 

}; 

int main() 
{ 
    std::vector<int> a; 
    for(int i = 0; i < 100; ++i) 
    { 
     a.push_back(i); 
    } 

    myRandomIterator<int> begin(a); 
    myRandomIterator<int> end(a, a.size() * 0.4); 

    std::random_shuffle(begin, end); 

    return 0; 
} 

Answer 6

你可以試試這個：

分配一個隨機數矢量的每個元素。隨機數在您指定的隨機數中最小的10％隨機數進行隨機播放：您甚至可以想象用佔位符替換向量中的10％，然後根據其隨機數對10％進行排序，然後將它們插入矢量佔位符的地方。

Answer 7

如果你有SGI的std::random_sample擴展名，你可以這樣做。如果不是，那麼在一個函數之上實現random_sample很容易，該函數返回指定範圍內的均勻分佈的隨機整數（Knuth，第2卷，「算法R」）。

#include <algorithm> 
#include <vector> 
using std::vector; 

void shuffle_fraction(vector<int> &data, double fraction) { 
    assert(fraction >= 0.0 && fraction <= 1.0); 

    // randomly choose the indices to be shuffled 
    vector<int> bag(data.size()); 
    for(int i = 0; i < bag.size(); ++i) bag[i] = i; 

    vector<int> selected(static_cast<int>(data.size() * fraction)); 
    std::random_sample(bag.begin(), bag.end(), selected.begin(), selected.end()); 

    // take a copy of the values being shuffled 
    vector<int> old_value(selected.size()); 
    for (int i = 0; i < selected.size(); ++i) { 
     old_value[i] = data[selected[i]]; 
    } 

    // choose a new order for the selected indices 
    vector<int> shuffled(selected); 
    std::random_shuffle(shuffled.begin(), shuffled.end()); 

    // apply the shuffle to the data: each of the selected indices 
    // is replaced by the value for the corresponding shuffled indices 
    for (int i = 0; i < selected.size(); ++i) { 
     data[selected[i]] = old_value[shuffled[i]]; 
    } 
} 

不是最有效的，因爲它使用三個「小」的載體，但避免了必須適應費 - 耶茨算法來對向量的一個子集進行操作。在實踐中，你可能希望這是一個在一對隨機訪問迭代器而不是向量上運行的函數模板。我沒有這樣做，因爲我認爲它會混淆代碼，而你沒有要求。我也會採取一個大小，而不是一個比例，留給呼叫者決定如何將分數舍入。