Array shuffling

[Botre]

LAST UPDATE: MARCH 10, 2015

 

You could use Collections by converting the array to a List but that would be more expensive and wouldn't work for primitives.

 

The ArrayUtilities.swapEntriesByIndex(...) method can be found here: http://osbot.org/forum/topic/65570-some-array-utilities-for-your-convenience/

package org.bjornkrols.algorithms.sequence_permutation;

import java.util.Random;

import org.bjornkrols.utilities.array.ArrayUtilities;

/**
 * Generates a random permutation of a finite set in an unbiased manner.
 * 
 * These methods can be used both procedurally (by not using the return value) 
 * and as a factory (by calling it on a copy of an existing array for example).
 * 
 * @param set	        The set to be shuffled.
 * @return		The shuffled set.
 * @author 		Bjorn Krols (Botre)
 * @version		0.2
 * @since		March 5, 2015
 */

public final class KnuthShuffle {

	private static final Random RANDOM = new Random();
	
	private KnuthShuffle() { 
		// This class should never be instantiated.
		// Do not delete or make accessible.
	}
	
	/**
	 * @see	KnuthShuffle
	 */
	public static boolean[] shuffle(boolean[] set) {
		int length = set.length;
		// For each index i of the array, starting at 1 (because i = 0 would systematically return j = 0).
		for (int i = 1; i < length; i++) {
			// Find j, a random index between 0 (inclusive) and i (inclusive).
			int j = RANDOM.nextInt(i + 1);
			// Swap the entries at indexes i and j.
			ArrayUtilities.swapEntriesByIndex(set, i, j);
		}
		return set;
	}
	
	/**
	 * @see	KnuthShuffle
	 */
	public static byte[] shuffle(byte[] set) {
		int length = set.length;
		for (int i = 1; i < length; i++) ArrayUtilities.swapEntriesByIndex(set, i, RANDOM.nextInt(i + 1));
		return set;
	}
	
	/**
	 * @see	KnuthShuffle
	 */
	public static short[] shuffle(short[] set) {
		int length = set.length;
		for (int i = 1; i < length; i++) ArrayUtilities.swapEntriesByIndex(set, i, RANDOM.nextInt(i + 1));
		return set;
	}
	
	/**
	 * @see	KnuthShuffle
	 */
	public static char[] shuffle(char[] set) {
		int length = set.length;
		for (int i = 1; i < length; i++) ArrayUtilities.swapEntriesByIndex(set, i, RANDOM.nextInt(i + 1));
		return set;
	}
	
	/**
	 * @see	KnuthShuffle
	 */
	public static int[] shuffle(int[] set) {
		int length = set.length;
		for (int i = 1; i < length; i++) ArrayUtilities.swapEntriesByIndex(set, i, RANDOM.nextInt(i + 1));
		return set;
	}
	
	/**
	 * @see	KnuthShuffle
	 */
	public static long[] shuffle(long[] set) {	
		int length = set.length;
		for (int i = 1; i < length; i++) ArrayUtilities.swapEntriesByIndex(set, i, RANDOM.nextInt(i + 1));
		return set;
	}
	
	/**
	 * @see	KnuthShuffle
	 */
	public static float[] shuffle(float[] set) {
		int length = set.length;
		for (int i = 1; i < length; i++) ArrayUtilities.swapEntriesByIndex(set, i, RANDOM.nextInt(i + 1));
		return set;
	}
	
	/**
	 * @see	KnuthShuffle
	 */
	public static double[] shuffle(double[] set) {
		int length = set.length;
		for (int i = 1; i < length; i++) ArrayUtilities.swapEntriesByIndex(set, i, RANDOM.nextInt(i + 1));
		return set;
	}
	
	/**
	 * @see	KnuthShuffle
	 */
	public static Object[] shuffle(Object[] set) {
		int length = set.length;
		for (int i = 1; i < length; i++) ArrayUtilities.swapEntriesByIndex(set, i, RANDOM.nextInt(i + 1));
		return set;
	}
	
}

Edited March 10, 2015 by Botre

[VladBots]

sup with your @see KnuthShuffle plz l2 doc

[Botre]

sup with your @see KnuthShuffle plz l2 doc

 

They all do the same, not going to copy and paste the explanation 10 times every time I feel like changing / completing / detailing the description

Edited March 6, 2015 by Botre

[VladBots]

They all do the same, not going to copy and paste the explanation 10 times every time I feel like changing / completing / detailing the description

fair enough xd

[Botre]

Updated

[Mysteryy]

Covering shuffling in algorithms class huh?

I feel like I always know what your doing in class by what you post. :p