More on Shuffledness

DEck of playing cards
Dowload from Creazilla.com

So I’ve updated my shuffledness calculation. This is a bit of a work in progress so probably isn’t the last version.  One of the things I’m interested in is what is the optimal number of swaps to get a good shuffled deck of cards. The shuffle algorithm picks two random indexes in the array 0-51 and then swaps the contents.

Obviously doing this 10 times would only shuffle at most 20 cards and probably fewer as there’s no checks for repeats. The only check is that both indexes (indices?) are not the same. So I want to experiment and see what an optimal value for numTries should be..

void ShuffleDeck(int numtries) {
	int firstIndex, secondIndex;
	for (int i = 0; i < numtries; i++) {
		do {
			firstIndex = rand() % 52;
			secondIndex = rand() % 52;
		}
		while (firstIndex == secondIndex);
		int value = deck[firstIndex];
		deck[firstIndex] = deck[secondIndex];
		deck[secondIndex] = value;
	}
}

Anyway, I’ve added a CalcDistance() function. This looks at each card and calculates how far it has moved from it’s original position.  It then divides this by the maximum distance it could have moved to get a move “factor”. These are summed up and divided by 52 to give an average move factor. That’s your CalcDistance() function.

float CalcDistance() {
	float distance = 0.0f;
	for (int i = 0; i < 52; i++) {
		float distanceDiv = (i < 26) ? 51 - i : i-1;
		//printf("%i: %3.0f\n", i, distanceDiv);
		distance += (abs(deck[i] - i) / distanceDiv);
	}
	return distance/52.0f;
}

The only thing odd about this function is the distanceDiv value which starts at 51, decreases to 25 then increases to 50. The printf let me check that was correct.

This is the current state of the program which I’ve listed fully below. Enjoy! It’s 63 lines long.

// shuffledness.c : This measures how shuffled a deck of cards is
// cards are hjeld as values 0-51 in a 52 int aaray.

#include <time.h>
#include <stdio.h>
#include <stdlib.h>

int deck[52];
time_t t;

// Order the cards 0-51. 0 = Acew Hards,13 = Ace Clubs,26 = Ace of Diamonds and 51 = King of Spades
void InitDeck() {
	for (int i = 0; i < 52; i++) {
		deck[i] = i;
	}
}

// Works on glovbal array deck and calculates a value for how displayed each card is
float CalcDisorder() {
	int total=0;
	for (int i = 1; i < 52; i++) {
		total += abs(deck[i] - deck[i - 1]);
	}
	printf("Total = %d\n", total);
	return total / (52.0f * 26.0f);
}

// Sum up distance card moved/max distance
float CalcDistance() {
	float distance = 0.0f;
	for (int i = 0; i < 52; i++) {
		float distanceDiv = (i < 26) ? 51 - i : i-1;
		//printf("%i: %3.0f\n", i, distanceDiv);
		distance += (abs(deck[i] - i) / distanceDiv);
	}
	return distance/52.0f;
}

// Shuffle a deck by swapping two random cards a specified number of times
void ShuffleDeck(int numtries) {
	int firstIndex, secondIndex;
	for (int i = 0; i < numtries; i++) {
		do {
			firstIndex = rand() % 52;
			secondIndex = rand() % 52;
		}
		while (firstIndex == secondIndex);
		int value = deck[firstIndex];
		deck[firstIndex] = deck[secondIndex];
		deck[secondIndex] = value;
	}
}

int main() {
	/* Intializes random number generator */
	srand((unsigned)time(&t));
	for (int i = 0; i < 25; i++) {
		InitDeck();
		ShuffleDeck(1000);
		printf("CalcDisorder() ==%f x %f = %f\n", CalcDisorder(),CalcDistance(),(double)CalcDisorder() * CalcDistance());
	}
	return 0;
}

Because I’m multiplying the two factors (disorder and Distance, the final value is never getting much above 0.35 and I’d prefer it to be in the range 0-0.999. Suggestions welcomed.

.

Leave a Reply

Your email address will not be published. Required fields are marked *