• Post Reply Bookmark Topic Watch Topic
  • New Topic

Shuffling an array  RSS feed

 
Prasanna Raman
Ranch Hand
Posts: 410
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hello,

While shuffling an array, if I use Collections.shuffle(), there is a chance that an element in a particular index in the input array can be present in the same index in the output array. Is there an existing method that handles that too? If not, how can I best handle it? After shuffling, will swapping every element with the last element work?
 
Henry Wong
author
Sheriff
Posts: 23295
125
C++ Chrome Eclipse IDE Firefox Browser Java jQuery Linux VI Editor Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Prasanna Raman wrote:While shuffling an array, if I use Collections.shuffle(), there is a chance that an element in a particular index in the input array can be present in the same index in the output array.


Yes. The result is random, so it is possible for some elements to be in their original position.

Prasanna Raman wrote:Is there an existing method that handles that too? If not, how can I best handle it? After shuffling, will swapping every element with the last element work?


Of course not, since the result is random, it is possible for any action that you do, will put the element back into the original position.

You only option is maintaining a copy of the collection, with the elements in the original position, so that you can check (and move) the elements, if they are in the original position.

Henry
 
Prasanna Raman
Ranch Hand
Posts: 410
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Henry Wong wrote:You only option is maintaining a copy of the collection, with the elements in the original position, so that you can check (and move) the elements, if they are in the original position.Henry
This method seems to work. I've tested it and it seems to work fine. Could you please check?
This is after I do Collections.shuffle().
 
Winston Gutkowski
Bartender
Posts: 10575
66
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Prasanna Raman wrote:Could you please check?

Well, the only thing I wonder about with the code is: What is 'bs'? You already have two arrays: 'a' and 'b'.

Also:
1. How do you know that the shuffle didn't change the position of the element? You're doing a value check, not an identity check.
2. Aren't you worried about putting "unmoved" elements in a predictable position - ie, probably the end? The whole point of shuffling is to randomize a Collection.
3. What if the element you end up swapping with has the same value?.

Personally, I'd be interested in knowing why you think you need to do this in the first place. Whatever you call it, it certainly isn't "shuffling".

Winston
 
Mike Simmons
Ranch Hand
Posts: 3090
14
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Yes, this method does not result in the same uniform distribution of probabilities that Collections.shuffle() does. And, the whole concept of your "shuffle" really only works if there are no duplicates. As an extreme example, what if the elements in the array are all identical? Is there any way to shuffle that, according to your specification?
 
Mike Simmons
Ranch Hand
Posts: 3090
14
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
As another example, what if the array has only two elements, e.g.

{"A", "B"}

If you "shuffle" this, should there be only one possible result?

{"B", "A"}

Or should there be two possibilities, equally probable?

{"A", "B"}
{"B", "A"}

Most of us would regard the latter description is more natural for a "shuffle". But perhaps you really do want the former.
 
Paweł Baczyński
Bartender
Posts: 2083
44
Firefox Browser IntelliJ IDE Java Linux Spring
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
What if the array has only one element? It's impossible to shuffle it without having an element in a position other than its original location.
 
Consider Paul's rocket mass heater.
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!