Where do I even begin with a Core Dump (Segmentation Fault)?

vaderboi (140)
When I tried to compile my program, I got this error:

"Segmentation fault (core dumped)"

The problem is, I have no idea where to even start. With a segmentation fault there is no specific line that I can look at because the compiler does not specify one. Memory access in C++ is something I am still new to so any pointers (no pun intended) in the right direction would be great.

Here is my program "permute.cpp":

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
 
 #include <string>
 #include <cstring>
 #include <stdio.h>
 
 void permute( const std::string & str );
  
 void permute( const  std::string & str, int low, int high );
  
 void swap( std::string & str, int index1, int index2 );
 

 int main()
 {
 
     permute( "abcd" );
 
     return 0;
 
 }
 
 
 void permute( const std::string & str )
 {
 
     permute( str, 0, str.length() - 1 );
 
 }
 
 void permute( const std::string & str, int low, int high )
 {
     /*if low is equal to (high - 2), that means base case
     * is reached and the program will swap the third to last
     * element with the second to last element (i.e. "abcd" to "acbd")
     * and subsequently the third to last element with       
     * the last element (i.e. "abcd" to "adcb").
     * After each swap, there will be a second swap between the second to
     * last element and the last element (i.e. "abcd" to "abdc").
     * The program will print out the element after every single swap*/
     if( low == (high - 2) )
     {
         for( unsigned int i = low; i <= high; i++ )
         {
             std::string tempStr = str;
             const char* charStr = tempStr.c_str();

                 if( i == low )
                 {
                     printf("%s ", charStr );

                     swap( tempStr, low + 1, low + 2 );
 
                     printf("%s ", charStr );
                 }
                 else
                 {
                     swap( tempStr, low, i );

                     printf("%s ", charStr );

                     swap( tempStr, low + 1, low + 2 );

                     printf("%s ", charStr );
                 }
         }

     }
     /*if base case is not reached, then that means that nothing will be      
      * printed out. Instead, low will be iterated and the initial string
      * entered as a parameter will then be used to recursively call
      * the permute function again. The recursion stack will the end at the
      * base case. When going back up the stack, however, the element at low
      * will be swapped with every element after it and then THAT value will
      * be entered in to a recursive loop until the base case is again reached
      * (i.e. if low is at index location "1" then "abcde" will be entered
      * in to the recursive loop, then "acbde", then "adcbe", then "aecdb").
      */
      else
      {
 
          for( unsigned int i = low; i < high - low; i++ )
          {
              std::string tempStr = str;
 
              if( i == low )
              {
                  int currentLowValue = low++;

                  permute( tempStr, currentLowValue, high );
              }
              else
              {
                  swap( tempStr, low, i );
 
                  permute( tempStr, low, high );
              }
 
          }
      }
  }


 void swap( std::string & str, int index1, int index2 )
 {

     char tempVar = str[index1];

     str[index1] = str[index2];

     str[index2] = tempVar;

 }

Thomas1965 (4571)
Seems to be a stack overflow since your recursive permute function will never end.
Adding some output is a useful debugging technique
Add this snippet printf("str = %s\tlow = %d\thigh = %d\n", str.c_str(), high, low); at the top of
void permute( const std::string & str, int low, int high )
lastchance (6980)
Your logic is all over the place.

In the recursive case, i is the index that you are going to swap with low. You can reduce this whole part to
1
2
3
4
5
6
7
8
9
 
      else
      {
          for( unsigned int i = low; i <= high; i++ )      // i is the index you will swap into the low position
          {
             std::string tempStr = str;
             if( i != low ) swap( tempStr, low, i );
             permute( tempStr, low + 1, high );
          }
      }



I have absolutely no idea what you are trying to do as base case. You can reduce this to the simple "if I'm down to the last letter then there is no more to do so print it". i.e
if( low == high ) printf("%s ", str.c_str() );


There is a neater solution at
https://stackoverflow.com/questions/7537791/understanding-recursion-to-generate-permutations
Last edited on
Repeater (3046)
The problem is, I have no idea where to even start.


With a debugger.

http://www.cplusplus.com/articles/iwTbqMoL/
Repeater (3046)
If you don't like the hands on debugging approach, there's always using an IDE's debugger: https://ibb.co/vLPX8D5

The free VS 2017 IDE shown there reveals the problem to be a stack overflow; your function recurses so many times that the stack simply runs out of memory. Every time you call a function, you use some stack memory. Every time you leave a function, you get that memory back to use again. Your code calls the function over and over and over and eventually you've used up all the available stack memory.
vaderboi (140)
Thank you all for the pointers thus far. I tried to trace the logic of my program and, you are all right, the logic doesn't make any sense. I think I am going to start it from scratch. I will let you know any progress I make. Thanks @Repeater, for the debugger suggestions.
vaderboi (140)
Figured it out! I just had to re-work my logic. I didn't find out what caused the memory leak but it may have been an infinite loop. Ran it in the compiler and it worked. Granted, it only works with strings that are of length "3" or higher. I am sure I could put in conditional statements to account for different inputs but for the purposes of what I am trying to do, I am content with the program.

Thank you all for the help!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
 
#include <string>
#include <cstring>
#include <stdio.h>

void permute(std::string & str);
void permute(std::string & str, int low, int high);
void swap(std::string & str, int first, int second);


int main()
{
	std::string permuteStr = "abc";

	permute(permuteStr);

	return 0;
}

void permute(std::string & str)
{
	int stringLen = str.length();

	permute(str, 0, stringLen - 1);
}

void permute(std::string & str, int low, int high)
{
	std::string tempStr = str;
	
	/*if "low" is 2 less than high, that means the base case
	 * has been reached. The program will then print the six
	 * possible combinations that can be formed by swapping 
	 * around the last three elements of the string (because 
	 * 3! == 6).*/
	if (low == (high - 2))
	{
		for (unsigned i = 0; i < 3; i++)
		{
			tempStr = str;
			
			//no swap is done on the first iteration of the for loop
			if (i != 0)
			{
				swap(tempStr, low, low + i);	
			}

			printf("%s ", tempStr.c_str());

			swap(tempStr, low + 1, low + 2);
			printf("%s ", tempStr.c_str());

		}
	}
	/*if base case has not been reached, then recurse the
	 * string but with "low" == low + 1. This, in effect, 
	 * moves the focus towards every character at low and after.
	 * The for loop will swap the character at low with every
	 * character after until the for loop terminates. This makes it
	 * so that every combination that can be formed by swapping around
	 * every character at low and after will eventually be printed out
	 * once the base case is reached. After the for loop terminates, 
	 * the program goes up the recursion stack until the program has reached
	 * the top of the stack and the top stack's for loop has terminated*/
	else
	{
		for (unsigned i = low; i <= high; i++)
		{
			permute(tempStr, low + 1, high);

			tempStr = str; 
			swap(tempStr, low, i + 1);
		}
	}
	
}


void swap(std::string & str, int first, int second)
{
	char tempVar = str[first];
	str[first] = str[second];
	str[second] = tempVar;
}
Repeater (3046)
I didn't find out what caused the memory leak


There was no memory leak.

You had a function that called itself so many times that eventually you had a million billion (i.e. some huge number of them) instances of that function taking up all the memory on the stack.

Every time you call a function it takes up some memory. Every time the function ends, you get that memory back. If a function calls itself over and over, never ending, always calling itself again, eventually you run out of memory.

https://en.wikipedia.org/wiki/Stack_overflow
Last edited on
vaderboi (140)
Ah, good to know. Thank you @Repeater.
jonnin (11438)
gdb (unix command should be there with your compiler) will let you look at core dump files, though I rarely bother. With experience, you can spot most of the core dump creating crash problems in code pretty quickly, just as Thomas did right off by glancing at your code. Until you get to that point, you may want to read the spew from the tool to see what the issue was.
Last edited on
Topic archived. No new replies allowed.