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

Я хочу удалить определенное количество случайных элементов из вектора, сохраняя порядок элементов. Я написал этот код для этой цели, и он хорошо работает, когда я запускаю его для небольших векторов, но когда я запускаю его для больших (всего 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;

}

c++ random vector preserve elements
person user2171927    schedule 29.10.2013    source источник
comment
Что вы имеете в виду под не работает должным образом?   -  person j_random_hacker    schedule 29.10.2013
comment
Что возвращает mtrand1.randInt( 9 )?   -  person Beta    schedule 29.10.2013
comment
@j_random_hacker Этот код является частью гораздо большей программы. Программа производит расчет мутационной устойчивости после удаления 200 элементов. Этот процесс повторяется 500 раз. Эта величина должна меняться со временем, но с этим кодом она остается постоянной в течение этих 500 итераций.   -  person user2171927    schedule 29.10.2013
comment
@Beta Возвращает случайное число от 0 до 9.   -  person user2171927    schedule 29.10.2013
comment
Если вам нужно удалить случайные элементы, почему бы не удалить из 200 случайных позиций в векторном массиве?   -  person Rohit Vipin Mathews    schedule 29.10.2013
comment
Кажется почти уверенным, что проблема в вашем генераторе случайных чисел MTRand, который находится в коде, который вы нам не показали. Каждый экземпляр MTRand создает одну и ту же последовательность случайных чисел. Если это так (и это достаточно легко проверить), вы должны либо выяснить, как инициализировать разные экземпляры с разными начальными значениями, либо создать один экземпляр вне цикла и использовать его во всех 500 итерациях.   -  person Beta    schedule 29.10.2013
comment
Это не ответ на ваш вопрос, и вы, возможно, уже это знаете, но std::vector выделяет непрерывный блок памяти, что означает, что стирание из вектора часто приводит к перераспределению памяти и перемещению элементов, которые не используются. не стирается. Если вам нужно много удалить из середины коллекции, вам лучше подойдет список.   -  person sbaker    schedule 29.10.2013

Ответы (1)


arrow_upward
2
arrow_downward

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

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