# Thread: Generate all 10-digit phone numbers - backtracking

1. ## Generate all 10-digit phone numbers - backtracking

I need to generate all 10-digit telephone numbers which start with 0721 and have 3 distinct even digits (not counting the first 4). I know I should be using backtracking and I think I got the math behind this: out of the 6 remaining digits, we should have combinations of 5 taken as 3 (0, 2, 4, 6, 8) * combinations with repetitions of 5 taken as 3 (1, 3, 5, 7, 9). I'm just not sure how to write this in code as my valid function.

Code:

Code:
```#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>

#define N 6 // because we already know the first 4 digits

int v[N], even[5] = {0, 2, 4, 6, 8}, odd[5] = {1, 3, 5, 7, 9};

void display()
{
FILE *fout = fopen("telephone_numbers.txt", "w");
if(!fout)
{
fprintf(stderr, "Error opening the file.\n");
exit(EXIT_FAILURE);
}
fprintf(fout, "0721 ");
for(int i = 0; i < N; i++)
{
fprintf(fout, "%d", v[i]);
}
fputc(';', fout);
}

bool valid(int step, int v[])
{
int i;
for(i = 1; i < step; i++)
{
if(
}
}

bool solution(step)
{
if(step == N)
return true;
return false;
}

void back(int step)
{
for(int i = 0; i < N; i++)
{
if(valid(step))
{
if(solution(step))
{
display();
}
else back(step + 1);
}
}
}

int main(int argc, char **argv)
{
back(1);

return 0;
}```

2. I don't think this is a task for backtracking. For instance, to generate all 3-combos of the numbers 0,1,2,3,4:
Code:
```    for (int a = 0;     a < 3; ++a)
for (int b = a + 1; b < 4; ++b)
for (int c = b + 1; c < 5; ++c)
printf("%d%d%d\n", a, b, c);```
Those can be turned into even numbers by multiplying by 2.

3. Originally Posted by john.c
I don't think this is a task for backtracking. For instance, to generate all 3-combos of the numbers 0,1,2,3,4:
Code:
```    for (int a = 0;     a < 3; ++a)
for (int b = a + 1; b < 4; ++b)
for (int c = b + 1; c < 5; ++c)
printf("%d%d%d\n", a, b, c);```
Those can be turned into even numbers by multiplying by 2.
Thank you for the reply, however if I do this:
Code:
``` for (int a = 0;     a < 3; ++a)
for (int b = a + 1; b < 4; ++b)
for (int c = b + 1; c < 5; ++c)
printf("%d%d%d\n", 2*a, 2*b, 2*c);```
This would give as results:
024
026
028
046
048
068
246
248
268
468

Which are all ordered, but I think I need combinations as well, so that the order doesn't matter, like 204 864 etc. Could I display the 3-digit combinations of the even numbers without using backtracking? Sort of starting from your code?

4. Take the current loop indices, create an array from them and use, e.g., Heap's algorithm to generate the permutations (not "combinations", which is what we are generating with the loops).
Code:
```#include <stdio.h>

void swap(int *a, int i, int j) { int t = a[i]; a[i] = a[j]; a[j] = t; }

void print(const int *a, int n) {
for (int i = 0; i < n; ++i) printf("%d", a[i]);
putchar('\n');
}

// Heap's algorithm
void permutations(int *a, int size, int n) {
if (size == 1)
print(a, n);
else
for (int i = 0; i < size; ++i) {
permutations(a, size - 1, n);
swap(a, size % 2 == 1 ? 0 : i, size - 1);
}
}

int main() {
for (int a = 0;     a < 3; ++a)
for (int b = a + 1; b < 4; ++b)
for (int c = b + 1; c < 5; ++c) {
int nums[6] = {a*2, b*2, c*2};
permutations(nums, 3, 3);
}
return 0;
}```

5. Your problem statement is a little unclear. If a number has "3 distinct even digits" what does that say about the remaining digits? Could the extra digits also be even, or must they be odd? Are the extra digits allowed to contain repeats of the "distinct even digits"? Is -002244 a valid set of digits?

My suggestion would be to implement a generator. Just iterate through the digits, calling a validation function once per iteration. There just aren't that many results, valid or not, so pretty much any optimization at this point is premature. Once you have something that you know works, you might apply some speedups afterwards, with the known-good results as your testing criteria.

6. It's not "premature optimization", just a different algorithm. But I agree that it's too complicated for this. There's only a million 6 digit numbers so you could just loop from 0 to a million and test the numbers for the conditions.

I also agree about the hazy spec. I'm assuming exactly 3 even numbers, all distinct, with the other 3 being any odd numbers, which don't need to be distinct.

This code generates 150,000 telephone numbers. I'm not sure it that's the correct count.
Code:
```#include <stdbool.h>
#include <stdio.h>

bool okay(int n) {
int d[10] = {0};
for (int i = 0; i < 6; ++i, n /= 10)
++d[n % 10];
// Exactly 3 even digits.
if (d[0] + d[2] + d[4] + d[6] + d[8] != 3)
return false;
// All even digits are distinct.
if (d[0] > 1 || d[2] > 1 || d[4] > 1 || d[6] > 1 || d[8] > 1)
return false;
return true;
}

int main() {
int count = 0;
for (int n = 0; n < 1000000; ++n)
if (okay(n)) {
//printf("0721%06d\n", n);
++count;
}
printf("count: %d\n", count);
return 0;
}```