Algo challenge

[Discere Faciendo]

This is a general challenge, opened to all.

Recently, I saw code I wrote when I was a kid that shuffled a regular deck of cards. I made no attempt to randomize the process (give me a break, I was 11), so the shuffle is entirely predictable. My solution, at the time, was the following:

1)Divide the original deck into halves
2)Insert the top half into odd positions of a copy.
3)Insert the bottom half into even positions of a copy.
4)Repeat less than 26 times (otherwise, you reverse the order of the deck)

The challenge: Can you come up with a better/shorter/(more elegant) solution?

Instructions:
Submit code, pseudo-code, or no code. Your choice. What's important is your algorithm. However, if you choose to submit code, just write a function with the following declaration: void shuffle(string* card);

There is no time constraint. Originally, I had 5-10 minutes to write the code. But since it mimicked a real world process I was already familiar with and it was unrandomized, it was relatively easy to code.

Have fun guys!

- Ray

Just for fun,the following is the code I wrote back then:

void shuffle(string* card, int TRIALS){
	for (int run=0; run<TRIALS; run++){
		int half = 0;
		string copy[52];
		for (int i=0; i<52; i++){
			if(i%2) {                       //even slots
				copy[i] = card[half];
				half++;
			}
			else{                          //odd slots
				half = i/2;
				copy[i] = card[half+26];
			}
		}
		//Update Card Array
		for (int i=0; i<52; i++)
			card[i] = copy[i];
	}
}

[Bazzy]

What about standard algorithms? http://www.cplusplus.com/reference/algorithm/random_shuffle/

[helios]

For i=0 to 50, pick a random card in the range [i;51] and swap it with i.

[Discere Faciendo]

It was implied; but I should have been more explicit. The goal is to come up with a process of your own design and not use one that's in existence. So simply using a standard algo from an existing library is not allowed . I know it's reinventing the wheel and impractical. But the purpose of this challenge was an exercise in creativity and to see different solutions people come up with. Cheers!

[jsmith]

Well I was just discussing this today with a colleague in the context of our work actually,
and he jokingly came up with this (pardon I'm using STL algos; just imagine I actually
wrote the code for quicksort, boost::lambda, and rand):

std::vector<std::string> deck;  // Assume it is initialized with 52 cards...
std::sort( deck.begin(), deck.end(),  !( rand() %2 ) );  // ! to force bool conversion 

I like the irony of calling "sort" to randomize a data structure. We call it the
"random sort".

NB: I have no idea if the above compiles; I haven't tried it.

[firedraco]

Wow, that's an interesting idea! >_>

[Zhuge]

Heh, I would never have thought to try to randomly tell whether one item is greater than the other to shuffle something. Interesting.

[helios]

Couldn't you just as easily do bool(rand()%2) (or &1)?

[Zhuge]

That was going to be my question but I imagine the answer is something like, "it's faster," and I've seen some instances where !! was used to convert into a bool...no idea why, since casting is much more obvious to the reader.

[helios]

!! is way cooler.

[Zhuge]

non_boolean_type YoureDead;
typedef bool And;
And then = !!YoureDead;

"So, the next line of code reads, 'and then, bang bang you're dead!'"

Additonally: Apologies for dragging this off-topic discussion out, but I couldn't resist trying something like this.

[sdgunter]

void shuffle(int array[])
{
int temp;
int rnd2;
int rnd1;
for (int i = 0; i < 100; i++) {
rnd1 = (rand() % 51);
rnd2 = (rand() % 51);
if (rnd1 != rnd2) {
temp = array[rnd1];
array[rnd1] = array[rnd2];
array[rnd2] = temp;
}
}
}

[jsmith]

Well nuts, the random sort doesn't work. std::sort() sometimes causes the array to get corrupted. I don't know how.

#include <algorithm>
#include <bitset>
#include <cstdlib>
#include <iostream>
#include <sys/time.h>

bool comp( int, int ) {
    return rand() % 2;
}

int main() {
    int a[ 52 ];

    srand( time( 0 ) );

    for( int i = 0; i < 52; ++i )
        a[ i ] = i;

    std::sort( a, a + 52, comp );

    std::bitset<52> present;
    for( int i = 0; i < 52; ++i ) {
        std::cout << a[ i ] << std::endl;
        if( a[ i ] < 0 || a[ i ] >= 52 )
            std::cout << "Invalid card" << std::endl;
        else if( present[ a[ i ] ] )
            std::cout << "Duplicate card" << std::endl;
        else
            present.set( a[ i ] );
    }

    if( present.count() != 52 )
        std::cout << "Not all cards accounted for" << std::endl;
}

[jRaskell]

Can you come up with a better/shorter/(more elegant) solution?

How about a different twist, who can come up with the best Rube Goldberg shuffle algorithm?

Something like:

float std_dev = 0;
int ave_dif = 0;
int num_swaps = 0;

vector<int> deck;
vector<int> neighbor_difference;

for(int x = 1; x <= 52; x++)
	deck.push_back(x);

//Rube shuffle
while(ave_dif < 17 || std_dev < 13.0){

	//Swap two cards
	int card1 = rand() % deck.size();
	int card2 = rand() % deck.size();
	int tmpcard = deck[card1];
	deck[card1] = deck[card2];
	deck[card2] = tmpcard;
	num_swaps++;
	
	//Neighbor differences
	neighbor_difference.clear();
	int sum = 0;
	for(int x = 0; x < deck.size() - 1; x++){
		if(deck[x] > deck[x+1]){
			neighbor_difference.push_back(deck[x] - deck[x+1]);
			sum += deck[x] - deck[x+1];
		}
		else{
			neighbor_difference.push_back(deck[x+1] - deck[x]);
			sum += deck[x+1] - deck[x];
		}
	}
	ave_dif = sum / neighbor_difference.size();
	
	//Neighbor Standard Deviation
	cout << endl << "Iteration " << num_swaps << endl;
	cout << "Dif Sum: " << sum << endl;
	cout << "Average difference: " << ave_dif << endl;
	
	sum = 0;
	for(int x = 0; x < neighbor_difference.size(); x++)
		sum += (neighbor_difference[x] - ave_dif) * (neighbor_difference[x] - ave_dif);
	
	std_dev = sqrt( sum / neighbor_difference.size());
	
	cout << "Standard Deviation: " << std_dev << endl;
}

Disclaimer: I make no claims as to the accuracy of how I'm calculating the Standard Deviation. That's just off the top of my head and I haven't done any sort of statistical analysis in a very long time.