как удалить случайные элементы из вектора, не повторяя их и сохраняя порядок элементов? Переполнение стека

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;

}

0

c++elements preserve random vector

Решение

Другие решения

Других решений пока нет …

Источник

Accepted Answer

Я бы предложил использовать алгоритм, описанный в Программирование Жемчуг для этой задачи (Алгоритм S от Кнута Получисленные алгоритмы). Идея состоит в том, чтобы выбирать элементы по порядку с вероятностью s / r, где s — число, оставшееся для выбора, и r — количество оставшихся элементов. Это выбирает m элементов из n по порядку, причем каждый элемент имеет равные шансы быть выбранным.

Эта реализация использует copy_if для копирования выбранных элементов в новый вектор. Скорее всего, это будет более эффективно, чем пытаться удалить элементы из исходного вектора, так как при удалении вы избегаете смещения всех элементов внутри вектора. Вы можете использовать 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, " "));
}

1