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

不是最有效的，因为它使用三个“小”的载体，但避免了必须适应费 - 耶茨算法来对向量的一个子集进行操作。在实践中，你可能希望这是一个在一对随机访问迭代器而不是向量上运行的函数模板。我没有这样做，因为我认为它会混淆代码，而你没有要求。我也会采取一个大小，而不是一个比例，留给呼叫者决定如何将分数舍入。