Results 1 to 19 of 19
  1. #1
    dojob is offline Member
    Join Date
    Jul 2013
    Posts
    52
    Rep Power
    0

    Default Random shuffling

    In many applications, you need to randomly reorder the elements in an array. This is called a shuffling. To accomplish this, for each element myList[i], randomly generate an index j and swap myList[i] with myList[j], as follows:

    Java Code:
    for(int i = 0; i < myList.length; i++){
       int index = (int)(Math.random() * myList.length);
      
       double temp = myList[i];
       myList[i] = myList[index];
       myList[index] = temp;
    }
    Above is the sample i extracted from book. From the code, isn't that index is repeatable? Since it is repeated, eg: 2, 2, then we will have myList[0] = myList[2], myList[1] = myList[2] and it will not reshuffle the order of elements as some of the new index is not there.(When we have 2 same values for index, some of the values(ranging from 0 to myList.length) will be missing. In other words, index is not unique.

    Is there anything wrong with the code or it just my mistake?

  2. #2
    Di Immortalis is offline Member
    Join Date
    Jul 2013
    Posts
    5
    Rep Power
    0

    Default Re: Random shuffling

    Your index will not be unique because A) Your giving it a finite length in the form of an integer, so there are only a small numbers that it is allowed to produce B) You are remaking it every time the loop restarts. It will never be unique because it doesn't know what its previous value were.
    I get that it needs to have a small range, so you should consider initializing an array outside of the loop, then adding whatever values index produces to it, then checking those values against new indexes. Also, if its randomly shuffling, you don't really want unique. As long as index != i, you should get a random shuffling.
    Last edited by Di Immortalis; 07-24-2013 at 05:56 PM.

  3. #3
    dojob is offline Member
    Join Date
    Jul 2013
    Posts
    52
    Rep Power
    0

    Default Re: Random shuffling

    Quote Originally Posted by Di Immortalis View Post
    Your index will not be unique because A) Your giving it a finite length in the form of an integer, so there are only a small numbers that it is allowed to produce B) You are remaking it every time the loop restarts. It will never be unique because it doesn't know what its previous value were.
    I get that it needs to have a small range, so you should consider initializing an array outside of the loop, then adding whatever values index produces to it, then checking those values against new indexes. Also, if its randomly shuffling, you don't really want unique. As long as index != i, you should get a random shuffling.
    Thanks. I have understand the code. It is to swap between two values.

  4. #4
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,310
    Blog Entries
    7
    Rep Power
    20

    Default Re: Random shuffling

    Google for "Knuth shuffle" or "Fisher Yates shuffle" for a good random shuffle algorithm.

    kind regards,

    Jos
    cenosillicaphobia: the fear for an empty beer glass

  5. #5
    dojob is offline Member
    Join Date
    Jul 2013
    Posts
    52
    Rep Power
    0

    Default Re: Random shuffling

    Thanks for the information.

  6. #6
    jim829 is offline Senior Member
    Join Date
    Jan 2013
    Location
    United States
    Posts
    3,340
    Rep Power
    5

    Default Re: Random shuffling

    Keep in mind what you want to use the shuffle for. It seems the modern Fisher-Yates algorithm ensures that no card ends up in its original position, where as the original Fisher-Yates does allow that. So the modern version might be suitable for randomizing the alphabet for cryptogram applications and the latter for card games. Or you could just use the modern version and randomize once for cryptograms and more than once for card games.

    Regards,
    Jim
    The Java™ Tutorial | SSCCE | Java Naming Conventions
    Poor planning our your part does not constitute an emergency on my part.

  7. #7
    dojob is offline Member
    Join Date
    Jul 2013
    Posts
    52
    Rep Power
    0

    Default Re: Random shuffling

    Quote Originally Posted by jim829 View Post
    Keep in mind what you want to use the shuffle for. It seems the modern Fisher-Yates algorithm ensures that no card ends up in its original position, where as the original Fisher-Yates does allow that. So the modern version might be suitable for randomizing the alphabet for cryptogram applications and the latter for card games. Or you could just use the modern version and randomize once for cryptograms and more than once for card games.

    Regards,
    Jim
    I try to modify the code to modern fisher-yate algorithm as follow but it still able to generate arrays ends up in its original position.
    Is there any problem in my code?

    Modern fisher-yates algorithm:
    To shuffle an array a of n elements (indices 0..n-1):
    for i from n − 1 downto 1 do
    j ← random integer with 0 ≤ j ≤ i
    exchange a[j] and a[i]
    Java Code:
      public static void main(String[] args) {
           int [] myList = {1,2};
            for(int i = myList.length - 1; i > 0; i--){
                int index = (int)(Math.random() * myList.length);
       
                int temp = myList[i];
                myList[i] = myList[index];
                myList[index] = temp;
            }
            
            for(int i = 0; i < myList.length; i++)
                System.out.println(myList[i]);    
        }

  8. #8
    jim829 is offline Senior Member
    Join Date
    Jan 2013
    Location
    United States
    Posts
    3,340
    Rep Power
    5

    Default Re: Random shuffling

    It took me a moment to find the error.

    Java Code:
    int index = (int)(Math.random() * myList.length);
    You should be multiplying by i, not myList.length.
    0 <= index <= i, not 0 <=index <= myList.length

    Regards,
    Jim
    The Java™ Tutorial | SSCCE | Java Naming Conventions
    Poor planning our your part does not constitute an emergency on my part.

  9. #9
    dojob is offline Member
    Join Date
    Jul 2013
    Posts
    52
    Rep Power
    0

    Default Re: Random shuffling

    Quote Originally Posted by jim829 View Post
    It took me a moment to find the error.

    Java Code:
    int index = (int)(Math.random() * myList.length);
    You should be multiplying by i, not myList.length.
    0 <= index <= i, not 0 <=index <= myList.length

    Regards,
    Jim
    I see. But I have few questions on this. How does replacing myList.length with i make the arrays not to shuffle back to the original arrangement.

    Second question is,
    if i replaced
    Java Code:
    for(int i = myList.length - 1; i > 0; i--)
    with
    Java Code:
    for(int i = 0; i < myList.length; i++)
    the arrays will also never shuffle back to the original arrangement. Why is it so?

  10. #10
    jim829 is offline Senior Member
    Join Date
    Jan 2013
    Location
    United States
    Posts
    3,340
    Rep Power
    5

    Default Re: Random shuffling

    I have not analyzed the algorithms so I can't answer that. But why not go thru the algorithm on paper with a small list size and see if you can figure it out?

    Regards,
    Jim
    The Java™ Tutorial | SSCCE | Java Naming Conventions
    Poor planning our your part does not constitute an emergency on my part.

  11. #11
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,310
    Blog Entries
    7
    Rep Power
    20

    Default Re: Random shuffling

    Quote Originally Posted by jim829 View Post
    Keep in mind what you want to use the shuffle for. It seems the modern Fisher-Yates algorithm ensures that no card ends up in its original position, where as the original Fisher-Yates does allow that. So the modern version might be suitable for randomizing the alphabet for cryptogram applications and the latter for card games. Or you could just use the modern version and randomize once for cryptograms and more than once for card games.

    Regards,
    Jim
    I don't think leaving none of the entries (cards, numbers etc) at its original place is a good randomizer, e.g. for the sequence { a, b } the outcome will always be { b, a } and for { a, b, c } the outcome is limited to { b, c, a } and {c, a, b }

    kind regards,

    Jos
    cenosillicaphobia: the fear for an empty beer glass

  12. #12
    jim829 is offline Senior Member
    Join Date
    Jan 2013
    Location
    United States
    Posts
    3,340
    Rep Power
    5

    Default Re: Random shuffling

    From a theoretical perspective I agree. I was just pointing out that good or bad, one that leaves no elements in its original position has some uses. But any one of the possible permutations of a set should be allowed, hopefully with equal or near equal probability.

    On a different note, I am glad you mentioned the names of the algorithms. I knew how to "shuffle cards" in software but I didn't know the algorithms had a name. It was an interesting read.

    Regards,
    Jim
    The Java™ Tutorial | SSCCE | Java Naming Conventions
    Poor planning our your part does not constitute an emergency on my part.

  13. #13
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,310
    Blog Entries
    7
    Rep Power
    20

    Default Re: Random shuffling

    Quote Originally Posted by jim829 View Post
    From a theoretical perspective I agree. I was just pointing out that good or bad, one that leaves no elements in its original position has some uses. But any one of the possible permutations of a set should be allowed, hopefully with equal or near equal probability.

    On a different note, I am glad you mentioned the names of the algorithms. I knew how to "shuffle cards" in software but I didn't know the algorithms had a name. It was an interesting read.
    Try to find 'Sorting and Searching' (volume III of 'The Art Of Computer Programming' by Donald Knuth; it's a bible but almost nobody knows about it anymore so they re-invent the wheel (or worse), It has an excellent explanation of this method (with a rigourous mathematical proof and all); b.t.w. I still think that leaving none of the elements in place is a terrible shuffler (see the examples above).

    kind regards,

    Jos
    cenosillicaphobia: the fear for an empty beer glass

  14. #14
    jim829 is offline Senior Member
    Join Date
    Jan 2013
    Location
    United States
    Posts
    3,340
    Rep Power
    5

    Default Re: Random shuffling

    Embarassingly, I have volumes 1-3 of his books (and an extra copy of volume 1). Time to brush up on MIX. :)

    Regards,
    Jim
    The Java™ Tutorial | SSCCE | Java Naming Conventions
    Poor planning our your part does not constitute an emergency on my part.

  15. #15
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,310
    Blog Entries
    7
    Rep Power
    20

    Default Re: Random shuffling

    Quote Originally Posted by jim829 View Post
    Embarassingly, I have volumes 1-3 of his books (and an extra copy of volume 1). Time to brush up on MIX. :)
    Shame on you! ;-) b.t.w. why do you have two copies of volume 1? Did you forget you had one already? Those three volumes are pearls, especially compared with all those 'X for dummies' and 'Y in 21 days' crapola ...
    cenosillicaphobia: the fear for an empty beer glass

  16. #16
    gimbal2 is offline Just a guy
    Join Date
    Jun 2013
    Location
    Netherlands
    Posts
    3,596
    Rep Power
    5

    Default Re: Random shuffling

    embarrassingly, I have none of those books, nor have I ever seen them. 140 bucks for the entire set is quite an investment :) Reading what it is all about though... *clears throat*

    DO WANT! MUST HAVE!
    "Syntactic sugar causes cancer of the semicolon." -- Alan Perlis

  17. #17
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,310
    Blog Entries
    7
    Rep Power
    20

    Default Re: Random shuffling

    Quote Originally Posted by gimbal2 View Post
    embarrassingly, I have none of those books, nor have I ever seen them. 140 bucks for the entire set is quite an investment :) Reading what it is all about though... *clears throat*

    DO WANT! MUST HAVE!
    140 bucks (euros?) is quite a lot of money but they're worth it imho. I can't remember what I payed for them thirty or so years ago but I do remember they were expensive in those days ... the beauty of those books is (again, imho) that Knuth proves everything; those or not just books on programming, they're books on discrete maths too. The only 'downside' (mind the quotes) is that MIX language. Every example is presented in MIX, a virtual assembly language, but it doesn't bother me much ... maybe you can buy them on a second hand market? Knuth also planned a volume IV (Compilers) but it never really saw the light ...

    kind regards,

    Jos
    cenosillicaphobia: the fear for an empty beer glass

  18. #18
    gimbal2 is offline Just a guy
    Join Date
    Jun 2013
    Location
    Netherlands
    Posts
    3,596
    Rep Power
    5

    Default Re: Random shuffling

    Hm, this amazon boxset references a '4a'.

    The Art of Computer Programming, Volumes 1-4A Boxed Set: Donald E. Knuth: 9780321751041: Amazon.com: Books

    EDIT:

    okay on bol.com I can get them for less in paperback form :) And again the quite recent (2011) "4a" book.
    Last edited by gimbal2; 07-26-2013 at 08:58 PM.
    "Syntactic sugar causes cancer of the semicolon." -- Alan Perlis

  19. #19
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,310
    Blog Entries
    7
    Rep Power
    20

    Default Re: Random shuffling

    Quote Originally Posted by gimbal2 View Post
    Hm, this amazon boxset references a '4a'.

    The Art of Computer Programming, Volumes 1-4A Boxed Set: Donald E. Knuth: 9780321751041: Amazon.com: Books

    EDIT:

    okay on bol.com I can get them for less in paperback form :) And again the quite recent (2011) "4a" book.
    Yep, that volume 4a is about combinatorial algorithms (one of my favorite subjects!); volume 5 is supposed to be about compilers. That man is amazing ... I'm not sure, but I am afraid that those paperback editions are going to fall apart soon; my hardcover editions hardly survived the years ;-)

    If you have LaTeX installed you can read a lot of articles on Donald Knuth's own web page.

    kind regards,

    Jos
    cenosillicaphobia: the fear for an empty beer glass

Similar Threads

  1. Replies: 0
    Last Post: 01-23-2012, 09:12 AM
  2. Poker Simulation (shuffling a deck of cards?)
    By StateofMind in forum New To Java
    Replies: 4
    Last Post: 04-06-2010, 08:59 PM
  3. Replies: 14
    Last Post: 10-19-2009, 10:57 AM
  4. Replies: 8
    Last Post: 04-19-2009, 05:50 PM
  5. Shuffling Help
    By KnivesACE in forum New To Java
    Replies: 1
    Last Post: 10-20-2008, 10:54 PM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •