aspose file tools*
The moose likes Beginning Java and the fly likes Permutations Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Java » Beginning Java
Bookmark "Permutations" Watch "Permutations" New topic
Author

Permutations

Mike Stach
Greenhorn

Joined: Oct 26, 2008
Posts: 8
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.
marc weber
Sheriff

Joined: Aug 31, 2004
Posts: 11343

There's probably such a library out there, but it's a fairly easy method to write yourself, assuming you know the formula. See Ask Dr. Math - Permutations and Combinations.


"We're kind of on the level of crossword puzzle writers... And no one ever goes to them and gives them an award." ~Joe Strummer
sscce.org
Mike Simmons
Ranch Hand

Joined: Mar 05, 2008
Posts: 3018
    
  10
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.
marc weber
Sheriff

Joined: Aug 31, 2004
Posts: 11343

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're right. That didn't even occur to me.
Garrett Rowe
Ranch Hand

Joined: Jan 17, 2006
Posts: 1296
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
 
Don't get me started about those stupid light bulbs.
 
subject: Permutations