bad_alloc () при рекурсивном создании комбинаций и сохранении в вектор - PullRequest
Новая
       29

bad_alloc () при рекурсивном создании комбинаций и сохранении в вектор

0 голосов
/ 15 ноября 2018

Обзор : я пытаюсь создать комбинации из набора символов с определенным начальным символом, где каждая комбинация имеет определенную длину в пределах диапазона.Например, если мой набор символов {A, B, C, D} и начальный префикс 'A', то мои комбинации для длин от 1 до 3: A, AA, AB, AC, AD, AAA, AAB, AAC, AAD, ...., ДОБАВИТЬ.

Задача : Я создаю каждую комбинацию рекурсивно.Проблема заключается в том, что, когда я пытаюсь сохранить комбинации с вектором для большего набора символов для диапазона длин от 1 до 8 (что я, очевидно, понимаю, это много комбинаций), я получаю ошибку дампа ядра bad_alloc.Насколько я понимаю, это означает, что у меня закончилась память (возможно, из-за переполнения моего вектора).Я хочу попробовать выделить этот вектор в куче и сохранить его глобальным.Ниже приведен мой текущий код, прежде чем пытаться изменить: 

#include <iostream>
#include <vector>
#include <string>
#include <time.h>
using namespace std;

#define SIZE_SET 15 // sizeof set below, set of characters to create permutations from
char set[] = {'A','B','C','D','E','F','G','H','I','J','K','L','M','N','O'};            
void ProducePerms(vector<string>&, string, const int, const int);

int main(){

    // Timing program run time
    clock_t t1, t2;
    t1 = clock();

    cout << "Starting time" << endl;

    vector<string> perms; // Stores permutations
    string start_prefix = "B"; // All permutations of lengths 1-8 begin with this prefix
    int length = 8; // Maximum length of permutation

    // Produce lengths 1-8 permutations starting with prefix
    for(int l = 0; l < length; l++){
        ProducePerms(perms, start_prefix, SIZE_SET, l);
    }

    // End run time
    t2 = clock();
    cout << "\nTime elapsed: " << (t2-t1)/(double)CLOCKS_PER_SEC << endl << endl;

    return 0;
}

void ProducePerms(vector<string>& vec, string prefix, const int n, const int length){
    if(length == 0){
       vec.push_back(prefix);
    }
    else{
       if(length == 1){
           for(int j = 0; j < n; j++){
               vec.push_back(prefix + set[j]);
            }
        }
        else{
            for(int i = 0; i < n; i++){
                ProducePerms(vec, prefix + set[i], n, length - 1);
            }
        }
    }
}

Также, если у кого-то есть какие-либо предложения о том, как я могу приспособить это к использованию pthreads, которые были бы полезны.В настоящее время я думаю о создании pthreads для вычисления комбинаций определенной длины.

...