# Permutations

Mike Stach

Greenhorn

Posts: 8

posted 8 years ago

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

Posts: 3090

14

posted 8 years ago

It's fairly easy to find the

Are you referring to nextPermutation() in org.apache.commons.math.random.RandomData and RandomDataImpl? That's not

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

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.

*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.

posted 8 years ago

You're right. That didn't even occur to me.

Originally posted by Mike Simmons:

It's fairly easy to find thenumberof 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.

*~Joe Strummer*

sscce.org

Garrett Rowe

Ranch Hand

Posts: 1296

posted 8 years ago

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