# Human (imperfect) array (card) shuffle written in C

I've got this humanoid_shuffle I wrote in Python. I've been wanting to learn C so as an exercise I ported it to C. As this is my first venture into C and even the ideas of memory management and the like, what are some ways to make this better from a code quality and efficiency perspective?

A couple of quick thoughts from a C beginner:

• Interesting how it's harder to justify creating multiple new copies of the array to juggle between.
• Seems like you have to be much more clever and less practical with C (obviously the Python version is much easier to follow).

Thoughts?

Python

@staticmethod
def humanoid_shuffle(items, num_shuffles=6):
# how many times items can be pulled from the same list consecutively
MAX_STREAK = 10

# divide list roughly in half
num_items = len(items)
end_range = int(num_items / 2 + random.randint(0, int(.1 * num_items)))
first_half = items[:end_range]  # list up to 0 - end_range
second_half = items[end_range:]  # list after end_range - len(items)

split_lists = (first_half, second_half)
mixed = []
streak = current_item_index = 0
# while both lists still contain items
while first_half and second_half:
# calc the percentage of remaining total items
remaining = (1 - float(len(mixed)) / num_items)
# if we happen to generate a random value less than the remaining percentage
# which will be continually be decreasing (along with the probability)
# or
# if MAX_STREAK is exceeded
if random.random() < remaining or streak > MAX_STREAK:
# switch which list is being used to pull items from
current_list_index = 1 ^ current_list_index
# reset streak counter
streak = 0

# pop the selected list onto the new (shuffled) list
mixed.append(split_lists[current_list_index].pop())
# increment streak of how many consecutive times a list has remained selected
streak += 1

mixed.extend(first_half)
mixed.extend(second_half)

num_shuffles -= 1
# if we still have shuffles to do
if num_shuffles:
# rinse and repeat
mixed = humanoid_shuffle(mixed, num_shuffles)

# finally return fully shuffled list
return mixed


C

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

void shuffle(int *shuffle_array, int length)
{
int const MAX_STREAK = 10;
int end_range;
int mixed[length];
int m, f, l;
int streak;
int *current_ptr;

srand(time(NULL));
current_ptr = (rand() % 2) ? &f : &l;
end_range = (int)(length / 2 + rand() % (int)(.1 * length));

for(m = 0, f = 0, l = (end_range + 1), streak = 0; m < length && l < length && f < end_range + 1; m++, *current_ptr += 1)
{
float remaining = 1 - m / (float)length;
float test = rand() / (float)RAND_MAX;

if (test < remaining || streak > MAX_STREAK)
{
current_ptr = (current_ptr == &f ? &l : &f);
streak = 0;
}

mixed[m] = shuffle_array[*current_ptr];
printf("Dropped from %p --> %d \n", current_ptr, mixed[m]);
streak += 1;
}

// change the pointer to the one that didn't cause the for to exit
current_ptr = (current_ptr == &f ? &l : &f);

printf("remaing items in %p\n", current_ptr);
while(m < length)
{
mixed[m] = shuffle_array[*current_ptr];
printf("Dropped from %p --> %d \n", current_ptr, mixed[m]);
m++;
*current_ptr += 1;
}

memcpy( shuffle_array, mixed, length * sizeof( int ) );

}

int main(void)
{
int i;
int array[52] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51 };
int length = sizeof(array) / sizeof(int);

printf("\nShuffling...\n\n");
shuffle( array, length );

// for(i = 0; i < length; i++)
// {
//  printf("%d\n", array[i]);
// }

return 0;

}


## Code Review

Be careful of identifiers in all caps.
It is traditional to reserve all caps for macros (which can cause problems when you get clashes as macros do not respect scope).

int const MAX_STREAK = 10;


It is usually best to initialize variables as you declare them

int end_range;
int mixed[length];


Try not to declare multiple variables on a single line (Every coding standard I have seen will hit you on this). There are also some corner cases with pointers that are not so obvious thus best to just avoid them.

int m, f, l;


Initialization of the random number generator should be done once in the application. So best to do it just after main() has been entered.

srand(time(NULL));


This is an excessive number of identifiers you are initializing in the for(;;).

for(m = 0, f = 0, l = (end_range + 1), streak = 0; m < length && l < length && f < end_range + 1; m++, *current_ptr += 1)


To be blunt I have a hard time following what you are trying to do. There should definitely be more comments explaining what you are trying to do at each step (the only way I managed to decode it was reading the python version).

One technique you can use to make things easier is to create structures to hold groups of related information (You should have mimicked the python array).

typedef struct Array
{
int*   data;
int    size;
// Other structures you want
} Array;


Unfortunately unlike python ther are no built-in us-full generic container types (That's why C++ is very popular (or one of the reasons)). As C++ has a std::vector (a dynamically sized array with push/pop).

In fact I would consider C++ a better bet for a python programmer as it gives you some useful built-in types and allows you to do OO programming like python.

Also as you mention in the comments (to the other questions) the downside (or the beauty depending on how you look at it) is the requirement for memory management. C is very basic and you must do it all manually. If you return dynamic allocated memory from a C function you must be very careful to document the requires of the user on what to do with it (this is solved in C++ where memory management is practically automatic).

Before I do a C review I just want to do a literal translation of your python so you can compare it. Personally I think you can make your C look identical to your python (a small amount of extra work required for memory management and the array like container but otherwise the same).

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

typedef struct Cards
{
int*    cards;
int     size;
} Cards;

Cards shuffle_n(Cards deck, int num_shuffles)
{
/* how many times items can be pulled from the same list consecutively */
int const MAX_Streak = 10;

/* divide list roughly in half */
int num_items   = deck.size;
int end_range   = num_items / 2 + rand() % (int)(.1 * num_items);

Cards   split_lists[2]      = { {deck.cards, end_range},                          /* # list up to 0 - end_range */
{deck.cards + end_range, deck.size - end_range}   /* list after end_range - len(items) */
};
int     current_list_index  = rand() % 2;

int*    mixedData           = (int*)malloc(sizeof(int) * deck.size);
Cards   mixed               = {mixedData, 0 };
int     streak              = 0;

/* # while both lists still contain items */
while((split_lists[0].size != 0) && (split_lists[1].size != 0))
{
/* calc the percentage of remaining total items */
int remaining = (1 - ((float)mixed.size) / num_items);
/* if we happen to generate a random value less than the remaining percentage
* which will be continually be decreasing (along with the probability)
* or
* if MAX_Streak is exceeded
*/
if ((rand() < remaining) || (streak > MAX_Streak))
{
/* switch which list is being used to pull items from */
current_list_index = !current_list_index;
/* reset streak counter */
streak = 0;
}

/* pop the selected list onto the new (shuffled) list */
mixed.cards[mixed.size++] = split_lists[current_list_index].cards[--split_lists[current_list_index].size];
/* increment streak of how many consecutive times a list has remained selected */
streak += 1;
}

/* add any remaining items */
memcpy(&mixed.cards[mixed.size], &split_lists[0].cards, split_lists[0].size * sizeof(int)); mixed.size += split_lists[0].size;
memcpy(&mixed.cards[mixed.size], &split_lists[1].cards, split_lists[1].size * sizeof(int)); mixed.size += split_lists[1].size;

num_shuffles -= 1;
/* if we still have shuffles to do */
if (num_shuffles > 0)
{   /* rinse and repeat */
Cards result = shuffle_n(mixed, num_shuffles);
free(mixedData);

mixed   = result;
}

/* # finally return fully shuffled list */
return mixed;
}
Cards shuffle(Cards deck) {return shuffle_n(deck, 6);}

int main()
{
srand(time(NULL));
int i;
int array[52] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51 };

Cards   deck = {array, sizeof(array)/sizeof(array[0])};

printf("\nShuffling...\n\n");
Cards   shuffled = shuffle( deck );

for(i = 0; i < shuffled.size; i++)
{
printf("%d\n", shuffled.cards[i]);
}
free(shuffled.cards);
}

• very cool. definitely some stuff I don't understand yet... what about comparing the two c approaches? also is there anything I'm doing in my version that is questionable from a convention standpoint? – jondavidjohn Jan 22 '12 at 15:37
• @jondavidjohn: Yes I will do a code review today (going skiing). I just wanted to show that you can write the C very much like the python. My point being once you know a language well you can easily translate to it. – Martin York Jan 22 '12 at 18:12
• Thanks, maybe a few considerations to address when you give it another look, with your version I'd be concerned (as a utility function) the user not knowing to free the result.cards, and while I did take joy in the cleverness of my solution, it clearly by a read the morning after, seems overly terse and complicated. Enjoy your skiing! – jondavidjohn Jan 22 '12 at 19:04