A c++ question with sorting

May 29, 2011 at 2:17am
Alright, so I have this program that I'm writing and I need to find all the possible outcomes of a the last 5 digits of a 10 digit number. So, I have the user input the first four numbers, then an IF statement to see if the the 4th number is odd or even, so that the 5th number is set to the opposite (IE 4th = odd, 5th = even; vic versa) Then I have a vector that I want to randomly generate all possible outcomes of the last 5 numbers that sum 33.

Heres what I have so far:

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
#include "stdafx.h"
#include <iostream>
#include <ctime>
#include <vector>
#include <algorithm>

using namespace std;


int main()
{
	vector<int> teleNumbs;
	vector<int> geneNumbs;
	int telenum;
	int oddEven = 0;
	int iRand;

	srand(time(NULL));

	cout << "Please enter the first four digits of the telephone number: " << endl;

	for( int i=0; i<4; i++){
		cout << " Enter number " << i+1 << ": " << endl;
		cin >> telenum;
		teleNumbs.push_back(telenum);
	}

	if( teleNumbs[3] % 2 == 0 ){
		oddEven = 1;
	}
	else{ oddEven = 2;}


//Now I want to find all possible outcomes totaling 33 and print those possible outcomes in this format:

//(xxx) xxx xxxx
// I want the last 5 digits from the geneNumbs vector to total 33 in all possible ways

	return 0;
}


How could I go about doing this?

Thanks for any help and suggestions!!!
May 29, 2011 at 3:16am
The list of five digit numbers that sum to 33 will always be the same. (There are 1745 of them.)
Here's some pseudocode to do it:

1
2
3
4
5
6
7
8
for (int n = 0; n < 100000; n++)
  {
  int sum = 0;
  for (int x = n; x; x /= 10)
    sum += x;
  if (sum == 33)
    cout << setw( 5 ) << setfill( '0' ) << right << n << endl;
  }

That's not tested. Here's the code I actually used to do it in Tcl:

for {set n 0} {$n < 100000} {incr n} {
  set ns [split $n {}]
  set sum [expr [join $ns +]]
  if {$sum == 33} {puts $ns}
  }

The only thing you'll have to do is go through the 5 possible values for the fifth digit (odd or even), which will bring your grand total to 8725 answers.

Hope this helps.

[edit] Fixed code to put each number on its own line... [edit] Fixed code typo to check against the correct variable...
Last edited on Jun 2, 2011 at 11:25am
May 29, 2011 at 3:27am
Could you explain what you are doing by setw and setfill? I looked it up, but it doesn't work with my code. Thanks.
May 29, 2011 at 4:01am
setw() spaces the output a certain number of spots. setfill is the character used in between (default is a space)

play with the two you'll see how it works.
May 29, 2011 at 12:16pm
Alright, so I guess I understand how the setw works, but how could I implement this to show every possible combination in this format:

(xxx) xxx xxxx

? Obviously, I have the first four digits from user input, and "oddEven" is set to 1 or 2 based on if teleNumbs[3] is odd or even.

So, I just cout those digit in front of the setw output?

Sorry, I'm new at this.
May 29, 2011 at 1:49pm
BUMP

**EDIT**

@Duaos

Your code didn't have any results that pertained to my question. I'm not sure what you were trying to do but I think you misunderstood what I was trying to do, unless you care to explain further.

Please help someone.
Last edited on May 29, 2011 at 2:08pm
May 30, 2011 at 3:02am
Your code didn't have any results that pertained to my question.

Oh?

... Then I have a vector that I want to randomly generate all possible outcomes of the last 5 numbers that sum 33.

My code did exactly that; it produces all five-digit numbers whose digits sum to 33. If that isn't what you want, then why did you ask for it?

To print a number as you want it, use the formatted output functions.
In the following snippet, the variables are:

  first_four   - The first four digits of the telephone number
  current_5th  - The fifth digit, which will be (as the loop rolls) 1,3,5,7,9 or 0,2,4,6,8
  n            - The same as the previous snippet I gave you

You will, of course, have to put in the loop for current_5th and the loop as above, and replace the output with the following.

1
2
3
geneNumbs.push_back(
  (first_four * 1000000) + (current_5th * 100000) + n 
  );

Output with:

1
2
3
4
5
6
cout << setfill( '0' ) << right;
...
cout << "("  << setw( 3 ) <<  (geneNumbs[ idx ] / 10000000)
     << ") " << setw( 3 ) << ((geneNumbs[ idx ] % 10000000) / 10000)
     << " "  << setw( 4 ) <<  (geneNumbs[ idx ]             % 10000)
     << "\n";
Be sure to note, also, that int is unlikely to be big enough to hold a ten-digit number. Use an unsigned long.

If I still haven't understood, then please be more exact in how you state the question.
May 31, 2011 at 3:04pm
Sorry, was gone for Memorial Day weekend.

That may work as a set of numbers, which I'm sure is much more efficient. Though, as you can see by the vector initializations, I would like each digit stored in there respective vector position, so then I can output the proper output using each element, such as:

 
cout << "(" << teleNumbs[0] << teleNumbs[1] << teleNumbs[2] << ")" << " " << teleNumbs[3] << even << geneNumbs[0] << " " << geneNumbs[1] << geneNumbs[2] << geneNumbs[3] << geneNumbs[4] << endl;


Could you help me understand how I'd do this?

I have it like this so far, but it seems and works very wrong, only outputting once. This programming stuff is tough.

Thanks a lot.

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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include "stdafx.h"
#include <iostream>
#include <ctime>
#include <vector>
#include <algorithm>
#include <iomanip>

using namespace std;


int main()
{
	vector<int> teleNumbs;
	vector<int> geneNumbs (5, 0);
	int telenum;
	int even = 0;
	int odd = 1;
	int iRand = 0;

	srand((unsigned int)time(NULL));

	cout << "Please enter the first four digits of the telephone number: " << endl;

	for( int i=0; i<4; i++){
		cout << " Enter number " << i+1 << ": " << endl;
		cin >> telenum;
		teleNumbs.push_back(telenum);
	}

	if( (teleNumbs[3] % 2) != 0){ //If teleNumbs 4 is odd...
		for( int even=0 ; even < 9; even+=2){
		for( int j=0; j<10; j++){
			geneNumbs[0]++;
				for( int k=0; k<9; k++){
					geneNumbs[1]++;
					for( int l=0; l<9; l++){
						geneNumbs[2]++;
						for( int m=0; m<9; m++ ){
							geneNumbs[3]++;
							for( int n=0; n<9; n++ ){
								geneNumbs[4]++;
								if( (even + geneNumbs[0] + geneNumbs[1] + geneNumbs[2] + geneNumbs[3] + geneNumbs[4]) == 33){
									cout << "(" << teleNumbs[0] << teleNumbs[1] << teleNumbs[2] << ")" << " " << teleNumbs[3] << even << geneNumbs[0] << " " << geneNumbs[1] << geneNumbs[2] << geneNumbs[3] << geneNumbs[4] << endl;
								}
							}//It only outputs one outcome and it doesn't even add up to 33
						}
					}
				}
			}
		}
	}
	else{ //if teleNumbs[3] is even...
		for( int odd=1; odd<10; odd+=2){
			for( int j=0; j<10; j++){
				geneNumbs[0]++;
					for( int k=0; k<9; k++){
						geneNumbs[1]++;
						for( int l=0; l<9; l++){
							geneNumbs[2]++;
							for( int m=0; m<9; m++ ){
								geneNumbs[3]++;
								for( int n=0; n<9; n++ ){
									geneNumbs[4]++;
									if( (odd + geneNumbs[0] + geneNumbs[1] + geneNumbs[2] + geneNumbs[3] + geneNumbs[4]) == 33){
									cout << "(" << teleNumbs[0] << teleNumbs[1] << teleNumbs[2] << ")" << " " << teleNumbs[3] << even << geneNumbs[0] << " " << geneNumbs[1] << geneNumbs[2] << geneNumbs[3] << geneNumbs[4] << endl;
								} //It only outputs one outcome and it doesn't even add up to 33
							}
						}
					}
				}
			}
		}
	}






	system("pause");

	return 0;
}
Last edited on May 31, 2011 at 3:07pm
May 31, 2011 at 3:48pm
Bump
May 31, 2011 at 8:28pm
Ah, if I understand you correctly, you are keeping exactly two things that represent the individual digits in a telephone number:

  teleNumbs - the list of digits given to you by the user
  geneNumbs - the list of digits for a complete telephone number generated by your program

If this is the case, then what about this:
Then I have a vector that I want to randomly generate all possible outcomes of the last 5 numbers that sum 33. [edited]
I have, thus far, ignored the word "randomly" since if you generate all possible outcomes there is no point in being random about it.

Are you actually trying to generate only a single possible outcome, chosen at random from all possible outcomes?
May 31, 2011 at 8:59pm

Ah, if I understand you correctly, you are keeping exactly two things that represent the individual digits in a telephone number:

teleNumbs - the list of digits given to you by the user
geneNumbs - the list of digits for a complete telephone number generated by your program


That is correct, teleNumbs is user input, geneNumbs is all possible combinations equaling 33.

Are you actually trying to generate only a single possible outcome, chosen at random from all possible outcomes?


I'm trying to get all possible combinations, so no, I guess it's not random.

Now this, helps.

Thanks.
Last edited on May 31, 2011 at 9:02pm
Jun 1, 2011 at 12:51am
Combinations don't care about order. So "5 2 9 8 7" is the same as "8 9 2 7 5". (Repeats are possible, but I am still unsure if you want them...)

For permutations, order does matter, just as it does for normal telephone numbers.


If you want all possible numbers, but you want individual digits stored as separate integers in a vector, then you need to improve the way you will store your numbers (such as a vector of vectors), or do you just plan to count them off in fives?

I am still unconvinced you answered my question about the 'teleNumbs' and 'geneNumbs' variables. A complete phone number is ten digits. Should the 'geneNumbs' variable have the complete phone number, or do you wish it to have only the last five, or what?

For example, do you want each output to be 'teleNumbs' + 5th digit + 'geneNumbs' or something like that?

-----

The algorithm I have showed you works like this: by starting at 00000 and counting to 99999, you have every possible five-digit number. This is easily done in a loop by simply adding one to a variable every time.

Each time through the loop, you want to know if the digits sum to 33 (or 30 or whatever). To do this you'll need a way to separate and sum the digits. (My example above does just that for you.) Once you have their sum, if it matches the desired sum, then you can add the digits to your list of answers.

Let me know how you want to continue.
Jun 1, 2011 at 3:44am
Yes, I want combination, so the order doesn't matter, nor does repetition. Just so long as the sum is the same.

The teleNumbs is the first four digits of the telephone number, which is user input, then the fifth digit is to be odd is teleNumbs[3] is even and vic versa. The geneNumbs will be the rest of the phone number, and the the last 6 digits must combine to be 30/33, whatever.

I want the output to be teleNumbs[0] - [3] + fifth digit + geneNumbs[0] - [4].

Thanks a lot for the help, it has stumped me for a while now.
Jun 1, 2011 at 4:14pm
bump
Jun 1, 2011 at 8:45pm
OK then, the algorithm doesn't change much. Just use the brute-force method I've given you, then order all of them and get rid of duplicate lists.
Jun 2, 2011 at 3:07am
Only problem is, your bruteforce method is only giving me this output:

33XXX

they dont add to 33.
Jun 2, 2011 at 11:25am
I made a very obvious typo. I fixed it above.
Jun 2, 2011 at 2:43pm
Thanks, but I believe I caught that too, I was messing around with it because I knew sum was being intialized, but not being used. So I knew something wasn't right.

Now though, I get an output like this:

(XXX) XX33

from this code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
if( (teleNumbs[3] % 2) != 0){

		for( int even = 0; even<10; even+=2 ){
			for (int n = 0; n < 100000; n++){
				int sum = 0;
				for (int x = n; x; x /= 10){
					sum += x;
					if (sum == 33){
					numPoss++;
					oddEven.push_back(even);
					geneNumbs.push_back(sum);
					}
				}
			 }
		}
		for( int j=0; j<numPoss; j++){
			cout << "(" << teleNumbs[0] << teleNumbs[1] << teleNumbs[2] << ") " << teleNumbs[3] << oddEven[j] << geneNumbs[j] << endl;
		}
	}

	else{


What am I doing wrong?
Jun 2, 2011 at 4:52pm
Bump?
Jun 3, 2011 at 1:22am
You aren't supposed to push_back(sum); the generated number is n, so geneNumbs.push_back(n);

My head is splitting so I haven't really looked too hard at it tonight. Sorry. :-(
Topic archived. No new replies allowed.