0

I was working on a playing cards shuffle problem and found two solutions for it.

The target is to shuffle all 52 playing cards stored in a array as Card objects. Card class has id and name associated to it.

Now, one way is to iterate using for loop and then with the help of a temp card object holder and a random number generator, we can swap two objects. This continues until we reach half of the cards.

Another way is to implement comparable overriding compareto method with a random generator number, so we get a random response each time we call the method.

Which way is better you think?

javaAndBeyond
  • 520
  • 1
  • 9
  • 26
  • 3
    "so we get a random response each time we call the method." Not this way - the comparator needs to be consistent on each invocation, or sort algorithms may well complain, e.g. [TimSort reports violation of general contract](http://stackoverflow.com/questions/19325256/java-lang-illegalargumentexception-comparison-method-violates-its-general-contr). – Andy Turner Apr 25 '16 at 22:04
  • 1
    http://www.tutorialspoint.com/java/util/collections_shuffle.htm – Sergey Kalinichenko Apr 25 '16 at 22:06
  • Edited. I will use comparable instead. – javaAndBeyond Apr 25 '16 at 22:06
  • 4
    Neither of these is preferable to using `Collections.shuffle`, which just does the right thing. – Louis Wasserman Apr 25 '16 at 22:08
  • 1
    @user2296988 no, implementing `Comparable` to return random ordering has the same problem. When you invoke `Collections.sort` on a collection which implements `Comparable`, it simply invokes the overload with a comparator implementing natural ordering, i.e. it delegates the `Comparator.compare` call to `Comparable.compareTo`. – Andy Turner Apr 25 '16 at 22:09

2 Answers2

1

You should not do it by sorting with a comparator that returns random results, because then those random results can be inconsistent with one another (e.g., saying that a<b<c<a), and this can actually result in the distribution of orderings you get being far from uniform. See e.g. this demonstration by Mike Bostock. Also, it takes longer, not that that should matter for shuffling 52 objects.

The standard way to do it does involve a loop, but your description sounds peculiar and I suspect what you have in mind may also not produce the ideal results. (If the question is updated to make it clearer what the "iterate using for loop" approach is meant to be, I will update this.)

(There is a way to get good shuffling by sorting: pair each element up with a random number -- e.g., a random floating-point number in the range 0..1 -- and then sort using that number as key. But this is slower than Fisher-Yates and requires extra memory. In lower-level languages it generally also takes more code; in higher-level languages it can be terser; I'd guess that for Java it ends up being about equal.)

[EDITED to add:] As Louis Wasserman very wisely says in comments, when your language's standard library has a ready-made function to do a thing, you should generally use it. Unless you're doing this for, e.g., a homework assignment that requires you to find and implement an algorithm to solve the problem.

Gareth McCaughan
  • 19,888
  • 1
  • 41
  • 62
  • your pairing in python 2 does something like `map(lambda x, y: y, sorted(map(lambda x: (random(), x)))` java stream api, or any good functional programing library should be similar in Java. – njzk2 Apr 25 '16 at 22:13
  • Yup, that's it. Is your point that in some languages it doesn't end up being more code than Fisher-Yates after all? OK, I agree and will adjust my answer accordingly. ... Now done. – Gareth McCaughan Apr 25 '16 at 22:15
0

First of all, the comparator you've described wont work. More on this here. TLDR: comparsions must be reproducible, so if your comparator says that a is less then b next time when comparing b to a it should return "greater", not a random value. The same for Comparable.

If I were you, I'd rather use Collections#shuffle method, which "randomly permutes the specified list using a default source of randomness. All permutations occur with approximately equal likelihood". It's always better to rely on someone's code, then write your own, especially if it is in a standard library.

Community
  • 1
  • 1
madhead
  • 31,729
  • 16
  • 153
  • 201