• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Paul Clapham
  • Ron McLeod
  • Jeanne Boyarsky
  • Tim Cooke
Sheriffs:
  • Liutauras Vilda
  • paul wheaton
  • Henry Wong
Saloon Keepers:
  • Tim Moores
  • Tim Holloway
  • Stephan van Hulst
  • Carey Brown
  • Frits Walraven
Bartenders:
  • Piet Souris
  • Himai Minh

Permutations

 
Greenhorn
Posts: 8
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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.
 
Sheriff
Posts: 11343
Mac Safari Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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.
 
Master Rancher
Posts: 4189
57
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Posts: 11343
Mac Safari Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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.
 
Ranch Hand
Posts: 1296
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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).
 
I need a new interior decorator. This tiny ad just painted every room in my house purple.
Free, earth friendly heat - from the CodeRanch trailboss
https://www.kickstarter.com/projects/paulwheaton/free-heat
reply
    Bookmark Topic Watch Topic
  • New Topic