macOS Getting duplicate numbers.

[larswik]

In Short, I am trying to fill the array list[11] with 10 random generated numbers from 0-9 while not duplicating any numbers in that array. If it finds a duplicate number it gets a new random number and starts the check all over again. I filled the array with the number 20 as a place holder to start off with.

When I step through the code with the debugger with break points it executes like I expect and all duplicate numbers are caught and replaced. But as I run the program normally 'build and go' it adds duplicate numbers in every now and then. This is part of a bigger program I am making to deal out cards and to check if it has already delt a card depending on it's number.

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

int main (int argc, const char * argv[]) {

	srand(clock());
	
	int list[11] = {20,20,20,20,20,20,20,20,20,20,'\0'};
	int randNumberRoll, i, count;
	
	count = 0;
		
	do{
	randNumberRoll = rand() %10; // creates a random number 0-9
	
	for (i=0; i < 9; i++) //finds the next space and increments count
	{ 
		if (list[count] != 20)
			count++;
	}
	
	do{
		for (i = 0; i <= count; i++) // Checks to see if the rand number is already in the list[]
		{
			if (randNumberRoll != list[i])
		{
			;
		}
		else{     // if it finds a duplicate number it resets i to 0 and rolls a new rand number.
			i = 0;
			randNumberRoll = rand() %10;
		}
			}
	}while(i < count);
	
	list[count] = randNumberRoll;  // adds the rand number to the next spot in list[]
			
	printf("count is %d and the list number is %d\n", count, list[count]); // prints the results
	
	} while(count < 9); // keeps going till the list array is full.
	
	return 0;
}

I know it is not the best way of zero terminating an int array but I don't think that is the problem.
-Lars

 

[balamw]

In Short, I am trying to fill the array list[11] with 10 random generated numbers from 0-9 while not duplicating any numbers in that array.

There are a finite number of orders that the 10 digits can be in. Usually an easier way to deal with this problem is to pick a random number that represents the order rather than looking for duplicates. (EDIT: this works well up to ~10, but I probably wouldn't do this for 52 or so).

Or another way to deal with it is to pick the first digit from 0-9, then the next one from 0-8 (not including the first number picked) then 0-7 not including the first two numbers and so forth...

Think of it as shuffling a deck of cards. EDIT: After you've picked one card for the first slot, you only have N-1 cards to choose from, etc...

B

 

[chown33]

Another way to do this is to put sequential numbers into the array, then randomly reorder the array.

Sequential numbers guarantees that each number is in the array exactly once.

The random reordering then rearranges the order of the numbers, but since it doesn't add or remove anything, the array still has exactly one of each number.

A simple random shuffle is to iterate through the array, generating a random number at each step. The random number is then used as the index of another array element to exchange the current element with. Repeat several times.

There are other (often better) shuffling algorithms (befriend google). This is just a simple and reasonably effective one.


This also illustrates a powerful and useful engineering principle: Decomposition. Break the problem down into separately solvable sub-components, solve each one separately, then recombine.

The exactly-once part was solved separately from the random-ordering part. Exactly-once is trivial: each array element is set to its index.

After we have the first part solved, all we we have to do is randomly reorder what we have without adding or removing anything. If we did add or remove anything, then we'd be breaking the first solution (exactly-once). So we completely avoid doing that by only exchanging position of numbers in the array, and never adding, removing, altering, or duplicating any value.

 

[ulbador]

Sequential numbers guarantees that each number is in the array exactly once.

The random reordering then rearranges the order of the numbers, but since it doesn't add or remove anything, the array still has exactly one of each number.

+1 to this. You already know all the data that will be in the array. There is no purpose in "generating" it at runtime other than wasting time. If the array is set in stone to be 1-10 or whatever, just build it when you write the program and randomly reorder it.

Think how many times you could potentially go around loop searching for the number 7 to come out randomly once you've "filled" in all the other slots of 1-10. Potentially forever. At the very least you would probably be going around the loop 100s or 1000s of times just to pull out one or two missing numbers. One time you ran the program it might finish in less than a second, another time it could take minutes depending on how your RNG is feeling that day.

Now if the upper or lower bounds could change, that would be a different story.

 

[balamw]

http://en.wikipedia.org/wiki/Shuffling#Shuffling_algorithms

Yeah an easy way to keep track of the numbers you have available is to start with the sequential array, pick a number from 0-9, swap that number into the last position, then pick a number from 0-8, swap that element into the next to last position, etc... This is what Wikipedia refers to as the Knuth/Fisher-Yates shuffle. You only have to do 10 swaps in this case.

I was using the first approach in a MATLAB problem where it had to iterate though all the various permutations and know that I had already analyzed a given order.

B

 

[Doctor Q]

Yeah an easy way to keep track of the numbers you have available is to start with the sequential array, pick a number from 0-9, swap that number into the last position, then pick a number from 0-8, swap that element into the next to last position, etc... This is what Wikipedia refers to as the Knuth/Fisher-Yates shuffle. You only have to do 10 swaps in this case.

I think you get the same result as with my version, which swaps each element with a random one.

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

int main (int argc, const char * argv[]) {

	int list[10] = {0,1,2,3,4,5,6,7,8,9};
	int randNumberRoll, i, temp;
	
	srand(clock());
	
	for (i=0; i <= 9; i++) //swap i'th element with random one
	{ 
	randNumberRoll = rand() %10; // creates a random number 0-9
	temp = list[randNumberRoll];
	list[randNumberRoll] = list[i];
	list[i] = temp;
	}
	
	for (i=0; i <= 9; i++)
	printf("list[%d] is %d\n", i, list[i]); // prints the results
	
	return 0;
}

 

[balamw]

I think you get the same result as with my version, which swaps each element with a random one.

(I was trying to reinforce the combinatorial math concepts behind it, not just provide a black box for the random shuffle )

B

 

[vaxt]

I don't know where to begin on this....

(1) if you're making a Mac OS X or iOS application, you should be taking advantage of the NS Objects and writing your application in Objective C. The only time someone writes an application in C is when (a) They're forced to, as part of some sort of schooling or (b) they are an "Old Dog" that refuses to learn "New Tricks"

Null terminated arrays, pre populated with the value 20? I'm pretty certain you only need null terminated arrays for Strings, but aside from that, I don't see why you wouldn't want to use dynamic memory by implementing Objects like linked lists or hash maps.

(2) if you're trying to see if a value already exists in a list, iterating through that set is a terrible in terms of run time O(n), if you use some sort of Hash Set, you can determine in O(1) if that value is in the set. This is far more efficient.

On this topic, the BEST case scenario for this code executing is O(n^3), which is really really bad. You can probably solve this problem in O(n).

(3) Your indenting and formatting is all messed up and, as a result, your code nearly impossible to read. You have a line that is only a semi-colon. And you have nested loops that have the same indentation level. If you want to produce maintainable code, or you want people to help you with your code, you should probably at least make the code readable first.


(4) if you insist on using arrays and C, and random numbers, something like this (which I have not tested or even compiled) may work, which runs in O(n) time:

int main (int argc, const char * argv[]) {
    int deck[10] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
    shuffle(deck, 10);
}

void shuffle(int[] deck, int size) {
    srand(clock());	
    int holder = 0;
    for (int i = 0; i < size; i++) {
        int switchIndex = rand() %10;    
        holder = deck[i];
        deck[i] = deck[switchIndex];
        deck[switchIndex] = holder[i];
    }
}

EDIT: Looks like someone came up with the same solution as me, while I was typing this up.

 

[dmi]

I think you get the same result as with my version, which swaps each element with a random one.

	for (i=0; i <= 9; i++) //swap i'th element with random one
	{ 
	randNumberRoll = rand() %10; // creates a random number 0-9
	temp = list[randNumberRoll];
	list[randNumberRoll] = list[i];
	list[i] = temp;
	}

No, that procedure produces some sequences with greater probability than other sequences, whereas the Fisher–Yates shuffle produces all sequences with equal probability.

 

[Doctor Q]

(I was trying to reinforce the combinatorial math concepts behind it, not just provide a black box for the random shuffle )

B

I agree that for that purpose you can't do much better than quote Knuth!

 

[chown33]

I don't know where to begin on this....

(1) if you're making a Mac OS X or iOS application, you should be taking advantage of the NS Objects and writing your application in Objective C. The only time someone writes an application in C is when (a) They're forced to, as part of some sort of schooling or (b) they are an "Old Dog" that refuses to learn "New Tricks"

In this case, the answer is (a); the OP is learning C. It wasn't mentioned in this post, but all his recent posts to this forum are in this vein.

 

[balamw]

In this case, the answer is (a); the OP is learning C.

Though on his own and not part of coursework. When he comes here for Turbo Pascal help we know it's coursework.

B

 

[gnasher729]

I know it is not the best way of zero terminating an int array but I don't think that is the problem.
-Lars

1. The whole business of filling the array with values of 20 is nonsense. A simple loop

for (count = 0; count < 10; ++count) { ... }

will achieve exaxctly the same thing, just much simpler.

2. The loop

do { ... } while (i < count);

is nonsense, because when i < count is evaluated, i will always be equal to count + 1.

3. The loop

for (i = 0; i <= count; i++)

is wrong. It should only go up to i < count, because when i == count you compare the random number with a value of 20.

4. When you reset i to 0, that's inside the for loop. So immediately after this, i will be increased to 1. So the next random number that you generate is _not_ compared to the first array element. I'll bet that your duplicates always match the first number in the array.


A much simpler structure for this would be:

for (count = 0; count < 10; ) {
   generate random number; 
   check if random number equals any of first (count) numbers
   if it doesn't match store it to list [count++]
}

(1) if you're making a Mac OS X or iOS application, you should be taking advantage of the NS Objects and writing your application in Objective C. The only time someone writes an application in C is when (a) They're forced to, as part of some sort of schooling or (b) they are an "Old Dog" that refuses to learn "New Tricks"

Well, in this case straightforward C code that doesn't go round the houses like the OP beats Objective-C code in simplicity, readability, and speed. You don't need hash tables for speed when you have 10 array elements. You don't need hash tables anyway when you have a small number of possible values - there is a much simpler and faster way to check for duplicates.

And last, your code doesn't produce a random permutation. I'd say the chances that the first element in the deck equals 9 are about 0.2 * 0.9^9. A correct version is:

void shuffle(int deck [], int size) {
    srand(clock());	
    int holder = 0;
    for (int i = size; i > 1; --i) {
        int switchIndex = rand() % i;    
        holder = deck[i - 1];
        deck[i - 1] = deck[switchIndex];
        deck[switchIndex] = holder;
    }
}

 

[larswik]

Wow, I step out for dinner and come back to 14 posts. Thank you ALL for your continuing support as I work though C. I was unsure if I could zero terminate an array before there was anything in it, so I populated the array with the number 20 followed by the incorrect '\0' for an int array to be safe

Here is the main part of my program, for a basic Black Jack. I do have 2 char arrays set up and reshuffle the deck to the the mixDeck char array. When it selects a number from the array 'cards' it places it in the new mixDeck array starting at 0 working to 52. After it places, for example, card[4] into mixDeck it then changes the char value in card[4] to '-'. If the random generator comes up with that number again it will see that char[4] value is '-' and guess a new number. When I run this it seems to work fine with no errors.

This sounds like the reordering you guys were talking about.

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

#define kDeck 52
int drawOneCard(int drawCard);


int main (int argc, const char * argv[]) {

	srand(clock());
	
	char mixDeck[kDeck];
	
	char cards[kDeck] = {'2','2','2','2',
		'3','3','3','3','4','4','4','4','5','5','5','5','6','6',
	'6','6','7','7','7','7','8','8','8','8','9','9','9','9','T',
	'T','T','T','J','J','J','J','Q','Q','Q','Q','K','K','K','K',
	'A','A','A','A'};
	
	int i,randNumberRoll,drawCard,pCard1,pCard2,nextCard;
	
	for(i=0 ; i< 52 ; i++) // Mixes the deck to mixDeck array
	{
		
		do {
			randNumberRoll = rand() %52;
		} while (cards[randNumberRoll] =='-');
		
		mixDeck[i] = cards[randNumberRoll];
		cards[randNumberRoll] = '-';
	}
	mixDeck[52] = '\0'; //adds zero terminator to string.
	
	printf("the mix deck this: %s\n",mixDeck); // TO REMOVE LATER - ITS A TEST.
	
	
	pCard1 = drawOneCard(drawCard);
	
	do { // checks to make sure you don;t get the same random number
		pCard2 = drawOneCard(drawCard);
	}while (pCard1 == pCard2);
	
	printf("The cards are %c and %c",mixDeck[pCard1], mixDeck[pCard2]);

		

    return 0;
}

int drawOneCard(int drawCard)
{

	
	drawCard = rand() %52;
	
	return drawCard;
	
}

The first post I was trying to work out a way to store the numbers of cards that the dealer has dealt out to avoid duplication. The problem I had was there were four '2', four '3' and so on in a deck of cards. So I could not create a char array (as far as I could see) to store the chars. So I decided it was better to keep track of the RandomNumbers to be safe. This was the crazy loop I created in my first post.

Thanks again so much, and Ican't wait to start my Turbo Pascal class

-Lars

 

[ulbador]

I don't know where to begin on this....

The only time someone writes an application in C is when (a) They're forced to, as part of some sort of schooling or (b) they are an "Old Dog" that refuses to learn "New Tricks"

Pretty much fail.

As a professional developer that is out of school, and not an "Old Dog", you are wrong.

Where I work, we use a combination of Java and PHP. I recently had to "relearn" how to write a program in C in the form of a daemon.

Connecting to a database, using shared memory; these are all things you take a little for granted until you have to do it on your own, and with memory management.

Bottom line. I wrote a pretty simple daemon in Java. The same daemon, in C, takes 1/1000 of the resources. While Java and C are definitely not directly comparable, there are still reasons to use other languages.

 

[dmi]

#define kDeck 52
char mixDeck[kDeck];
mixDeck[52] = '\0'; //adds zero terminator to string.

[/CODE]

This is writing beyond the end of the array, which can cause undefined behavior.

 

[chown33]

Here is the main part of my program, for a basic Black Jack. I do have 2 char arrays set up and reshuffle the deck to the the mixDeck char array. When it selects a number from the array 'cards' it places it in the new mixDeck array starting at 0 working to 52. After it places, for example, card[4] into mixDeck it then changes the char value in card[4] to '-'. If the random generator comes up with that number again it will see that char[4] value is '-' and guess a new number. When I run this it seems to work fine with no errors.

I think you should work on the basic design a lot more.

The description you give amounts to this:
1. Shuffle the deck (randomly reorder it).
2. Pick a random position in the shuffled deck and deal that card.
3. Never deal any card more than once.

The first two steps are not how the game is dealt. Worse, it's redundant. If you've shuffled the deck, then it's already in random order. So if you simply step through sequentially (mixedDeck[0], mixedDeck[1], etc.) then the cards will be randomly ordered. That was the point of shuffling the deck. It also happens to be how the game is played: cards are dealt from the top of the shuffled deck.

Since you're simply moving sequentially through a shuffled deck, all you have to do is keep track of your position in the shuffled deck. You don't have to mark dealt cards as '-', or anything else. Just track your position, and when you run out of cards (i.e. the index reaches the end of the deck), you reshuffle the deck and start over at 0 again.

If you actually sit down with some cards and step through the actions in simple detail, you will see how simple it is. Take notes. Seriously. Writing it down will force you to notice exactly what's happening. Next, step through your code and match what it does with what you'd do with a real deck of cards, including all the "avoid dealing the same card twice" stuff. It's much more complex.

Right now, I see more problems with how you're analyzing problems and designing code, rather than the actual coding. You're not coding a faithful representation of how things really work. I think that's because you're focusing too much on coding it in C and not enough on basic understanding, modeling, and design. You create solutions to problems that don't exist (such as randomly choosing a card from an already randomized deck, and thus needing to track which card was randomly chosen). This substantially increases the complexity, even making it so complex it's wrong, or so convoluted no one can understand what it's trying to do.

 

[dmi]

	for(i=0 ; i< 52 ; i++) // Mixes the deck to mixDeck array
	{
		
		do {
			randNumberRoll = rand() %52;
		} while (cards[randNumberRoll] =='-');
		
		mixDeck[i] = cards[randNumberRoll];
		cards[randNumberRoll] = '-';
	}

Although this works, and although an expected run time of O(kDeck*log(kDeck)) is not too excessive,
It may be useful in principle to be aware how this can be done in O(kDeck):

	for(i=0 ; i< kDeck ; i++) // Mixes the deck to mixDeck array
	{
             randNumberRoll = rand() % (kDeck-i);
             mixDeck[i] = cards[randNumberRoll];
             cards[randNumberRoll] = cards[kDeck-i-1];
             //cards[randNumberRoll] = '-'; is now unnecessary
        }

(which happens to make it equivalent to a Fisher–Yates shuffle)

 

[Doctor Q]

Here is the main part of my program, for a basic Black Jack.

You've reminded me of a funny experience I had. In a college programming course our class was given a choice of problems to solve. One of them was to write a blackjack-player program which would be linked with a blackjack-dealer program provided by the instructor to see how well our players did. I picked that assignment because it sounded both challenging and interesting. It turned out that I was the only student to pick that choice of assignment, and the day before the due date the instructor asked me to write the dealer program for him since nobody else was submitting a player program.

My player program counted cards and did the probability analysis that we humans only wish we could do in Las Vegas, so I was expecting it to make a little pseudo-money. But after I quickly wrote a dealer program and tried them together, my player program lost big-time!

The instructor figured out the problem: my dealer had a bug in the card-shuffling routine and was producing impossible decks of cards! It even dealt itself a 5th ace in one game! However, the instructor gave me an A on the project because he was grading only the player program. Whew!

 

[larswik]

HAHA- Sometimes I have to laugh at myself.

Chown33- I think you hit the nail on the head with me. You are right on all counts. I asked the question a little while ago about finding another book to teach me how to correctly code. So far in my book it is teaching me how to code and not proper techniques or tackeling projects. The mixDeck is already mixed, why use a random num generator to pull cards, HAHA, that is a big DUH on my part Good advice on looking how things are done in the real world!

DMI - Thanks for that code. I will look at it and when I understand it completely I will include it. It looks like you are reducing the rand number by 1 each time through the for loop and also reducing the card array as well. This line I need to look at a little more cards[randNumberRoll] = cards[kDeck-i-1];

Doctor Q- nice story and A.

Thanks guys!

-Lars

 

[larswik]

DMI - I tried your code in another project first and I must be doing something wrong. I have a couple printf before and after to test what each array looks like.

Looks like you are generating a rand num the size of kDeck - i whcih is incremented 1 time through each loop reducing the rand number each time.
Then you assign the card[randNumberRoll] to the next mixDeck. The last line is a bit confusing, can you explain it more cards[randNumberRoll] = cards[kDeck-i-1]; It is doing something to it's self which I don't get?

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

#define kDeck 53


int main()
{
	
	int i,randNumberRoll;
	char mixDeck[kDeck];
	char cards[kDeck] = {'2','2','2','2',
		'3','3','3','3','4','4','4','4','5','5','5','5','6','6',
		'6','6','7','7','7','7','8','8','8','8','9','9','9','9','T',
		'T','T','T','J','J','J','J','Q','Q','Q','Q','K','K','K','K',
		'A','A','A','A'};
	
	srand(clock());
	
	printf("mixDeck array before is: %s\n", mixDeck);
	printf("cards array before is: %s\n\n", cards);
	
	for(i=0 ; i< kDeck ; i++) // Mixes the deck to mixDeck array
	{
		randNumberRoll = rand() % (kDeck-i);
		mixDeck[i] = cards[randNumberRoll];
		cards[randNumberRoll] = cards[kDeck-i-1];
		
	}
	mixDeck[53] = '\0';
	
	printf("mixDeck array after is: %s\n", mixDeck);
	printf("cards array after is: %s", cards);
	
	
	
	
	return 0;
}

-Lars

 

[dmi]

A program that runs less efficiently than it could, or which is biased in favor of some sequences over others, or the stylistic (and maintainability) problem of using kDeck in some places and 52 in others, are not as serious as the problem of writing past the end of an array.

The C standard says that an expression pointing one past the last element of an array shall not be accessed.
Violating a "shall not" requirement means that the behavior is undefined and the standard imposes no requirements on what the program might do.

 

[dmi]

#define kDeck 53
	char mixDeck[kDeck];
	char cards[kDeck] = {'2','2','2','2',
		'3','3','3','3','4','4','4','4','5','5','5','5','6','6',
		'6','6','7','7','7','7','8','8','8','8','9','9','9','9','T',
		'T','T','T','J','J','J','J','Q','Q','Q','Q','K','K','K','K',
		'A','A','A','A'};

	printf("mixDeck array before is: %s\n", mixDeck);
	printf("cards array before is: %s\n\n", cards);
	
	for(i=0 ; i< kDeck ; i++) // Mixes the deck to mixDeck array
	{
		randNumberRoll = rand() % (kDeck-i);
		mixDeck[i] = cards[randNumberRoll];
		cards[randNumberRoll] = cards[kDeck-i-1];
		
	}
	mixDeck[53] = '\0';
	
	printf("mixDeck array after is: %s\n", mixDeck);
	printf("cards array after is: %s", cards);

This illustrates some of the problems with mixing kDeck in some places and 52 in others. It makes writing beyond the end of an array harder to notice,
And changing one thing affects others inconsistently.
There is also a problem that strings printed with printf %s need to be null terminated.

More maintainable might be

        int i,randNumberRoll;
        char cards[] = {
                '2','2','2','2',
                '3','3','3','3',
                '4','4','4','4',
                '5','5','5','5',
                '6','6','6','6',
                '7','7','7','7',
                '8','8','8','8',
                '9','9','9','9',
                'T','T','T','T',
                'J','J','J','J',
                'Q','Q','Q','Q',
                'K','K','K','K',
                'A','A','A','A',
                '\0'};
#define kDeck (sizeof(cards)/sizeof(cards[0])-1)
        char mixDeck[kDeck+1]={'\0'};

        srand(clock());

        printf("mixDeck array before is: %s\n", mixDeck);
        printf("cards array before is: %s\n\n", cards);

        for(i=0 ; i< kDeck ; i++) // Mixes the deck to mixDeck array
        {
                randNumberRoll = rand() % (kDeck-i);
                mixDeck[i] = cards[randNumberRoll];
                cards[randNumberRoll] = cards[kDeck-i-1];
        }
        mixDeck[kDeck] = '\0';

        printf("mixDeck array after is: %s\n", mixDeck);
        printf("cards array after is: %s\n", cards);

With no fixed magic constants, no other modifications to the program are necessary if you change number of elements in cards.

(modifying the program so that mixDeck array is unnecessary is left as an exercise for the reader)

 

[Sydde]

Personally, I like the idea of using a NSMutableIndexSet to represent the deck. You fill it with indexes ( -removeAllIndexes: followed by -addIndexesInRange:, where the range would be 0 to 51, or whatever is convenient), then randomly generate the cards as you go. Use the method -indexLessThanOrEqualToIndex: to obtain a card value, falling back on -indexGreaterThanIndex: if that fails (returns the NSNotFound value). After you have the number of the card, use -removeIndex: to "draw" the card out of the deck. Note also that NSIndexSet has a -count function to tell you how many cards are left in the deck.

 

[lloyddean]

But the original poster is in the process of learning 'C' not 'ObjC' and Cocoa.