Permutations

Discussion in 'Java' started by gaijinco, Sep 27, 2006.

  1. gaijinco

    gaijinco Guest

    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!
     
    gaijinco, Sep 27, 2006
    #1
    1. Advertising

  2. gaijinco

    Oliver Wong Guest

    "gaijinco" <> wrote in message
    news:...
    > 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
     
    Oliver Wong, Sep 27, 2006
    #2
    1. Advertising

  3. gaijinco

    gaijinco Guest

    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!
     
    gaijinco, Sep 27, 2006
    #3
  4. opalinski from opalpaweb, Sep 27, 2006
    #4
  5. -----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+7xMGD3itQRAgLlAJ9W6mdmNc7OhKvITJoDGRKy449uXgCfZHud
    zQfuWToatlVcHvwf6e+wHUM=
    =J9R1
    -----END PGP SIGNATURE-----
     
    Hendrik Maryns, Sep 27, 2006
    #5
  6. gaijinco

    Daniel Dyer Guest

    On Wed, 27 Sep 2006 15:03:01 +0100, gaijinco <> 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/org/uncommons/maths/PermutationGenerator.html

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

    Dan.

    --
    Daniel Dyer
    http://www.dandyer.co.uk
     
    Daniel Dyer, Sep 27, 2006
    #6
  7. gaijinco

    Eric Sosman Guest

    Daniel Dyer wrote:

    > On Wed, 27 Sep 2006 15:03:01 +0100, gaijinco <> 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
    lid
     
    Eric Sosman, Sep 28, 2006
    #7
  8. gaijinco

    Daniel Dyer Guest

    On Thu, 28 Sep 2006 03:04:23 +0100, Eric Sosman
    <> wrote:

    > Daniel Dyer wrote:
    >
    >> On Wed, 27 Sep 2006 15:03:01 +0100, gaijinco <> 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
     
    Daniel Dyer, Sep 28, 2006
    #8
  9. Thomas Weidenfeller, Sep 28, 2006
    #9
  10. 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
     
    Patricia Shanahan, Sep 28, 2006
    #10
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Karsten Wutzke

    Permutations of instances in array

    Karsten Wutzke, Mar 2, 2004, in forum: Java
    Replies:
    5
    Views:
    17,784
    Chris Lamprecht
    Mar 4, 2004
  2. Hendrik Maryns
    Replies:
    0
    Views:
    350
    Hendrik Maryns
    Mar 3, 2006
  3. Roger
    Replies:
    1
    Views:
    433
    Martin Magnusson
    Sep 24, 2003
  4. Ed Neukirch

    Permutations

    Ed Neukirch, Dec 24, 2003, in forum: C++
    Replies:
    7
    Views:
    631
    Mike Hewson
    Dec 27, 2003
  5. Daniel Fortin
    Replies:
    3
    Views:
    379
    Frank Schmitt
    Feb 18, 2004
Loading...

Share This Page