How to generate all the distinct numbers which can be formed by eliminating one or more digits from left and/or right end of each number

Question

I need to read some numbers from a file and generate all the numbers which can be formed by removing 1 digit from the start and one from the end ( for each one of my numbers read ) and print them into a new file.I know how to read and print in files so my question is more about the way I should think when solving this problem. Here is an example for this problem:

for 3457 the output should be:

457
345
34
45
57
3
4
5
7

my initial thought was to read the numbers as an array of strings using a double pointer ( assuming I know how many numbers I should read so I can dynamically allocate memory to it ) and then to work on them.

After that I though of a way to generate the numbers that are obtained by removing 1 digit from the start and one from that end ( but not simultaneously ) for that I used a for loop:

for ( i = 1, j = (strlen(p[0]) - 2); i < strlen(p[0]) - 2, j >=0; ++i, --j ) //p[0] is my first number read from the file
{
    printf("\n%s", p[0] + i); //this will print the numbers 457, 57, 7

    char temp[10];

    strncpy(temp, p[0], j);//I copy into a new temporary string to print the numbers 345, 34, 3
    temp[j] = '\0';

    printf("%s", temp);
    printf("\n%s", temp + i);//this will print the numbers 45,4





}  

But I have no idea on how to proceed with the rest of the numbers and i simply wasn't able to find or to think of an algorithm which will print them in that order, so I would really appreciate some help on how to solve this problem

Answer 1

Assuming that you have the number converted to a string (e.g. using sprintf) you could do something like this:

• Take the original string and remove 0 chars from the right

  • Remove 0 chars from the left and print
  • Remove 1 chars from the left and print
  • Remove 2 chars from the left and print
  • ...
  • Remove string length - 1 chars from the left and print

• Take the original string and remove 1 chars from the right

  • Remove 0 chars from the left and print
  • Remove 1 chars from the left and print
  • Remove 2 chars from the left and print
  • ...
  • Remove string length - 1 chars from the left and print

• Take the original string and remove 2 chars from the right

  • Remove 0 chars from the left and print
  • Remove 1 chars from the left and print
  • Remove 2 chars from the left and print
  • ...
  • Remove string length - 1 chars from the left and print

The above is easy to implement using two nested for-loops. Like:

int main()
{
  char str[] = "123456";
  size_t len = strlen(str);
  size_t i, j;
  for (i = 0; i < len; i++) // i is number of chars to remove (aka not print) from right
  {
    for (j = 0; j < len-i; j++) // j is number of chars to remove (aka not print) from left
    {
      size_t z=j;
      int p = 0;
      while (z < (len - i))
      {
        printf("%c", str[z]);
        z++;
        p = 1;
      }
      if (p) printf("\n");
    }
  }
  return 0;
}

Output:

123456
23456
3456
456
56
6
12345
2345
345
45
5
1234
234
34
4
123
23
3
12
2
1

Now if the input string is "1001" the output of the program is (comments added manually):

1001  // ok
001   // Is this valid? Or should it be 1
01    // Is this valid? Or should it be 1
1     // ok
100   // ok
00    // Is this valid? Or should it be 0
0     // ok
10    // ok
0     // ok but repeated! Is this valid?
1     // ok but repeated! Is this valid?

As you can see there may be a problem with the algorithm, e.g. leading zero and repeated numbers. If that is invalid, you'll have to

1. keep track of already printed numbers
2. avoid printing leading zeros

Answer 2

The following assumes that the numbers are read from the input file as strings (null-terminated character arrays) and that those strings are valid representation of base 10 integers, not necessarily in the range of an int, just only digits.

• Skip the leading zeroes. I assume that a string like "0042", if not rejected, should be interpreted as the number 42, so that the output should be only 4 and 2, without any 0. strspn could be used here.

• Find the length (len) of the remaining string, if it's less then two characters, return.

• Loop from 1 (included) to len (excluded). That is the number of characters to be removed from the source, let's call it i.

  • The size of the substrings is sub_length = len - i.

  • Loop from 0 to i (both included) to consider all the substrings of size sub_length. E.g. from 123 we consider first 12 and 23.

    • If the first character of the substring is '0' and its length is greater than 1, skip the following steps, so that e.g. from 1007 we won't print 007 nor 07, only 0 and 7.

    • Check if the actual substring can be found in the left part of the source string that we have already considered. E.g. given 4545, after having printed 45 and 54 we would find the last 45 in 454 and skip it. A loop with functions like strncmp or memcmp may come in handy, here, more than strstr which requires null-terminated strings as parameters.

    • If the previous step doesn't find a duplicate, print the substring (with a loop, or using printf with the format specifier "%.*s" as explained here).

This algorithm would produce the following results:

Source: "3457"
345 457 34 45 57 3 4 5 7

Source: "1045"
104 10 45 1 0 4 5

Source: "5454"
545 454 54 45 5 4

Source: "10000"
1000 100 10 1 0

Source: "0042"
4 2