Permutations

[gaijinco]

Is there any static methods in Java to do permutations and rotations?

Also, is there an easier way to sort a String than to do this:

String unsorted = "UnsortedString";
char[] u = unsorted.toCharArray();
Arrays.sort(u);
String sorted = new String(u);

Thanks a lot!

 

[Oliver Wong]

Is there any static methods in Java to do permutations and rotations?

Permutation: Not from Sun, as far as I know, but you could provide find
some free downloadable libraries to provide this functionality.

Also, is there an easier way to sort a String than to do this:

String unsorted = "UnsortedString";
char[] u = unsorted.toCharArray();
Arrays.sort(u);
String sorted = new String(u);

Not that I can think of.

- Oliver

 

[gaijinco]

Thanks Olvier!

Isn't it weird that there is a shuffle() method but not a
next_permutation() one? It is more weird if you take account that the
STL provides one!

 

[opalpa]

Permutation: Not from Sun, as far as I know, but you could provide find
some free downloadable libraries to provide this functionality.

http://groups.google.com/group/comp.lang.java.programmer/msg/2be02aee66641431

All the best,
Opalinski
(e-mail address removed)
http://www.geocities.com/opalpaweb/

 

[Hendrik Maryns]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

gaijinco schreef:

Thanks Olvier!

Isn't it weird that there is a shuffle() method but not a
next_permutation() one? It is more weird if you take account that the
STL provides one!

Have a look here: http://mindprod.com/jgloss/permutation.html, you’ll
find some code from me there

You can also get a jar from my homepage with the permutation package in
it, see below and look for combinatorics.

H.
- --
Hendrik Maryns
http://tcl.sfs.uni-tuebingen.de/~hendrik/
==================
http://aouw.org
Ask smart questions, get good answers:
http://www.catb.org/~esr/faqs/smart-questions.html
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.2 (GNU/Linux)

iD8DBQFFGptae+7xMGD3itQRAgLlAJ9W6mdmNc7OhKvITJoDGRKy449uXgCfZHud
zQfuWToatlVcHvwf6e+wHUM=
=J9R1
-----END PGP SIGNATURE-----

 

[Daniel Dyer]

Is there any static methods in Java to do permutations and rotations?

http://www.merriampark.com/perm.htm

I have modified this (optimised for permutations of length 20 or less) for
my own project to provide what I feel is a more useful API:

https://watchmaker.dev.java.net/api/org/uncommons/maths/PermutationGenerator.html

(Source:
https://watchmaker.dev.java.net/sou...iew=auto&content-type=text/vnd.viewcvs-markup)

Dan.

 

[Eric Sosman]

http://www.merriampark.com/perm.htm

I have modified this (optimised for permutations of length 20 or less)
for my own project to provide what I feel is a more useful API:

I find it hard to believe that "optimization" has any useful
meaning when you're running through all the permutations of twenty
items.

Do the math: If you use one nanosecond to generate and process
each permutation, your program needs seventy-seven years to finish.
What are the chances you will still care about the answer?

 

[Daniel Dyer]

I find it hard to believe that "optimization" has any useful
meaning when you're running through all the permutations of twenty
items.

Do the math: If you use one nanosecond to generate and process
each permutation, your program needs seventy-seven years to finish.
What are the chances you will still care about the answer?

That's precisely the point - it's optimised for small sets. 20 just
happens to be the limit imposed by using longs for arithmetic (instead of
BigInteger), the motiviation though was to improve performance when
dealing with sets smaller than that (mostly I've only used permutations of
length 7 or less). Perhaps I'm guilty of premature optimisation but, for
exactly the reason you state, I could not envisage needing to use lengths
greater than 20 so I didn't see a need for the overhead of object
arithmetic.

Perhaps I should have used "restricted" instead of "optimised" since the
point was to draw attention to a restriction in my version that is not
present in the original.

Dan.

 

[Thomas Weidenfeller]

Thanks Olvier!

Isn't it weird that there is a shuffle() method but not a
next_permutation() one?

I am more surprised that there is a shuffle() method. Only few people in
the world need it, so why clutter the standard edition with it?

/Thomas

 

[Patricia Shanahan]

I am more surprised that there is a shuffle() method. Only few people in
the world need it, so why clutter the standard edition with it?

How many people want to write a card game? It can be used to shuffle
card decks.

I use it when I want to make a random choice of K elements from N,
without replacement. Of course, I could write my own truncated version
of the algorithm, but so far it has not been a performance problem, and
it is very simple.

I think it was worth doing partly because it is high leverage. Shuffling
by swapping elements is something that a lot of people get wrong. On the
other hand, if you know what you are doing it is a short, simple algorithm.

Patricia