2

Following this question: Shuffling numbers in a map and selecting one.

Say you need to select a series of integers randomly from a List. Could a Collections.shuffle be considered as equivalent to repeatedly using Random#nextInt?

I'm not familiar with how shuffle is implemented and whether they could be seen as truly equivalent from a mathematical point of view (permutations). The link below does insist on the importance of using a single Random object.

http://www.javapractices.com/topic/TopicAction.do?Id=62

P.S: I'm aware that Collections.shuffle adds an operation in that it actually reorganizes content. It's the result I'm interested in.

Edit: Found this question on SO detailing the shuffle method as using what's called a Fisher-Yates shuffle: Java's Collections.shuffle is doing what?

Community
  • 1
  • 1
James P.
  • 19,313
  • 27
  • 97
  • 155
  • What do you mean by *equivalent*? That both return the exact same sequence? That both return values in the same range? That both probability distribution functions are the same? – Bruno Reis Jul 30 '11 at 08:51
  • Equivalent in the same way that algorithm A would be equivalent to algorithm B if they produced the exact same fixed results. Edit: Equivalent from the point of view of probability distribution as you say. – James P. Jul 30 '11 at 08:54
  • 1
    Just remember that Random#nextInt isn't really random anyway... it is pseudo-random, therefore deterministic. The same goes for `shuffle`. – Bruno Reis Jul 30 '11 at 09:03
  • You're right to point that out. There's some interesting information on the topic in this [question](http://stackoverflow.com/questions/6438155/how-to-check-if-a-function-really-gives-a-random-result) – James P. Jul 30 '11 at 09:06

1 Answers1

2

If you're asking if using Collections.shuffle and then using the resulting list of randomly-ordered numbers is equivalent to picking them one by one by using Random, the answer is no. The latter will quite likely return you the same index twice, which will result in duplicates.

Matti Virkkunen
  • 63,558
  • 9
  • 127
  • 159
  • Ok. Say the algorithm using Random includes a step where the randomly selected index is removed. Could they be considered equivalent then? I've updated the question with a relevant link from SO. – James P. Jul 30 '11 at 09:03
  • For a limited amount of operations (collection's size), yes. Until the collection runs out of elements. – Flavius Jul 30 '11 at 09:06
  • 1
    @James: For all intents and purposes, yes, that would make them equivalent. However removing indexes will likely not be as efficient as `Collections.shuffle`, which does the whole thing in-place (as long as the collection supports quick indexed access) – Matti Virkkunen Jul 30 '11 at 09:06