如何從矢量中移除隨機元素而不重複它們並保留元素順序？ C++

Question

我想從矢量中去除一定數量的隨機元素，同時保留元素順序。我爲這個目的編寫了這段代碼，它在我爲小向量運行時運行良好，但是當我爲大運行運行它（1000個總元素除去200個隨機元素）時，它似乎不能正常工作。

任何人都可以給我一個正確的方向踢嗎？

#include<iostream> 
#include<cmath> 
#include<stdio.h> 
#include<stdlib.h> 
#include<fstream> 
#include<string> 
#include<iomanip> 
#include<vector> 
#include "mersenne.cpp" 
#include "userintf.cpp" 
#include "stocc.h" 
#include "stoc1.cpp" 
#include<time.h> 
#include <algorithm> 
#include "./Mersenne-1.1/MersenneTwister.h" 



MTRand mtrand1; 

using namespace std ; 

int main() 
{ 
    vector<string> stable ; 


    stable.push_back("CCAAAATCAACTCCTCGAGGAAGTAAATGCGATGGCTGTGTTACAGCGTGTATCGCGTCATGTCCTTGTTGCTGTAATTTCCACTGTCAGGACGATGAAAGCGCCGGGACGAAGGGCCATCAGGGGCTACTCCAGACCGACGAGTTCCCTCTCTGCCAGAAAATATGTTGTGGTGCGAGTTTTAACATACACTGCGGGACCAGCAAGCCG") ; 
    stable.push_back("CCAAAATCAACTCCTCGAGGAAGTAAATGCGATGGCTGTGTTACAGCGTGTATCGCGTCATGTCCTTGTTGCTGTAATTTCCACTGTCAGGACGATGAAAGCGCCGGGACGAAGGGCCATCAGGGGCTACTCCAGACCGATGAGTTCCCTCTCTGCCAGAAAATATGTTGTGGTGCGAGTTTTAACATACACTGCGGGACCAGCAAGCCA") ; 
    stable.push_back("CCAAAATCAACTCCTCGAGGAAGTAAATGCGATGGCTGTGTTACAGCGTGTATCGCGTCATGTCCTTGTTGCTGTAATTTCCACTGTCAGGACGATGAAAGCGCCGGGACGAAGGGCCATCAGGGGCTACTCCAGACCGACGAGTTCCCTCTCTGCCAGAAAATATGTTGTGGTGCGAGTTTTAACATACACTGCGGGACCAGCAAGCCA") ; 
    stable.push_back("CCAAAATCAACTCCTCGAGGAAGTAAATGCGATGGCTGTGTTACAGCGTGTATCGCGTCATGTCCTTGTTGCTGTAATTTCCACTGTCAGGACGATGAAAGCGCCGGGACGAAGGGCCATCAGGGGCTACTCCAGACCGACGAGTTCCCTCTCTGCCAGAAAATATGTTGTGGTGCGAGTTTTAACATACACTGCGGGACCAGCAAGCCA") ; 
    stable.push_back("CCAAAATCAACTCCTCGAGGAAGTAAATGCGATGGCTGTGTTACAGCGTGTATCGCGTCATGTCCTTGTTGCTGTAATTTCCACTGTCAGGACGATGAAAGCGCCGGGACGAAGGGCCATCAGGGGCTACTCCAGACCGACGAGTTCCCTCTCTGCCAGAAAATATGTTGTGGTGCTAGTTTTAACATACACTGCGGGACCAGCAAGCCA") ; 
    stable.push_back("CCAAAATCAACTCCTCGAGGAAGTAAATGCGATGGCTGTGTTACAGCGTGTATCGCGTCATGTCCTTGTTGCTGTAATTTCCACTGTCAGGACGATGAAAGCGCCGGGACGAAGGGCCATCAGGGGCTACTCCAGACCGACGAGTTCCCTCTCTGCCAGAAAATATGTTGTGGTGCTAGTTTTAACATACACTGCGGGACCAGCAAGCCA") ; 
    stable.push_back("CCAAAATCAACTCCTCGAGGAAGTAAATGCGATGGCTGTGTTACAGCGTGTATCGCGTCATGTCCTTGTTGCTGTAATTTCCACTGTCAGGACGATGAAAGCGCCGGGACGAAGGGCCATCAGGGGCTACTCCAGACCGACGAGTTCCCTCTCTGCCAGAAAATATGTTGTGGTGCGAGTTTTAACATACACTGCGGGACCAGCAAGCCA") ; 
    stable.push_back("CCAAAATCAACTCCTCGAGGAAGTAAATGCGATGGCTGTGTTACAGCGTGTATCGCGTCATGTCCTTGTTGCTGTAATTTCCACTGTCAGGACGATGAAAGCGCCGGGACGAAGGGCCATCAGGGGCTACTCCAGACCGACGAGTTCCCTCTCTGCCAGAAAATATGTTGTGGTGCGAGTTTTAACATACACTGCGGGACCAGCAAGCCA") ; 
    stable.push_back("CCAAAATCAACTCCTCGAGGAAGTAAATGCGATGGCTGTGTTACAGCGTGTATCGCGTCATGTCCTTGTTGCTGTAATTTCCACTGTCAGGACGATGAAAGCGCCGGGACGAAGGGCCATCAGTGGCTACTCCAGACCGACGAGTTCCCTCTCTGCCGGAAAATATGTCGTGGTGCGAGTTTTAACATACACTGCGGGACCAGCAAGCCA") ; 
    stable.push_back("CCAAAATCAACTCCTCGAGGAAGTAAATGCGATGGCTGTGTTACAGCGTGTATCGCGTCATGTCCTTGTTGCTGTAATTTCCACTGTCAGGACGATGAAAGCGCCGGGACGAAGGGCCATCAGGGGCTACTCCAGACCGACGAGTTCCCTCTCTGCCAGAAAATATGTTGTGGTGCGAGTTTTAACATACACTGCGGGACCAGCAAGCCA") ; 


//////////////////////////////////////////////////////////// 



    vector<int> dict ;//Remembers random values 

    dict.push_back(mtrand1.randInt(9)) ; 

    int dummy = 0 ; 

    bool found = false ; 

    int counter = 0 ; 

    int randomvalue ; 

    while(counter < 5) 
    {    
     dummy = dict.size() ; 

     found = false ; 

     randomvalue = mtrand1.randInt(9) ;  

     for (int j = 0 ; j < dummy ; j++) 
     { 
      if (dict[j] == randomvalue) 
      { 
       found = true ; 

       break ; 
      } 
     } 

     if(!found) 
     {   
      dict.push_back(randomvalue) ; 

      stable[randomvalue] = "flag" ;  

      counter++ ; 
     }  
    } 

    stable.erase(remove(stable.begin(), stable.end(), "flag"), stable.end()); 



///////////////////////////////////////////////////////// 

cout << "This is the new stable array: " << endl ; 

for(int i = 0 ; i < stable.size() ; i++) 
{ 
    cout << stable[i] << endl ; 
} 

return 0; 

} 

Answer 1

我會建議使用在編程珠璣這個問題描述的算法（算法S從Knuth的半數值算法）。這個想法是按照概率s/r的順序選擇元素，其中s是剩餘的數字，r是剩餘元素的數量。這將從n中選擇m個元素，以便每個元素具有相同的選擇機會。

此實現使用copy_if將選定元素複製到新矢量。這通常可能比嘗試從原始矢量中移除元素更有效率，因爲您可以避免在刪除時向量中所有元素向下移動。如果您不需要保留原始向量以避免附加元素副本，則可以在C++ 11中使用move_iterator。

#include <algorithm> 
#include <iostream> 
#include <iterator> 
#include <random> 
#include <string> 
#include <vector> 

using namespace std; 

template<typename I1, typename I2, typename Engine> 
I2 copyRandomM(I1 first, I1 last, I2 dest, int m, Engine& eng) { 
    int n = distance(first, last); 
    return copy_if(first, last, dest, [&](decltype(*first)) { 
     return uniform_int_distribution<>(0, --n)(eng) < m ? --m, true : false; }); 
} 

int main() { 
    mt19937 engine; 
    auto v = vector<string>{ "orange", "apple", "banana", "pear", "kiwi", "tangerine" }; 
    vector<string> selection(4); 
    copyRandomM(begin(v), end(v), begin(selection), selection.size(), engine); 
    copy(begin(selection), end(selection), ostream_iterator<string>(cout, " ")); 
}