Google c++ class question

[Tarek Firzli]

So one of the examples on the google c++ course is this:

How many ways can you arrange 6 different books, left to right, on a shelf?
This time we will just give you the solution and let you write the program: 720.

Heres the link: http://code.google.com/edu/languages/cpp/basics/getting-started.html

So after thinking for a bit I started writing a it, and it took a good 15 minutes before it was all tweaked, but here is the code I came up with. I know it is right because it spits out the right answer, and it makes perfect sense. What I was wondering was if there is an easier way anyone sees?

Some background, this is my second day writing in c++, the first was on labor day when I started to learn it, so im very new. I have written 15ish programs, some easy, some which i am somewhat impressed with.

heres my code:

#include <iostream>
using namespace std;

int main() {
int a, b,c,d,e,f,n;



for (a=0;a<=5;a++){

for (b=0;b<=5;b++)
if (b!=a)

for(c=0;c<=5;c++)
if (c!=b && c!=a)

for(d=0;d<=5;d++)
if (d!=c && d!=b && d!=a)

for(e=0;e<=5;e++)
if(e!=d && e!=c && e!=b && e!=a)

for(f=0;f<=5;f++)
if(f!=e && f!=d && f!=c && f!=b && f!=a) n++;

}
cout<<n<<endl;

return 0;
}

[Zhuge]

http://en.wikipedia.org/wiki/Permutation
Just take the factorial of the number of books you have.
6! = 720

[webJose]

Yes, there is a simpler way (although not necessarily a more efficient one): Recursion. These types of problems have an act for recursion: You have N elements (books) and you need to find out all possible ways of sorting them out, left to right. A recursive algorithm would take the first book out of the collection and call itself with the collection of books minus the one it took. Recursively, it would do that until the collection of books contains just one book (the last book). At this point it returns the one book (giving one sort), which is paired with the second-to-last book to the left and the right (giving 2 sorts); the sort combinations start to pile up until you return to the original call that compiles all of the combinations.

But of course, that method is just the mechanic one. We are talking permutations here and all you have to do is calculate a simple formula which you can google it out; there's one for permutations -where the order of the elements matter like in this example- and another one similar for combinations -where the order of the elements doesn't matter, therefore reducing the number of possibilities-.

[Tarek Firzli]

I think the point was to find a way to work through the data one by one using a program

The intro to the problems said "One of the powers of computing is being able to do a brute-force search for a solution to a problem. Trial and error works just fine for some problems. In fact, computers can be especially good at such problems."

[Cuddlebuddie928]

A simple, non-recursive method:

#include <iostream>
using std::cout;
using std::cin; //last two instead of using namespace std (if you like)

int main()
{
	int factorial; //number to be factored

	cout << "Enter a number to get its factorial: ";
	cin >> factorial;

	if(factorial < 0) return 1; //detects error (cannot factor <0)
	else if(factorial==0 || factorial==1) factorial=1; //the factorial 0 or 1 is 1... no other calculation needed
	else {
		for( int index=factorial-1; index > 1; index--) factorial*=index;
		/*essentially for your example:
		factorial starts at 6, and index is set to 5 (which is factorial-1)... they're multiplied to get 30
		30 is multiplied by index again, which is now 4, for 120.
		then that is multiplied by 3 and so on until index=1...*/
	}

	cout << factorial;
	return 0;
}

[Tarek Firzli]

Thanks! This is definitely easier, hah.