Join 132,366 C++ Programmers for FREE! Get instant access to thousands of C++ experts, tutorials, code snippets, and more! There are 1,289 people online right now. Registration is fast and FREE... Join Now!
I have a program that generate Plate number with text file and it is in random order. How can I make sure that the output in the text file will not show duplicates records... Please help.. See my codes below:
CODE
# include <stdio.h> # include <fcntl.h> # include <stdlib.h>
I suppose that my program version was just too complicated (it works great though). SO we thought about a few ways that you can ensure that you don't repeat numbers.
First off you can store all the numbers you have generated. However even using just 1 bit to represent each number you end up with over 2Mb of data just to keep track of numbers.
So my brother made an interesting suggestion. If you create 3 arrays of letters (arranged randomly), and 3 arrays of digits (again arranged randomly), and then randomly arranged them. you could simply "count" but since you have arranged the numbers randomly rather than getting AAA000 AAA001 AAA002, you get something like ARF451, ARF459, ARF453...
So we can improve this idea by making the array of number 1000 entries long ... now we can generate numbers like ARF456, ARF345, ARF111, ARF104... the adjacent plates still have adjacent letters...
but I am sure we can come up with a way to randomize these too... by randomly arranging the digits in the arrays, we can hide the patterns used to choose the numbers.
boy.... we came up with another interesting idea.... but it is probably more complicated to implement than my LCG method.
Basically we want to make a way of counting. Since we have arranged the letters and digits randomly in our arrays we just need some way of choosing numbers in such a way that we do not repeat.
Well one way of doing this is to walk a tree so that you never visit the same node twice. This is a common problem in computer science and it does not take a lot of work...
well my plane is boarding now... generally this idea would be rather complicated. NEAT... but complicated.
First off you can store all the numbers you have generated. However even using just 1 bit to represent each number you end up with over 2Mb of data just to keep track of numbers.
Good thing I have more memory than that.
perl
#!/usr/local/bin/perl
use strict; use warnings;
# Three base-26 digits (otherwise known as letters of the alphabet). sub BASE26_MAX { 26 ** 3 } # Three base-10 digits. sub BASE10_MAX { 10 ** 3 }
# Take a number that is a 3-digit base-10 number, with a 3-digit base-26 number tacked on, and # print it in a human readable fashion. sub licEncToStr { my $n = shift; # Input argument. my $v = $n % 1000; # Get 3 trailing digits. my $w = int($n / 1000); # Get 3 alpha characters.
It worked, but was slow enough to make your eyes bleed.
For the next version I shortcut the search by using the last three digits as a lookup index. The alpha lookup part was not optimized in any way. The 100000 amount ran in less than five seconds, the 1M version less than a minute. After twenty minutes I gave up on the 17M version, it had produced 4739072 entries at that point. There are two functional bottlenecks to doing this in memory, one is obviously the lookup, the other is the malloc. If I wanted a faster version, I'd allocate a 26 position array of pointers to a 26 position array, etc. While not the most memory efficient, I believe the speed would be reasonably close to optimal.
I don't want to offer the whole code, hoping the poster will come to their own solution. Here's a chunk from what I did:
So I don't like the idea of using some data structure to keep track of what values we have been at. The walking the tree is really overly complicated (I don't even want to program it). So how could we keep track of what numbers we have visited without saving it?
We can use a pattern. If we have a pattern that we know does not repeat (at least until it has reached all the values) then we don't have to worry about keeping track of where we have been! we just need to know where we are!
So we need a pattern that will save state... Well I don't know if CS majors are required to take Number Theory or Abstract Algrbra but we can do this using the formula:
N = (N + S) % M;
Where S and M are relatively prime. So imagine that M = 10, and S = 3:
0, 3, 6, 9, 2, 5, 8, 1, 4, 7
So for my solution I imagined the plates as coordinates (A, D) where A was in the range of 0 to 17575 and D is in the range 0 to 999.
So I created 6 arrays, 3 for letters and 3 for digits. I then scrambled the values in the arrays. Then I created a 2 functions to convert from numbers to either a 3 letter pattern or a 3 digit pattern. Then I simply made the following loop:
The numbers 5119 and 719 are prime numbers and I choose them to be roughly in off of center. All in all it works very well. It will produce all of the possible plates relatively quickly. Not quite a clean and concise as the version I discussed in the other thread.
Ignore that last one. Best approach, in terms of speed versus simplicity, is to allocate the entire memory, place each plate in order in the array while simultaneously doing a simple binary tree reference in the node for a search.
Here's a bit of it, this one needs a little more code to give the gist.
Basically, since you have to keep track of all the items anyway, you might as well not bother dumping it out until your list is done. By keeping the order of generation in sequence and also using pointers for an ordered traversal, you get the best of both worlds.
Well I don't know if CS majors are required to take Number Theory or Abstract Algrbra but we can do this using the formula:
Just saw this after I posted. Very neat. And I thought pointer pointers might break someone's head.
As I found myself considering very problem specific answers, I ultimately settled on something basically generic. It's the standard CS trade off, more broadly applicable at the cost of efficiency for particular problems.
The last digit has the pattern 2,9,0,1,4,3,5,8,6,7 The last letter also has a repeating pattern. I thought that the random arrangement of the digits may hide the patterns well enough but sadly no. Of course different choices for the values of S will produce different patterns. I am not sure if the bottom digit will always have a period of 10.
void scramble(char *array, int length, int iterations);
//These are made global for convience but should be considered // to be constant after they have been scampled. char Alpha1[26] = { 'A','B','C','D','E', 'F','G','H','I','J', 'K','L','M','N','O', 'P','Q','R','S','T', 'U','V','W','X','Y', 'Z' }; char Alpha2[26] = { 'A','B','C','D','E', 'F','G','H','I','J', 'K','L','M','N','O', 'P','Q','R','S','T', 'U','V','W','X','Y', 'Z' }; char Alpha3[26] = { 'A','B','C','D','E', 'F','G','H','I','J', 'K','L','M','N','O', 'P','Q','R','S','T', 'U','V','W','X','Y', 'Z' }; char Digit1[10] = { '0','1','2','3','4', '5','6','7','8','9' }; char Digit2[10] = { '0','1','2','3','4', '5','6','7','8','9' }; char Digit3[10] = { '0','1','2','3','4', '5','6','7','8','9' };
//Rather than using a 2D array we can use the preprocessor to concatinate symbols //This macro produces the line: // scramble(Alpha1, 26, 260); #define SCRAMBLE_ALPHA(num) scramble(Alpha ## num, NUM_ALPHA, NUM_ALPHA * 10) #define SCRAMBLE_DIGIT(num) scramble(Digit ## num, NUM_DIGIT, NUM_DIGIT * 10)
void convert_alpha(char str[4], int number); void convert_digit(char str[4], int number);
int main() { int alphas, digits; char letters[4], numbers[4]; srand(time(NULL)); //Scramble the numbers and digits... // SCRAMBLE_ALPHA(1); SCRAMBLE_ALPHA(2); SCRAMBLE_ALPHA(3); SCRAMBLE_DIGIT(1); SCRAMBLE_DIGIT(2); SCRAMBLE_DIGIT(3);
void scramble(char *array, int length, int iterations) { int a, b, i; char temp; for (i = 0; i < iterations; ++i) { a = rand() % length; b = rand() % length; temp = array[a]; array[a] = array[b]; array[b] = temp; } return; }
Here's an adaptive algorithm, partially based on my original approach. It takes about a minute to execute on my system (which is getting rather old..). The output does not appear to have any obvious patterns. It finds all combinations.
Ok. I know you guys are experts and I am definitely not, but I have an idea that I want to share with you, about this problem.
This will generate 17576 (26 * 26 * 26) different numbers in about 25 seconds (on my computer anyway). I know it's not the completed program, and you'd have to change the numbers to correspond to letters (if j == 1, cout "A"; etc), but do you think something like this would work?
If not, why not?
cpp
for (int i = 1; i<= 26; i++) { for (int j=1; j<=26; j++) {
I have not tried anything yet to output the numbers. I think it would be easier than the letters, though. Seems like you could start with 100, on the first line, and go through 999, then start back at 100 again. There would not be two identical plates since the letters would be different.
What do you think?
edit--or you could start with 000 if it would print all the zeros.
This post has been edited by OliveOyl3471: 30 Aug, 2008 - 10:58 PM