[seanohue]

I'm doing recursion now in my C++ class and I am stuck with my code. I'm trying to write a program that will compute all the permutations for a number. Say I enter 4, which gives me 24 permutations of 1234 since 4! = 24. My code thus far is this:

Code:

[left]#include <iostream> #include <vector> using namespace std; typedef vector<int> vint; int factorial(int n) { if(n == 0) return 1; int smaller_factorial = factorial(n - 1); int result = smaller_factorial * n; return result; } vector<vint> permutations(int permute) { int vec_size = factorial(permute); vector<vint> supervec(vec_size); vint vec(permute); if(permute == 1) { vec[0] = 1; supervec[0] = vec; return supervec; } else for(int j = 1; j == permute; j++) { vec[j - 1] = j; } for(int i = 0; i < supervec.size(); i++) { for(int k = 0; k < vec.size(); k++) { for(int n = ; n < ; n++) { vector<int> remain(vec.size() - k - 1); remain[n] = vec[ } for(int m = (vec.size() - 1); n < (vec.size() - k - 1); n++) { vec[vec.size() - k - m] = remain[vec.size() - k - m]; } } supervec[i] = vec; } return supervec; } int main() { cout << "Enter the an integer (not 0)\n"; int x; cin >> x; vector<vint> vec = permutations(x); vector<int> tempvec; for(int i = 0; i < vec.size(); i++) { vec[i] = tempvec; for(int j = 0; j < tempvec.size(); j++) { cout << tempvec[j] << "\n"; } } return 0; }[/left]

What I am attempting to do is create a large vector (supervec) of integer vectors (vints). After each permutation, the rearranged vint is stored in an index of the supervec. My problem is getting the swap to work. I can't figure out how to rearrange the numbers inside the vector and get it to work recursively. That mess of code in the permutations function doesn't work, the only thing that does it the base case. Can anyone point me in the right direction? (well, more like give me a big kick in the rear) I'm stumped at this point.

 

[vagarach]

Well, first thing to do is embrace a recursive design. You want what is true in the trivial base case to hold in the not-so-trivial ones. Also, there is the onion analogy. Think of how you find the permutations of {1} and of {1,2}. The key is to extend the procedure. I'm seeing about some pseudocode, but think about those for now.

and a little story on the pain of recursion:

In my cs for undergraduate math class, we had to write the classic BigInteger class using linked lists or something. Anyway, for some arithmetic function I needed to be able to increment a BigInteger variable. Now I had hit so many obstacles I completely overlooked the fact that I could just call BigInteger.add(1) and be done. Just one simple line. No, I went and wrote a recursive function that stepped through successively smaller linked lists and incremented the actual digit values of the BigInteger. My friend had a big laugh at my expense, and it had taken me days to figure out the correct algorithm.

One way of doing this is: given {1,2,3,4}

all the permutations are:

prepend 1 to permutations({2,3,4})
prepend 2 to permutations({1,3,4})
prepend 3 to permutations({1,2,4})
prepend 4 to permutations({1,2,3})

and permutations({2,3,4}) is given by:

prepend 2 to permutations({3,4})
prepend 3 to permutations({2,4})
prepend 4 to permutations({2,3})

and permutations({3,4}) is given by:

prepend 3 to permutations({4})
prepend 4 to permutations({3})

clearly here your base case is an array of length 1.

Hope that helps. It's odd that they're teaching fundamentals in a language like C++, something less complicated would have been better. There is the problem of how to return values, and one could either append to a very long 1D array, append to a 2D array, or, have a persistent array that is filled, and is passed into the recursive function.

 

[threEchelon]

When we did recursive methods in class, we always put the recursive method call on the return line, like this:

return n+john(n-1);

It might make your code simpler. For instance, your factorial method could be reduced to 2 lines.

 

[error401]

Quote:

Originally Posted by threEchelon /img/forum/go_quote.gif When we did recursive methods in class, we always put the recursive method call on the return line, like this: return n+john(n-1); It might make your code simpler. For instance, your factorial method could be reduced to 2 lines.

Not only does this make the code simpler (and easier to write!), it allows a good compiler to optmize the stack much more effectively. It's referred to as tail recursion, and is very important to functional programming. A function is tail recursive if the last statement executed (prior to returning) in any path is either constant or a recursive function call. Because the last call in the function is recursive, the entire stack frame can be discarded since local data will never be needed again, and the return address is the same. GCC does this, and most strictly functional languages like Scheme require that this optimization happen.

As was mentioned, trying to take a recursive process and turn it into a set of discrete loops is not fun, and will result in very inelegant code. Your code (this problem, at least) will still have loops, but they will not be there to simulate recursion. Aside from the trivial cases where speed is important and the compiler can do a better job with the loop-based code, you're much better off writing recursive code recursively. Your code will shrink, and it'll be very clear what's happening.

When doing recursive code, it's very important to consider the end-case: where you want the recursion to stop, and how to detect it. It's usually best to have this be the first statement in your recursive function (it prevents you from missing the check somewhere in your recursion); check the end condition, and return without recursion. In all other cases, you make a recursive call. This does result in an extraneous function call, but the stack quickly unwinds, and the code is much clearer.

Now, how to approach the actual problem solving process. Recursion is one of those things; at first it's totally alien and you're going to have trouble thinking in terms of it, but once you get it you'll start to recognize what problems will be recursive and it will be clear to you how to solve them. Generally the dataset grows logarithmically with each recursive call. Your inputs will be the data set from the next 'deeper' call (the return value of the recursive call), and the 'static' data for the problem (the initial input).

Let's look at the trivial example, factorial(n). Factorial can be defined recursively, and this is a common definition that the mathematical definition can easily be distilled to. The end case is where n=1, n!=1 (ignoring zero). For all other cases, n!=(n-1)!*n. We can write this in C:
Code:

[left]unsigned int factorial(const unsigned int n) { if (n == 1) return 1; return n * factorial(n-1); }[/left]

Your problem is a little more complex, but not that much. I can't think of a classical recursion example similar enough to yours that I think it will help, so I'm going to lay out how to solve the problem but not give you any code. Hopefully it helps you figure out the thought process.

If you're accepting just '4' as input, you need to generate the set {1,2,3,4}, this will be the input to your first recursive call. Now, each time you 'place' a value, there's one less value available to place in the next spot. This is how your recursion will happen. For each value in the input set, you 'place' that value in your (eventual) output, and make a recursive call with a smaller input set (the placed value removed). This recursive call then does the same thing. The end case is where the input length is zero. You end up with a for loop, each iteration containing a recursive call (it is possible to maintain tail recursion here, but I'll leave that as an exercise for you, it's considerably less intuitive).

In very loose psuedocode:
Code:

[left]permute(input:set):set output:set = {} if input.length is zero, return output for value:char in input output.append(permute(input.copy.remove(value)) return output[/left]

There are better ways to do this that don't require the temporary 'output' structure and are truly tail recursive, but this is probably the easiest to 'get'.

Phew. Fun!

 

[seanohue]

Ok, thanks for all the info. I still cannot wrap my head around this. I wonder if there is some syntax that I have not learned yet to help speed this process up. I see all sort of other codes that do this with templates and stuff but I don't know how to interpret that into something I can get ideas off of. I'm even lost in that pseudocode error401 lol.

 

[error401]

It's definitely not the easiest computer science concept to grasp, especially if you start with and get yourself accustomed to procedural programming. It's a different way of thinking entirely. In traditional procedural programming you break up the task to be performed into a set of different procedures, and apply them sequentially to each data item you want to process. In recursive programming you instead break the data up into ever-smaller sets that all have the same properties and have the same identical process applied to them. It's a difficult thing to teach, you'd probably do well reading e.g. the Wiki article on recursion. I'm going to PM you an assignment I did way back in college that is a bit similar to this one and might help you out. Check your PMs.

I'm not sure that C++ is the worst language to start with. If you avoid C-isms like pointers, and the advanced stuff like templates for a while it's quite good. Much better than Java, which seems to be all the rage these days in education, and is IMO an awful language to start with. C++ is not fantastic for recursive, functional programming, but it's good enough to teach the basics. A course dedicated to this methodology would of course benefit from using a functional language like Scheme or another LISP variant.

 

[mcsamms]

The problem would be much easier once you have a bit more of a background in proofs and number theory. If you have ever proved something by induction it is more or less the same thing. Since you already know that the number of permutations is the number n multiplied by every int x where 1 <= x < n. If I remember correctly in Java how you would accomplish this is to write something along the lines of creating a class that returns a value n*n-1, and calls the class again, this time the function will start with the value n*n-1 which will be the new n and then compute n*n-2. The process repeats for all values greater then or equal to one. I don't know the C++ syntax anymore but I believe the procedure should be the same. But I believe that would be a correct pseudocode.

 

[scompton]

Quote:

Originally Posted by error401 /img/forum/go_quote.gif I'm not sure that C++ is the worst language to start with. If you avoid C-isms like pointers, and the advanced stuff like templates for a while it's quite good. Much better than Java, which seems to be all the rage these days in education, and is IMO an awful language to start with. C++ is not fantastic for recursive, functional programming, but it's good enough to teach the basics. A course dedicated to this methodology would of course benefit from using a functional language like Scheme or another LISP variant.

Why do you think Java is a bad language for teaching? It seems to me to be a fairly simple language with few of the gotchas that C++ has. I work with some people who started with C++ in college 5-10 years ago. Do you mean that beginning classes should be taught in a non-OO language like Pascal or Basic?

I doubt that the course that the OP is taking is dedicated to recursion. It's probably one project in a class.

In your factorial function, shouldn't the end condition be
Code:

[left]if (n == 1) return 1;[/left]

The way you've coded it, it will always return 0 (I think

).


I think your pseudocode is fine but since the OP didn't understand it let me try to summarize in English with one slight change

Code:

[left]The permute function takes a set as a parameter and returns a set create the output set as an empty set if the input set is empy, return the empty input set add the input set to the output set for each value in the input set create a new set containing all of the elements in the input set, except the current value recursively call permute passing the new set add the output from the recursive call return the output set[/left]

To the OP, recursion is not easy to understand, but in some situations it is the best way to solve a problem.

 

[joe]

As soon as I read the word recursion, I thought of this comic:

http://www.xkcd.com/c244.html

Good times.

 

[error401]

Quote:

Originally Posted by scompton /img/forum/go_quote.gif Why do you think Java is a bad language for teaching? It seems to me to be a fairly simple language with few of the gotchas that C++ has. I work with some people who started with C++ in college 5-10 years ago. Do you mean that beginning classes should be taught in a non-OO language like Pascal or Basic?

Java's standard library is heavily over-engineered in my opinion. Just performing simple tasks like reading from STDIN requires the instantiation of several objects, accessing class-scoped static variables and other things. Even doing some very basic things in Java requires instantiating complex container objects and other similar tasks that can't be properly explained until a more advanced course in data structures or specifically OO. Not only that, its strict adherence to OO methods forces the student to take on the entirety of OO design (including generics, the pitfalls of using references, object instantiation, more complex scoping etc. etc. etc.) when they should be learning the basics about loops, how the stack works and the like. Because of the complex standard library, it forces the instructor to gloss over extremely important concepts in the interest of keeping things as simple as possible for the student. For example, when I took an introductory class in Java the instructor didn't even explain what all the keywords in the classic 'public static void main(String[] args)', despite many students asking (citing that it would confuse many) until more than halfway through the course. Those with existing experience in any language were asking questions the instructor didn't want to answer so he didn't confuse the rest of the class, and both sets of students end up out of the loop. I had prior experience in OO and didn't have a problem with this, but most students were very confused by all the hoops they had to jump through. Further, Java has its own pitfalls that I don't think are any easier to resolve than those in C++ - and IME are much more likely to be runtime errors rather than compile time errors. I also extremely dislike that it even has types that aren't objects, and all the workarounds required to deal with them. It's supposed to be a strict OO language and yet it has variables that aren't objects?! I know they did this for performance reasons, but it's still a huge pain in the ass. This is a bit better in Java 1.5 with autoboxing, but then you run into other invisible issues... It's not fun for me, and I know what I'm doing, I'd hate to be a student writing my first program running into these kinds of things...

Personally, I think a language like Python is ideal for teaching. You can start with a 'script' having no functions or methods at all, it supports basically any programming methodolgy but does not force you to use any, and therefore it can grow with what the student knows. The biggest downfall of this is how loose the language lets you be, it may not force you to be 'good' enough, leading to sloppy programmers. Really this is the instructors job though and not the fault of the language, IMO.

Quote:

Originally Posted by scompton /img/forum/go_quote.gif In your factorial function, shouldn't the end condition be Code: [left]if (n == 1) return 1;[/left] The way you've coded it, it will always return 0 (I think ).

Absolutely right. I originally was going to write it using both end cases but I changed my mind in the interest of simplicity. Of course, I deleted the wrong conditional. Ooops. Sorry, OP.

 

[seanohue]

I was just telling error401 that I had a sudden insight right at the end of my C++ class today. I was flipping through my book (Cay Horstman's C++ Essentials) and found 2 functions in the vector's section called insert and erase, which were exactly what I was trying to figure out how to do since I can do this same type of thing but with strings (a string is a vector, but my teacher said we could NOT use strings since Horstman had already coded that in the book

). I haven't written it out or compiled it yet, but I have a damn good idea how to make this work now.

My school (highschool) does C++ as a prereq for Java, which is the AP Computer Science courses. I was lazy in the beginning of the year and should have taken C++ in my sophomore year so I could be taking AP CS AB this year (my senior year). Although, my major in college (going to Rose-Hulman) is EE and from what I gather, C++ is the primary language used in that field. Anywho, thanks for the help and I'll let you guys know what happends when I try and compile this tomorrow.

 

[eitook]

i still get the shudders everytime i look at programming code. Brings me back to my undergrad days of plagiarising code

 

[laxx]

Quote:

Originally Posted by scompton /img/forum/go_quote.gif In your factorial function, shouldn't the end condition be Code: [left]if (n == 1) return 1;[/left] The way you've coded it, it will always return 0 (I think ).

That's the first thing I realized and was about to comment on it, lol.

I have to agree with error401 on JAVA not being a good beginner language. You definitely glance over alot of important concepts. I know first hand since I started with JAVA. But taking a few electives really helped out in understanding (Wait, did it really help? Those classes were hard. =T)

Recursion was one of the tougher concepts to grasp, but once you get it, it's lovely. =]

 

[Arainach]

Post being revised because I'm insane

 

[scompton]

Good points error401 and laxx. I guess it shows my age. My college started us in Fortran, then Assembler, then a multi language course that included Pascal, Lisp, SNOBOL, and APL. After that everything was in Pascal. The first project in the first class, they gave us a 10 line program that we had to type onto punch cards. The college had a micro computer lab that you had to be a senior to get access to.

My high school didn't even have their records computerized. Everything was paper files.