• Post Reply Bookmark Topic Watch Topic
  • New Topic

Method to rearrange elements in an array list?  RSS feed

 
Christopher Laurenzano
Ranch Hand
Posts: 105
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Okay, so I'm still trying to learn how to read and understand the API's.

I've got an array list and I was wondering if there was a method that can randomly re arrange the elements in terms of their index positions.
 
Stefan Evans
Bartender
Posts: 1837
10
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
The java.util.Collections class has a number of static helper methods in it. One of those should be able to do the job.
 
Campbell Ritchie
Marshal
Posts: 56570
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
They do depend on the elements in your List fulfilling certain conditions.
 
Dave Tolls
Ranch Foreman
Posts: 3065
37
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Campbell Ritchie wrote:They do depend on the elements in your List fulfilling certain conditions.


I am now going to have to eat my lunch wondering what you are referring to...
The method I'm thinking of doesn't have (as far as I know) any requirements for the elements.
 
Campbell Ritchie
Marshal
Posts: 56570
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Damn! I should learn to read.

I didn't see the bit about randomly. You are right: random rearrangement does not have any preconditions about the elements. Sorry.
 
Tushar Goel
Ranch Hand
Posts: 934
4
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I suppose to get the perfect randomness you need to shuffle it first correctly.
 
Campbell Ritchie
Marshal
Posts: 56570
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
You don't get perfect randomness like that; there is no way to be absolutely certain a large List has been properly randomised. You can try randomising it several times which will probably get you close, but a bit of probability will help. Remember that the number of different orders of an n‑element list is n!, and factorials can increase rapidly.
 
Campbell Ritchie
Marshal
Posts: 56570
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Actually the Collections class gives a description of the method it uses and it appears to be pretty close to random.
 
Tushar Goel
Ranch Hand
Posts: 934
4
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
You are right but in my algorthim class (In Coursera by Robert Sedgwick), he said we can get perfect randomness using Knuth Shuffle. It will give the randomness in n! using O(n). But yes than it also depends upon the random number generated using Math.random().
 
Campbell Ritchie
Marshal
Posts: 56570
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thank you for the correction.
There is another randomising class; since it extends java.util.Random you can use it in its place.
The Collections documentation does say that method runs in O(n) time.
 
Tushar Goel
Ranch Hand
Posts: 934
4
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Yup thanks
 
Campbell Ritchie
Marshal
Posts: 56570
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
You can still get non‑randomness if you don't use enough bits for the random generator. Look at this Wikipedia page where it says you need 226 bits to be sure to shuffle a pack of 52 cards correctly.
 
Tushar Goel
Ranch Hand
Posts: 934
4
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
You are right Campbell. As per Wikipedia, we need to have 226 bits for 52! but we only have 32 bit or 64 bit available that means we can get perfect randomness for upto 20 bit list length(as per Wikipedia).

 
Campbell Ritchie
Marshal
Posts: 56570
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Since 12! is 479001600 and 21! is 51090942171709440000, you are going to be running out of your 32/64 bits before 12! and 21!
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!