Velocity Reviews (http://www.velocityreviews.com/forums/index.php)
-   Java (http://www.velocityreviews.com/forums/f30-java.html)
-   -   Permutations (http://www.velocityreviews.com/forums/t373009-permutations.html)

 gaijinco 09-27-2006 02:03 PM

Permutations

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 09-27-2006 02:27 PM

Re: Permutations

"gaijinco" <gaijinco@gmail.com> wrote in message
> 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

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

 gaijinco 09-27-2006 02:50 PM

Re: Permutations

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@gmail.com opalinski from opalpaweb 09-27-2006 03:15 PM

Re: Permutations

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

All the best,
Opalinski
opalpa@gmail.com
http://www.geocities.com/opalpaweb/

 Hendrik Maryns 09-27-2006 03:40 PM

Re: Permutations

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

 Daniel Dyer 09-27-2006 03:46 PM

Re: Permutations

On Wed, 27 Sep 2006 15:03:01 +0100, gaijinco <gaijinco@gmail.com> 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

 Eric Sosman 09-28-2006 02:04 AM

Re: Permutations

Daniel Dyer wrote:

> On Wed, 27 Sep 2006 15:03:01 +0100, gaijinco <gaijinco@gmail.com> 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.

--
Eric Sosman
esosman@acm-dot-org.invalid

 Daniel Dyer 09-28-2006 09:13 AM

Re: Permutations

On Thu, 28 Sep 2006 03:04:23 +0100, Eric Sosman
<esosman@acm-dot-org.invalid> wrote:

> Daniel Dyer wrote:
>
>> On Wed, 27 Sep 2006 15:03:01 +0100, gaijinco <gaijinco@gmail.com> 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

 Thomas Weidenfeller 09-28-2006 09:29 AM

Re: Permutations

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/

 Patricia Shanahan 09-28-2006 02:08 PM

Re: Permutations

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

 All times are GMT. The time now is 01:11 AM.