Fisher Yates or Durstenfeld Shuffle in Java
Fisher-Yates shuffle or Knuth shuffle is an algorithm for generating a random shuffle of a finite set. A typical use case would be shuffling the characters in a word or string. A modern efficient variant of Fisher-Yates is known as Durstenfeld algorithm.
The Durstenfeld algorithm is,
for i from 0 to n − 2 do
j is a random integer such that i <= j < n
exchange a[j] and a[i]
end for
The following Java program demonstrates the use of Durstenfeld algorithm for shuffling characters in a word.
import java.util.concurrent.ThreadLocalRandom; /** * Example Java program to shuffle a word randomly using * modified Fisher-Yates algorithm (Durstenfeld algorithm) */ public class ShuffleWord2 { public static void main(String[] args) { ShuffleWord2 sw = new ShuffleWord2(); String word = "Superman"; String shuffled = sw.shuffle(word); System.out.println("Original word:"+word); System.out.println("Shuffled word:"+shuffled); } /** * Shuffles a given word. Uses Fisher-Yates/Durstenfeld algorithm * @param word * @return */ private String shuffle(String word) { String shuffledWord = word; // start with original int wordSize = word.length(); for(int i=0;i<wordSize-1;i++) { int j = ThreadLocalRandom.current().nextInt(i, wordSize); shuffledWord = swapCharacters(shuffledWord,j,i); } return shuffledWord; } /** * Swaps characters in a string using the given character positions * @param shuffledWord * @param position1 * @param position2 * @return */ private String swapCharacters(String shuffledWord, int position1, int position2) { char[] charArray = shuffledWord.toCharArray(); // Replace with a "swap" function, if desired: char temp = charArray[position1]; charArray[position1] = charArray[position2]; charArray[position2] = temp; return new String(charArray); } }