My terribly inefficient array loops for generating numbers

Page 1 of 1

3 Replies - 1594 Views - Last Post: 18 November 2012 - 10:50 PMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'http://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=300755&amp;s=1cfb5fca662d428c87914d2cb6ff8795&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

#1 AndrewSa

Reputation: 4
• Posts: 100
• Joined: 02-November 12

My terribly inefficient array loops for generating numbers

Posted 18 November 2012 - 09:23 PM

I already submitted my homework which requires me to to generate 2187 random words for a 7 digit phone number.
Unfortunately, due to it being an online class my teacher never gives us any feedback; he will just grade us based on our results. However, I am actually interested in learning the material and not just getting a good grade. My question is, how do I efficiently do this without writing out 2187 combinations like I did (took my computer 20+ seconds to compile that much code). I felt like I should be using a Multi-dimension array or possibly a struct but my code was not working out right. Yes, Q and Z are removed from the array as requested by the teacher.

```#include <stdio.h> // standard input/output library

//function prototypes

int main(void)
{
//declare variables
char phoneNumber[7];// phone number array to convert into a string of alphanumberic characters
char phoneArray[10][3]={{NULL},{NULL},{'A','B','C'},{'D','E','F'},{'G','H','I'},{'J','K','L'},{'M','N','O'},{'P','R','S'},{'T','U','V'},{'W','X','Y'}}; // could not figure out how to properly use this array
char phoneTwo[]={'A','B','C'};
char phoneThree[]={'D','E','F'};
char phoneFour[]={'G','H','I'};
char phoneFive[]={'J','K','L'};
char phoneSix[]={'M','N','O'};
char phoneSeven[]={'P','R','S'};
char phoneEight[]={'T','U','V'};
char phoneNine[]={'W','X','Y'};
int i; //counter for loops
int x;
int j;

FILE *fPtr; // points to file asgn12.out

// opens or creates file - if file doesn't open then show error message
if(( fPtr = fopen( "asgn12.out", "w")) == NULL){
printf("File could not be opened.\n");
} // end if

else{

printf("Input 7 digit phone number\n"); //prompt user

//test phone number for 0's or 1's
for(i=0; i<7; i++){
if( phoneNumber[i] == '0' || phoneNumber[i] == '1'){
printf("Input 7 digit phone number\n"); //reprompt user
scanf("%s", phoneNumber);
}
}

for(i=0; i<7; i++){
if (phoneNumber[i] == '2')
fprintf(fPtr,"%c", phoneTwo[0]);
if (phoneNumber[i] == '3')
fprintf(fPtr,"%c", phoneThree[0]);
if (phoneNumber[i] == '4')
fprintf(fPtr,"%c", phoneFour[0]);
if (phoneNumber[i] == '5')
fprintf(fPtr,"%c", phoneFive[0]);
if (phoneNumber[i] == '6')
fprintf(fPtr,"%c", phoneSix[0]);
if (phoneNumber[i] == '7')
fprintf(fPtr,"%c", phoneSeven[0]);
if (phoneNumber[i] == '8')
fprintf(fPtr,"%c", phoneEight[0]);
if (phoneNumber[i] == '9')
fprintf(fPtr,"%c", phoneNine[0]);}
fprintf(fPtr,"\n");

for(i=0; i<7; i++){
if (phoneNumber[i] == '2')
fprintf(fPtr,"%c", phoneTwo[1]);
if (phoneNumber[i] == '3')
fprintf(fPtr,"%c", phoneThree[0]);
if (phoneNumber[i] == '4')
fprintf(fPtr,"%c", phoneFour[0]);
if (phoneNumber[i] == '5')
fprintf(fPtr,"%c", phoneFive[0]);
if (phoneNumber[i] == '6')
fprintf(fPtr,"%c", phoneSix[0]);
if (phoneNumber[i] == '7')
fprintf(fPtr,"%c", phoneSeven[0]);
if (phoneNumber[i] == '8')
fprintf(fPtr,"%c", phoneEight[0]);
if (phoneNumber[i] == '9')
fprintf(fPtr,"%c", phoneNine[0]);}
fprintf(fPtr,"\n");

for(i=0; i<7; i++){
if (phoneNumber[i] == '2')
fprintf(fPtr,"%c", phoneTwo[2]);
if (phoneNumber[i] == '3')
fprintf(fPtr,"%c", phoneThree[0]);
if (phoneNumber[i] == '4')
fprintf(fPtr,"%c", phoneFour[0]);
if (phoneNumber[i] == '5')
fprintf(fPtr,"%c", phoneFive[0]);
if (phoneNumber[i] == '6')
fprintf(fPtr,"%c", phoneSix[0]);
if (phoneNumber[i] == '7')
fprintf(fPtr,"%c", phoneSeven[0]);
if (phoneNumber[i] == '8')
fprintf(fPtr,"%c", phoneEight[0]);
if (phoneNumber[i] == '9')
fprintf(fPtr,"%c", phoneNine[0]);}
fprintf(fPtr,"\n");

// I repeated this 2187 times to get all 7^3 power results.

fclose(fPtr); //fclose closes file
printf("Check asgn12.out to see results.\n");
}

return 0; //end main
}

```

Is This A Good Question/Topic? 0

Replies To: My terribly inefficient array loops for generating numbers

#2 raghav.naganathan

• Perfectly Squared ;)

Reputation: 410
• Posts: 1,440
• Joined: 14-September 12

Re: My terribly inefficient array loops for generating numbers

Posted 18 November 2012 - 09:50 PM

First of all, god bless your teacher if he had scrolled through your entire program( probably from dawn to dusk).
Coming to your problem,I don't know if this will work, but try it out and let me know.

```{
.
.
for(int j=0;j<2187;j++)
{
for(i=0;i<7;i++)
{
phoneNumber[i]=rand()%10;

if (phoneNumber[i] == '2')
fprintf(fPtr,"%c", phoneTwo[0]);
if (phoneNumber[i] == '3')
fprintf(fPtr,"%c", phoneThree[0]);
if (phoneNumber[i] == '4')
fprintf(fPtr,"%c", phoneFour[0]);
if (phoneNumber[i] == '5')
fprintf(fPtr,"%c", phoneFive[0]);
if (phoneNumber[i] == '6')
fprintf(fPtr,"%c", phoneSix[0]);
if (phoneNumber[i] == '7')
fprintf(fPtr,"%c", phoneSeven[0]);
if (phoneNumber[i] == '8')
fprintf(fPtr,"%c", phoneEight[0]);
if (phoneNumber[i] == '9')
fprintf(fPtr,"%c", phoneNine[0]);
}
fprintf(fPtr,"\n");
}
}

```

regards,
Raghav

This post has been edited by raghav.naganathan: 18 November 2012 - 09:55 PM

#3 jon.kiparsky

• Pancakes!

Reputation: 8473
• Posts: 14,661
• Joined: 19-March 11

Re: My terribly inefficient array loops for generating numbers

Posted 18 November 2012 - 10:07 PM

rand? Is that a joke? No, this is not a random problem, this is a problem of generating all of the possible combinations of characters for a given phone number. For each number, there are three possibilities, so for a 1-digit number, you have a set of 3, for a 2-digit you have a set of 9, then if you add a third digit you have three more possibilies for each of the 9, and so on for 3^n where n is the length of the number - not n^3!

How to generate these? Exhaustive enumeration is heroic, but incorrect. You want to capture the essential pattern here, you want to generalize effectively. So let's talk about generating bytes. A byte is a series of 8 bits, each of which can be zero or 1. How would you list all of the possible combinations of bits that can comprise a byte? Well, you could start by listing all of the combinations of 7 bits, and then for each of them generate two new combinations, one starting with 1 and one with 0. And how do you generate those combinations? Well, quite simply: you generate all of the combinations of 6 bits, and again you extend each one with a 1 and with a zero. And so forth, until you get to the combinations of zero bits, which of course is a nothing. So, working forward from here, we'd generate bit sequence of length 1 by making a string of 1 prepended to nothing, and another of 0 prepended to nothing, and so forth.

To me, this is easiest to think of recursively: define a function f(n) which returns an array of 2^n strings consisting of 1s and 0s, by the following rule:

if n == 0, return ""
otherwise, for each string s in f(n-1), return {"0"+s, "1"+s}

You can do it iteratively if you like: start with an array of length 1, containing "". Now, count up to n, each time declaring a new array of double the previous length, and for each element s of the old array, add {"0"+s, "1"+s} to the new array.

The only difference between this and your phone number problem is that to deal with the phone numbers you have to look up the characters to append, but that's just a simple array access.

#4 raghav.naganathan

• Perfectly Squared ;)

Reputation: 410
• Posts: 1,440
• Joined: 14-September 12

Re: My terribly inefficient array loops for generating numbers

Posted 18 November 2012 - 10:50 PM

Jon, that was really very comprehensive indeed

I guess I misinterpreted the problem.

OP : As Jon says, recursion is the best way to go about it.

regards,
Raghav