Fisher-Yates shuffle Java implementation

Question

This is my attempt at an implementation of the modern Fisher-Yates shuffle in Java. I'm not sure if it can be made more efficient, but I did my best to make it as simple as possible, and I learned how to use generics specifically for this, so If I did something wrong in that regard, let me know.

package com.kestrel.test;
import java.util.ArrayList;
import java.util.Random;
public class ShuffleTest
{
 public static <T> ArrayList<T> shuffle(ArrayList<T> a)
 {
 Random rand = new Random();
 for(int n = a.size() - 1; n > 0; n--)
 {
 int index = rand.nextInt(n + 1);
 T temp = a.get(index);
 a.set(index, a.get(n));
 a.set(n, temp);
 }
 return a;
 }
 public static <T> T[] shuffle(T[] a)
 {
 Random rand = new Random();
 for(int n = a.length - 1; n > 0; n--)
 {
 int index = rand.nextInt(n + 1);
 T temp = a[index];
 a[index] = a[n];
 a[n] = temp;
 }
 return a;
 }
}

I know that I would have to implement methods for all of the primitive array types separately, but I'm short on time, and I don't think autoboxing will slow down my code all that much.

Answer 1

You are both mutating & returning the value you are passing to the function. Pick one. Either return void or return a new array/ArrayList without mutating the input.

Your first shuffle() method requires an ArrayList, yet any Collection which implements the List interface would work, and will work well if it has \$O(1)\$ get & set complexity. So consider loosening the type from a concrete type to the List interface. (It will even work for LinkedList, albeit with horrible performance, but working slowly is arguably better than not being able to work at all.)

---

The value returned by ArrayList<T>::set(int idx, T obj) is the previous contents of that location. Therefor, the temporary is not necessary.

 T temp = a.get(index);
 a.set(index, a.get(n));
 a.set(n, temp);

can become:

 a.set(n, a.set(index, a.get(n)));

or more clearly, just Collections.swap(a, n, index);.

Similarly,

 T temp = a[index];
 a[index] = a[n];
 a[n] = temp;

can also become Collections.swap(a, n, index);, a similar function which takes a T[] instead of a List<?> as the first argument.

---

Here is an implementation of your "something like K<T> using generics" from the comments. And no longer coding from the hip, so the Java syntax is actually correct.

MacBook-Pro:~ aneufeld$ jshell
| Welcome to JShell -- Version 10.0.1
| For an introduction type: /help intro
jshell> public class ShuffleTest {
 ...> public static <T,K extends List<T>> K shuffle(Collection<T> a, Supplier<K> supplier) {
 ...> K dup = supplier.get();
 ...> dup.addAll(a);
 ...> Collections.shuffle(dup); // Or use your shuffle implementation
 ...> return dup;
 ...> }
 ...> }
| created class ShuffleTest
jshell> var orig = List.of("Hello", "world");
orig ==> [Hello, world]
jshell> ArrayList<String> shuffled = ShuffleTest.shuffle(orig, ArrayList<String>::new);
shuffled ==> [world, Hello]
jshell> 

• AJNeufeld: Due to "Type Erasure", if you change ArrayList to List, and you pass in an ArrayList, you will notice zero difference in behaviour or performance, because exactly the same bytecode will being generated. There shouldn’t be any downside.
• AJNeufeld: Java is strictly pass-by-value. However, what is being passed by value is a reference to the object (in this case, List or ArrayList). If you change the object in anyway, everyone with a reference to the object will see the change. If you mutate the a object, the caller will see their list has changed. If you set the variable a to a different value, such as null, the caller won’t see that change because the reference was passed by value.
• AJNeufeld: I’d not return anything. public static <T> void shuffle(List<T> a). Because the list is being mutated, you don’t need a return value to assign to anything.
• AJNeufeld: In that case, perhaps public static <T> ArrayList<T> shuffle(Collection<T> c). The first thing the function should do would be ArrayList<T> dup = new ArrayList<T>(c);, and then it would be free to sort this duplicate list. You could pass in an ArrayList<>, but you could also pass in a Vector<>. Even a LinkedList<> would now shuffle in \$O(n)\$ time. Unordered collections like HashSet<> could even be shuffled. The catch is: it would always return an ArrayList<>.
• AJNeufeld: Like: public static <T, K extends List<? extends T>> K shuffle(K a) { ... }? Sure. But now you need to use reflection to create your duplicate K. Better, you could pass in a Supplier<K> to create the object that will be returned. Coding from the hip ... something like ... public static <T, K extends List<? extends T>> K shuffle(K a, Supplier<K> supplier) { K dup = supplier.get(); dup.addAll(a); ...do_the_shuffle... ; return dup; }. You would call it with ... ArrayList<String> shuffled_dup = ShuffleTest::shuffle(orig, ArrayList<String>::new);