Prevent Duplicate Inputs to Array

[pdunc88]

Hi guys, first post so be nice :S

I've been working on a software project (wordsearch generator) for one of my classes at university and I'm stumped on this section. I'm supplied with an array filled with x strings, the integer value of x (for the size of the array) and an integer specifying how many strings to be used.

The first task is to randomly select the specified amount of strings. Here is the code I have so far;

#include <ctime>
#include <cstdlib>
#include <string>
#include <iostream>

using namespace std;

int main() 

{
	//*************Inputs from other section*****************//

	string wordbank[]={"yes", "no", "hello", "goodbye", "france", "google", "diagram", "strath", "x", "ten", "eleven", "twelve", "thirteen", "fourteen", "fifteen", "sixteen", "seventeen", "getting", "close", "kabam"};
	int no_of_words = 10;
	int words_in_bank = 20;

	//*************Inputs from other section*****************//

	int array_element; //defines the element of wordbank[] array to be accessed
	int check_array[]={-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1}; //array used to check whether duplicates are created
	int t; //looping variable
	int chosen_words; //indicates the number of words chosen
	int flag; //variable used to indicate duplicate words

	chosen_words = 0; //initialise variable to zero

	while(chosen_words < no_of_words) //loop will terminate once the correct number of words are selected
	{
	
		array_element = rand() % words_in_bank;  //and set this to array_element

		for(t=0; t<20; t++) //loop through each element of the array
		{
			flag = 0;

			if (check_array[t] == array_element)  // if match is found
			{
				flag = 1;
				break;
			}
			else
			{
				if (check_array[t] == -1)
				{
					check_array[t] = array_element;
				}
			}
		
		}

		if (flag != 1)
		{
			cout << wordbank[array_element] << endl;
			chosen_words++;
		}
	}
	return 0;
}

I've tried to be specific with my comments although if you don't understand my logic (?) feel free to ask!! It's giving me the following output;

no
strath
fifteen
yes
ten
france
close
close
hello
france
Press any key...

I'm guessing it's something within the if statement which is allowing the same index "array_element" pass. I've tried everything I can, any and all help appreciated :)

Pete

[tux4life]

> So if I didn't understand you the wrong way each word may only appear one time ?
>>In this case the unique STL-algorithm might be helpful :)

[ArkM]

Alas, it's an absolutely incorrect algorithm. Look at your select condition:

if (check_array[t] == array_element) // if match is found
{ 
    flag = 1;
    break;
}

In other words you make selection if and only if you have selected the element already!
Quite the contrary, make selection if and only if the element was not selected yet:

if (check_array[array_element] == -1) {
    check_array[array_element] = array_element]; // or what else but -1
    cout << ...
    chosen_words++;
}

No need in the inner loop and flag var at all.
Apropos, better use bool array with all false elements initially.

[pdunc88]

Thanks for both of your replies!!

@tux4life - the STL-algorithm you suggest seems to remove duplicate data from an array, I was looking to prevent it from being assigned in the first place.

@ArkM - I implemented pretty much identical code to what you suggested. My while loop now looks like this;

while(chosen_words < no_of_words) //loop will terminate once the correct number of words are selected
	{
	
		array_element = rand() % words_in_bank;  //and set this to array_element

		for(t=0; t < words_in_bank; t++) //loop through each element of the array
		{
			if (check_array[array_element] == -1)
			{
				check_array[array_element] = array_element;
				cout << wordbank[array_element] << endl;    
				chosen_words++;
			}
		}
	}

This is working now :) ..almost! It generates a random order without duplicating any entries, although the order is the same everytime I run the program.

I tried adding

srand(time(NULL));

below the ...rand()... line although this results in just a blinking underscore as my output.. I understand random number generation is fairly crude in C++ but a different set of numbers each time will be required. Any ideas? :)

Peter

[Nick Evan]

How to use rand()

[pdunc88]

Thank you, problem solved :) here is my code for anyone interested. I didn't use the 'best' generation technique because it was taking around 1:40 to complete, the way I've done it gives sufficiently random data and takes around :40 for all 20 words.

#include <ctime>
#include <cstdlib>
#include <string>
#include <iostream>

using namespace std;

unsigned time_seed()
{
time_t now = time ( 0 );
unsigned char *p = (unsigned char *)&now;
unsigned seed = 0;
size_t i;
 
for ( i = 0; i < sizeof now; i++ )
seed = seed * ( UCHAR_MAX + 2U ) + p[i];

return seed;
}

int main() 

{
	//*************Inputs from other section*****************//

	string wordbank[]={"yes", "no", "hello", "goodbye", "france", "google", "diagram", "strath", "x", "ten", "eleven", "twelve", "thirteen", "fourteen", "fifteen", "sixteen", "seventeen", "getting", "close", "kabam"};
	int no_of_words = 20;
	int words_in_bank = 20;

	//*************Inputs from other section*****************//

	int array_element; //defines the element of wordbank[] array to be accessed
	bool check_array[20]; //array used to check whether duplicates are created
	int i,t; //looping variable
	int chosen_words; //indicates the number of words chosen
	int orientation;
	
	for(i=0; i < 20; i++) //initialise all elements of check_array to false
	{
		check_array[i] = false;
	}

	chosen_words = 0; //initialise variable to zero

	while(chosen_words < no_of_words) //loop will terminate once the correct number of words are selected
	{
		srand ( time_seed() );
		array_element = rand() % words_in_bank;  //and set this to array_element
		
		for(t=0; t < words_in_bank; t++) //loop through each element of the array
		{
			if (check_array[array_element] == false) //if the array_element position is false..
			{
				check_array[array_element] = true; // ..assign it with a true value
				orientation = rand() % 4;
				cout << wordbank[array_element] << " - " << orientation << endl; //display the corresponding word and it's orientation
				chosen_words++; //increment the chosen_words variable
			}
		}
	}
	
	return 0;
}

The 'orientation' variable defines the direction of the word and whether or not the characters are inverted. The original problem is solved so I'll mark the thread.

Thanks again guys :twisted:

Peter