Customer Reviews

The Art of Computer Programming, Volume 4, Fascicle 2: Generating All Tuples and Permutations

5 star:		(6)
4 star:		(0)
3 star:		(0)
2 star:		(0)
1 star:		(0)

 

 

First, I would like to say this is the first Donald Knuth book I have read, only because every programmer respects TAOCP so much that they say it is too hard for the hobby programmer. I have a small background in Computer Science, and some mid-level Math; yet Knuth walks you through some of the most exciting Computer Science problems you could ever dream of with ease! I came to find this book perfect, mostly because my favorite Programming problem is the Traveling Salesman, this book as well as fasicles 3 and 4, are the perfect reference to find great ways to venture into the unsolved TSP Algorithm, and the feared Hamilitonian Cycle.

Reading about gray generation I immediatly found so much more value to this book than I ever expected. As well, the book then jumps into ways to use loopless generation( which blew my mind! ). Then the best part comes in the second half of the book, "Generating All Permutations" First it starts with a brute force method for achieving all permutations, then Algorithm L to G(my favorite algorithm in the book...) is the largest hurtle in the book; I actually bought the whole TAoCP volumes so I could get through this part because it goes over permutation pre-multiplication ( Knuth has a better way of defining this ), although the idea is simple, an effective way to implement and explore pre-multiplication I found to be extremely important and should not be over looked. Then after that the diffictulty goes to equal as the first half.

In summary this book is deffinitly worth the wait, and it helps a person, no matter how experienced, to explore new ways to venture out of the straight and narrow, and into an arena of problems that few dare to venture.

This preliminary excerpt from Knuth's Volume 4 will please all the fans of his seminal first three volumes. The didactic style is the same. So too is the very distinctive Tex typeface. (You know that he invented Tex, don't you?)

Of course, there are the problem sets. This little book has two sections. In each are 112 problems. Strewth! Knuth thoughtfully gives an estimate next to each of how long it will take you to solve it. Those estimates probably refer to someone of his calibre. I've attempted most of the problems in his earlier volumes and could typically only get within a factor of two of the time estimate. And this was only when I could actually solve a problem.

The book addresses a gap in the literature of computer science. Research papers in journals or books of conference proceedings do not usually present you with problems. While introductory texts do, but those are simple. Very difficult to find a solid compendium of challenging problems.

Such is the attraction of this book to me and perhaps to you. The potential readership is exclusive and self selecting. The only drawback is the wait for the rest of Volume 4.

Combinatorial problems arise in a wide range of contexts. Among combinatorial problems, generation of all distinct sets of some size (tuples) or all rearrangements of the objects (permutations) occur commonly, often as the first step in a larger calculation. Knuth addresses some important classes of such problems in this book.

Even "all possible permutations" leaves a wide range of choices open. For example, should the list be in alphabetical order? Should it minimize the number of differences between consecutive elements? Many other constraints can be imposed as well, even esthetic ones! "Ringing the changes" on a carillon is one such combinatorial problem, with a long history and criteria for beauty all its own. However choices are made, the next step is to specify a way of creating the list. This can have constraints of its own. For example, it may be neccesary to create the next arrangement in the sequence knowing only the current element of the sequence. Knuth offers different algorithms for meeting different sets of constraints. If none of them match your needs, then the references will help you find something that does, or the discussion and exercises will help you develop one of your own.

Although useful, this book is very brief. 144 pages isn't a lot. Take away 45 pages just for solutions to exercises, then more for index and exercises, and the text is surprisingly brief. What's left carries its weight, though. It's a valuable addition to almost programmer's library.

-- wiredweird

Am studying Gray codes for a graduate paper. This was an excellent resource. Fun and interesting read.

Three classic volumes from Donald Knuth. I have the 3rd edition. Once your get pass understanding MIX ( MMIX, 4th edition), it is a great technical read. Bring so much to Computer Science. I used them in school. I use them today.

The Art of Computer Programming is a classic from Professor Knuth.

Volume 2 carries on where Vol. 1 left off.

this is required CS reading and should be required for every programmer.