# Random shuffling

• 07-24-2013, 05:29 PM
dojob
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:

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?
• 07-24-2013, 05:54 PM
Di Immortalis
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.
• 07-24-2013, 06:18 PM
dojob
Re: Random shuffling
Quote:

Originally Posted by Di Immortalis
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.
• 07-24-2013, 06:24 PM
JosAH
Re: Random shuffling
Google for "Knuth shuffle" or "Fisher Yates shuffle" for a good random shuffle algorithm.

kind regards,

Jos
• 07-25-2013, 05:35 AM
dojob
Re: Random shuffling
Thanks for the information.
• 07-25-2013, 05:20 PM
jim829
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
• 07-26-2013, 01:05 PM
dojob
Re: Random shuffling
Quote:

Originally Posted by jim829
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?

Quote:

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]
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]);        }```
• 07-26-2013, 03:18 PM
jim829
Re: Random shuffling
It took me a moment to find the error.

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
• 07-26-2013, 04:37 PM
dojob
Re: Random shuffling
Quote:

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

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

`for(int i = myList.length - 1; i > 0; i--)`
with
Code:

`for(int i = 0; i < myList.length; i++)`
the arrays will also never shuffle back to the original arrangement. Why is it so?
• 07-26-2013, 06:06 PM
jim829
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
• 07-26-2013, 06:32 PM
JosAH
Re: Random shuffling
Quote:

Originally Posted by jim829
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
• 07-26-2013, 06:47 PM
jim829
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
• 07-26-2013, 07:01 PM
JosAH
Re: Random shuffling
Quote:

Originally Posted by jim829
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
• 07-26-2013, 07:06 PM
jim829
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
• 07-26-2013, 07:59 PM
JosAH
Re: Random shuffling
Quote:

Originally Posted by jim829
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 ...
• 07-26-2013, 08:39 PM
gimbal2
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!
• 07-26-2013, 08:52 PM
JosAH
Re: Random shuffling
Quote:

Originally Posted by gimbal2
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
• 07-26-2013, 08:56 PM
gimbal2
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.
• 07-27-2013, 09:03 AM
JosAH
Re: Random shuffling
Quote:

Originally Posted by gimbal2
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