Arrays/Java/FisherYates - Revision history

Admin: Replacing charlesreid1.com:3000 with git.charlesreid1.com

2019-10-09T03:16:02Z

Replacing charlesreid1.com:3000 with git.charlesreid1.com

← Older revision		Revision as of 03:16, 9 October 2019
Line 20:		Line 20:
	==Arrays==		==Arrays==

	Example of class: https://charlesreid1.com~~:3000~~/cs/java/src/master/arrays/fisher-yates/FisherYates.java		Example of class: https://git.charlesreid1.com/cs/java/src/master/arrays/fisher-yates/FisherYates.java

	===Deck of Cards===		===Deck of Cards===

Admin: /* Flags */

2017-06-02T21:54:39Z

Flags

← Older revision		Revision as of 21:54, 2 June 2017
Line 129:		Line 129:
	[[Category:Java]]		[[Category:Java]]
	[[Category:Arrays]]		[[Category:Arrays]]
	[[Category:~~Shuffling~~]]		[[Category:Random]]
			[[Category:Shuffle]]

Admin: /* Driver to test */

2017-06-02T21:36:37Z

Driver to test

← Older revision		Revision as of 21:36, 2 June 2017
Line 119:		Line 119:





			=Flags=

			{{DataStructuresFlag}}

	[[Category:CS]]		[[Category:CS]]

Admin: /* Driver to test */

2017-06-02T21:36:21Z

Driver to test

← Older revision		Revision as of 21:36, 2 June 2017
Line 78:		Line 78:
	===Driver to test===		===Driver to test===

			<pre>
	/** Hope you like cards.		/** Hope you like cards.
	*		*
Line 116:		Line 117:
	}		}
	</pre>		</pre>



			[[Category:CS]]
			[[Category:Java]]
			[[Category:Arrays]]
			[[Category:Shuffling]]

Admin: /* Deck of Cards */

2017-06-02T21:35:46Z

Deck of Cards

← Older revision		Revision as of 21:35, 2 June 2017
Line 19:		Line 19:

	==Arrays==		==Arrays==

			Example of class: https://charlesreid1.com:3000/cs/java/src/master/arrays/fisher-yates/FisherYates.java

	===Deck of Cards===		===Deck of Cards===
Line 55:		Line 57:
	int n = inputs.length;		int n = inputs.length;
	for(int j=n-1; j>0; j--) {		for(int j=n-1; j>0; j--) {
	~~// don't want to do the case of j==0.~~
	~~// if you do, you have have a 1 in n chance of un-sorting,~~
	~~// or un-doing or leaving out two pairs from the shuffle.~~
	//
	// Fisher Yates shuffle:		// Fisher Yates shuffle:
	// j starts at n-1		// j starts at n-1
Line 76:		Line 74:

	}		}
			</pre>

			===Driver to test===

	/** Hope you like cards.		/** Hope you like cards.

Admin: /* Pseudocode */

2017-06-02T21:32:07Z

Pseudocode

← Older revision		Revision as of 21:32, 2 June 2017
Line 6:		Line 6:

	The Fisher Yates shuffle algorithm walks through an entire list of numbers, starting at the back. The pointer points to the index being shuffled. A random index between 0 and the current index being shuffled is selected, and the two values are swapped. The pointer then decrements by one (moves one index closer to the front of the list).		The Fisher Yates shuffle algorithm walks through an entire list of numbers, starting at the back. The pointer points to the index being shuffled. A random index between 0 and the current index being shuffled is selected, and the two values are swapped. The pointer then decrements by one (moves one index closer to the front of the list).

			Note that the index i should not cover the first item in the list (i=0).

	The pseudocode for shuffling an array of length n is:		The pseudocode for shuffling an array of length n is:

	<pre>		<pre>
	for i in 1..n:		for i in n..1:
	j = random number in 0..i		j = random number in 0..i
	swap array[i], array[j]		swap array[i], array[j]
			decrement i
	</pre>		</pre>

Admin: /* Arrays */

2017-06-02T21:30:51Z

Arrays

← Older revision		Revision as of 21:30, 2 June 2017
Line 16:		Line 16:

	==Arrays==		==Arrays==

			===Deck of Cards===

			This example tests the Fisher Yates shuffle method by creating a deck of cards as an array of Strings, and passes the array to the method to shuffle it in place.

	<pre>		<pre>

Admin: Created page with "=Fisher Yates Shuffle= Implementation of a classic shuffle algorithm using various Java data structures. ==Pseudocode== The Fisher Yates shuffle algorithm walks through an..."

2017-06-02T21:30:04Z

Created page with "=Fisher Yates Shuffle= Implementation of a classic shuffle algorithm using various Java data structures. ==Pseudocode== The Fisher Yates shuffle algorithm walks through an..."

New page

=Fisher Yates Shuffle=

Implementation of a classic shuffle algorithm using various Java data structures.

==Pseudocode==

The Fisher Yates shuffle algorithm walks through an entire list of numbers, starting at the back. The pointer points to the index being shuffled. A random index between 0 and the current index being shuffled is selected, and the two values are swapped. The pointer then decrements by one (moves one index closer to the front of the list).

The pseudocode for shuffling an array of length n is:

<pre>
for i in 1..n:
j = random number in 0..i
swap array[i], array[j]
</pre>

==Arrays==

<pre>
import java.io.*;
import java.util.*;

/**
* Fisher Yates Shuffle class.
*
* This class implements the Fisher-Yates shuffle
* as a static method.
*
* This accepts an array as input, and shuffles it in-place.
*/
public class FisherYates {

/** swap two "Objects" */
private static void swap(Object[] arr, int x, int y){
if(x != y) {
Object temp = arr[x];
arr[x] = arr[y];
arr[y] = temp;
}
}

/**
* Fisher Yates shuffle : this is getting complicated.
* How to implement this with arrays of generic types?
*/
public static void shuffleFY(String[] inputs) {
Random r = new Random();
int n = inputs.length;
for(int j=n-1; j>0; j--) {
// don't want to do the case of j==0.
// if you do, you have have a 1 in n chance of un-sorting,
// or un-doing or leaving out two pairs from the shuffle.
//
// Fisher Yates shuffle:
// j starts at n-1
// swap with random element between 0 and j (INCLUSIVE)
int k = r.nextInt(j+1);
swap(inputs, j, k);
}
}

public static void main(String[] args) {
Deck d = new Deck();
System.out.println(d);
System.out.println("-------------------");
shuffleFY(d.toArray());
System.out.println(d);
}

}

/** Hope you like cards.
*
* This implements a standard deck of 52 cards.
*/
class Deck {
private String[] deck;

// define how your cards work
private final int capacity = 52;
private final String[] SUITS = {"SPADES","CLUBS","HEARTS","DIAMONDS"};
private final String[] FACES = {"A","2","3","4","5","6","7","8","9","10","J","Q","K"};

/** constructor don't need no arguments */
public Deck(){
deck = new String[capacity];

int card = 0;
for(String suit : SUITS) {
for(String face : FACES) {
deck[card] = face + " of " + suit;
card++;
}
}
}

/** turn into string array */
public String[] toArray() { return deck; }

/** turn into string */
public String toString() {
StringBuffer s = new StringBuffer();
for(String this_card : deck) {
s.append(this_card+"\n");
}
return s.toString();
}
}
</pre>