Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > Java > Permutations

Reply
Thread Tools

Permutations

 
 
gaijinco
Guest
Posts: n/a
 
      09-27-2006
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!

 
Reply With Quote
 
 
 
 
Oliver Wong
Guest
Posts: n/a
 
      09-27-2006
"gaijinco" <(E-Mail Removed)> wrote in message
news:(E-Mail Removed) ups.com...
> 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.

Rotation: java.util.Collections.rotate(List<?> list, int distance)

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

 
Reply With Quote
 
 
 
 
gaijinco
Guest
Posts: n/a
 
      09-27-2006
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!

 
Reply With Quote
 
opalpa@gmail.com opalinski from opalpaweb
Guest
Posts: n/a
 
      09-27-2006


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


http://groups.google.com/group/comp....e02aee66641431

All the best,
Opalinski
http://www.velocityreviews.com/forums/(E-Mail Removed)
http://www.geocities.com/opalpaweb/

 
Reply With Quote
 
Hendrik Maryns
Guest
Posts: n/a
 
      09-27-2006
-----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 :-p

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+7xMGD3itQRAgLlAJ9W6mdmNc7OhKvITJoDGR Ky449uXgCfZHud
zQfuWToatlVcHvwf6e+wHUM=
=J9R1
-----END PGP SIGNATURE-----
 
Reply With Quote
 
Daniel Dyer
Guest
Posts: n/a
 
      09-27-2006
On Wed, 27 Sep 2006 15:03:01 +0100, gaijinco <(E-Mail Removed)> wrote:

> 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/...Generator.html

(Source:
https://watchmaker.dev.java.net/sour...viewcvs-markup)

Dan.

--
Daniel Dyer
http://www.dandyer.co.uk
 
Reply With Quote
 
Eric Sosman
Guest
Posts: n/a
 
      09-28-2006
Daniel Dyer wrote:

> On Wed, 27 Sep 2006 15:03:01 +0100, gaijinco <(E-Mail Removed)> wrote:
>
>> 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:


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?

--
Eric Sosman
(E-Mail Removed)lid
 
Reply With Quote
 
Daniel Dyer
Guest
Posts: n/a
 
      09-28-2006
On Thu, 28 Sep 2006 03:04:23 +0100, Eric Sosman
<(E-Mail Removed)> wrote:

> Daniel Dyer wrote:
>
>> On Wed, 27 Sep 2006 15:03:01 +0100, gaijinco <(E-Mail Removed)> wrote:
>>
>>> 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:

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

--
Daniel Dyer
http://www.dandyer.co.uk
 
Reply With Quote
 
Thomas Weidenfeller
Guest
Posts: n/a
 
      09-28-2006
gaijinco wrote:
> 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
--
The comp.lang.java.gui FAQ:
http://gd.tuwien.ac.at/faqs/faqs-hie...lang.java.gui/
ftp://ftp.cs.uu.nl/pub/NEWS.ANSWERS/...g/java/gui/faq
 
Reply With Quote
 
Patricia Shanahan
Guest
Posts: n/a
 
      09-28-2006
Thomas Weidenfeller wrote:
> gaijinco wrote:
>> 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?


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
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
[Slightly OT] Which algorithm for permutations Hendrik Maryns Java 0 03-03-2006 02:10 PM
Permutations of instances in array Karsten Wutzke Java 5 03-04-2004 04:49 AM
Finding permutations of a list in a map or multimap Daniel Fortin C++ 3 02-18-2004 09:51 AM
Permutations Ed Neukirch C++ 7 12-27-2003 12:44 AM
Permutations with repatitions in c++ Roger C++ 1 09-24-2003 10:52 PM



Advertisments