我想从 vector 中删除确定数量的随机元素,同时保留元素顺序。我为此目的编写了这段代码,当我为小 vector 运行它时它运行良好,但当我为大 vector 运行它时(总共 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;
}
最佳答案
对于这个问题,我建议使用Programming Pearls 中描述的算法(来自 Knuth 的半数值算法 的算法 S)。这个想法是以概率 s/r 按顺序选择元素,其中 s 是剩余要选择的数量,r 是剩余元素的数量。这从 n 个元素中选择 m 个元素,每个元素被选中的机会均等。
此实现使用 copy_if 将选定元素复制到新 vector 。这通常可能比尝试从原始 vector 中删除元素更有效,因为您在删除时避免了 vector 中所有元素的向下移动。如果您不需要保留原始 vector 以避免额外的元素拷贝,则可以将 move_iterators 与 C++11 结合使用。
#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, " "));
}
关于c++ - 如何从 vector 中删除随机元素而不重复它们并保留元素顺序? C++,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/19647998/