0

Im trying to write a program that outputs the next permutation of a numerical string in lexicographic order but i am getting a memory error:

terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc
Aborted

I'v never had this problem before, any ideas? here is the full program:

#include<iostream>
#include<vector>

using namespace std;

vector<char> Next_Permutation(vector<char> InList);
void Reverse_Tail(vector<char>& List,int k);
vector<char> Swap(vector<char> InputList,int k, int l);
vector<char> GetInput();
int Find_K(vector<char> List);
int Find_l(vector<char> List,int k);
int Factorial(int n);

int main(){

 vector<char> Input = GetInput();//Getting initial input use 1234 for test

 int limit = Factorial(Input.size()); // finds how many permutations will be made

 vector<char>* AllPerms = new vector<char>[limit]; //AllPerms is the collection of all permutations(it is an array of vectors where each vector is a permutation)

 AllPerms[0] = Input; //setting intial permutation;

 for(int i=1;i<2;i++){


   // here is where i believe the program crashes. I've tried      test = Next_Permutation(AllPerms[i-1])       then 
   // doing        AllPerms[i] = Test          and the program runs through the first line fine but crashed on AllPerms[i] = Test?

  AllPerms[i] = (Next_Permutation(AllPerms[i-1]));

}
 for(int j=0; j < limit;j++){

  for(int i=0;i<AllPerms[j].size();i++){

     cout << AllPerms[j][i] << " " ;

}

cout << endl;

 }
 //cout << endl << "K = " << K << endl<< "l = " << l << endl<< endl;


  cout << endl<< endl;
  return 0;
}

int Factorial(int n){

  if(n==0)
    return 1;
  else
    return n*Factorial(n-1);

}

vector<char> Next_Permutation(vector<char> InList){

  int K = Find_K(InList);
  int l = Find_l(InList,K);

  vector<char> Output = Swap(InList,K,l);

  Reverse_Tail(Output,K);

}

void Reverse_Tail(vector<char>& List,int k){

  int i = k+1;

  int lim = (List.size() - i)/2;

  int len = List.size()-1;

  while(i < (List.size() - lim -1)){

    List = Swap(List,i,len);
    len--;
    i++;

}

}

vector<char> Swap(vector<char> InputList,int k, int l){

  vector<char> OutList = InputList;

  int Temp = OutList[l];

  OutList[l] = InputList[k];

  OutList[k] = Temp;

  return OutList;

}

int Find_l(vector<char> List,int k){

  int l=List.size()-1;

  while(List[l] < List[k]){

    l--;

  }

  return l;

}

int Find_K(vector<char> List){

  int k = List.size()-2;

  while(List[k] > List[k+1]){

    k--;

  }

  if(k == List.size()-1){

    return -1;

  }

  return k;

}

vector<char> GetInput(){

vector<char> InputString;

cout << "Please input the string of symbols you would like to gain all permutations of: ";

char temp = 0 ;

while( temp != '\n' ){

cin.get(temp);

InputString.push_back(temp);

}

InputString.pop_back();

return  InputString;

}
12
  • 3
    std::bad_alloc is thrown when new fails. I would look to see what limit is set to. Using the factorial as an array limit can very VERY quickly run out of memory.
    – Dave S
    Sep 1, 2011 at 17:12
  • 1
    1. Fix code indentation. 2. Attach a debugger and see where the exception originates. Sep 1, 2011 at 17:13
  • I would replace vector<char>* with vector<vector<char>> for clarity, took me a moment to realize that wasn't a typo/bug. Sep 1, 2011 at 17:13
  • How big is your input string when it crashes?
    – Kerrek SB
    Sep 1, 2011 at 17:17
  • this looks like a simple debug session activity would solve it. have you tried it yourself before submitting to the SO "human compilers"?
    – NirMH
    Sep 1, 2011 at 17:19

1 Answer 1

2

You don't return a value from Next_Permutation. Failure to return a value from any function but main invokes undefined behavior, where the compiler and the program are free to do anything they like. My Solaris compiler refuses to accept the program, whereas my Linux compiler compiles the program, but then the program crashes because free detected an invalid pointer at some point. Both are valid ways to treat something that's undefined.

When you have undefined behavior, it's generally not wise to put much effort into figuring out exactly why your program is behaving strangely because whatever you're seeing isn't necessarily reproducible by anyone else, and possibly not even reproducible by you. Make sure you have a valid program, and then start debugging. Although it's possible that you're legitimately running out of memory, it's more likely that the exception is being thrown while trying to copy something that's not even a valid object in the first place.

Your compiler probably offers some diagnostics, but you might have to request them when you run it. If you're using g++, make sure to include the -Wall option, which enables "all" warnings. (There are a few obscure ones that aren't enabled, but you generally don't need to worry about them.)

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.