Thread: Generate all 10-digit phone numbers - backtracking

  1. #1
    Registered User
    Join Date
    Jan 2021
    Posts
    11

    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. #2
    Registered User
    Join Date
    Dec 2017
    Posts
    1,626
    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.
    A little inaccuracy saves tons of explanation. - H.H. Munro

  3. #3
    Registered User
    Join Date
    Jan 2021
    Posts
    11
    Quote Originally Posted by john.c View Post
    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. #4
    Registered User
    Join Date
    Dec 2017
    Posts
    1,626
    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;
    }
    A little inaccuracy saves tons of explanation. - H.H. Munro

  5. #5
    Registered User
    Join Date
    Apr 2021
    Posts
    138
    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. #6
    Registered User
    Join Date
    Dec 2017
    Posts
    1,626
    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;
    }
    Last edited by john.c; 06-13-2021 at 07:32 AM.
    A little inaccuracy saves tons of explanation. - H.H. Munro

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Read from file - 1-digit and 2-digit numbers
    By Bonaventura in forum C Programming
    Replies: 8
    Last Post: 03-06-2010, 06:33 AM
  2. Quick Question Regarding Scanf() & Phone Numbers!
    By weaveram in forum C Programming
    Replies: 3
    Last Post: 09-20-2007, 09:58 AM
  3. Classes using phone numbers
    By correlcj in forum C++ Programming
    Replies: 3
    Last Post: 11-13-2002, 10:17 PM
  4. phone numbers using classes?
    By correlcj in forum C++ Programming
    Replies: 3
    Last Post: 11-09-2002, 06:31 PM
  5. Convert Phone Letters To Numbers
    By nicolobj in forum C Programming
    Replies: 4
    Last Post: 10-03-2002, 03:53 PM

Tags for this Thread