This week's book giveaway is in the Servlets forum. We're giving away four copies of Murach's Java Servlets and JSP and have Joel Murach on-line! See this thread for details.

Is there any standard math library to find permutations? The apache commons math does not find all the permutations. I would like to use some kind of a library that finds all 6P4 permutations.

It's fairly easy to find the number of permutations. Generating the actual permutations is more tricky. It sounds like Marc may be talking about the former, while Rajesh is talking about the latter.

[Rajesh]: The apache commons math does not find all the permutations.

Are you referring to nextPermutation() in org.apache.commons.math.random.RandomData and RandomDataImpl? That's not intended to generate all permutations - it's just intended to generate a single random permutation. Subsequent calls to the method may repeat previous permutations, or not. There's no requirement in the API to avoid repetition and thereby eventually generate all permutations.

I don't know of any standard library to do what you're asking. I do know that Knuth wrote about the problem at some length. That's not to say you need to read all that to get a solution - I'm sure he was considering a number of related problems, and discussing different algorithms, evaluating them for different properties like performance or requiring the least number of changes from one permutation to the next. Since you're posting in Beginner, I think you should probably try this book only if you're new to Java but not new to programming in general.

Here is a page with several algorithms for doing this using C. And here is a page with applets to do this in Java. I haven't carefully evaluated the content of either, but maybe that can get you started.

I did this myself some years ago - I wanted to generate all permutations in order, meaning like this

1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1

As I recall I made a recursive method to choose each element in turn, by picking the highest available (not-yet-used) value to populate the current position. I think I used a Set of some sort - probably a TreeSet or LinkedHashSet - to keep track of which values were still available, and which were already used. I'm sure there are better implementations out there, whether you want your elements in order, or you just want the fastest algorithm (e.g. Heap's algorithm).

It would be nice if there were a reasonably well-known library that implemented this sort of thing. Please let us know if you do find one.

Originally posted by Mike Simmons: It's fairly easy to find the number of permutations. Generating the actual permutations is more tricky. It sounds like Marc may be talking about the former, while Rajesh is talking about the latter...

You may already be aware that the Wikipedia article on Permutation has a relatively straightforward implementation of a permutation generating algorithm. It needs to be tweaked a little to work in Java because the algorithm assumes 1-based arrays (the article fails to explicitly mention that).

Some problems are so complex that you have to be highly intelligent and well informed just to be undecided about them. - Laurence J. Peter