0

In C, I have a char array with random numbers and letters without capital letters. I'd need to figure out how can I generate all possible combinations that include capital letters while leaving the numbers intact but I'm not even sure where to begin. (Eg. abc123, Abc123, aBc123, abC123, ABc123, AbC123, aBC123, ABC123)

Dolog
  • 11
  • Start by being clearer about what you want: is your example saying your initial array contained `abc123`, and you want all of the ways to capitalize some (possibly all) of the letters? – Scott Hunter May 22 '15 at 19:48
  • If you have `n` letters there are `2^n` ways to have them be upper or lower case, and exactly one that has no upper case letters. Enumerating these should be easy. – MooseBoys May 22 '15 at 19:52

2 Answers2

2

Indeed it will be 2^n possibilities, n meaning the amount of alphabetic characters you have in your char array.

To solve your problem, I suggest you to see about recursion, I guess it's the easiest way to achieve what you want to do, you just have to think a bit differently than usual.

EDIT : Here is some implementation

void enumerate(char *str, int n)
{
  printf("%s\n", str); // Print one solution
  while (++n < strlen(str)) // Loop while you don't reach the end
    if (str[n] > 96 && str[n] < 123) // Check if str[n] is alphabetic
      {
        char *tmp = calloc(strlen(str) + 1, sizeof(char));
        strcpy(tmp, str); // Create a copy of the initial string
        tmp[n] -= 32; // Put tmp[n] = str[n] in uppercase
        enumerate(tmp, n); // Call recursion with new string and current position
      }
}

And you call it like this

enumerate("abc123", -1);

Results in 

abc123
Abc123
ABc123
ABC123
AbC123
aBc123
aBC123
abC123
Misery
  • 495
  • 4
  • 17
  • Awesome, thanks! Took a while to figure out how to return the values into another function to use them and I can't say I completely understand how it works but then again yesterday I didn't even know the difference between char arrays and char pointers so it took a lot of searching but now it's working perfectly. – Dolog May 23 '15 at 20:38
  • If you have any question about this is working, feel free to ask. Plus, I suggest you to run it with printing values in each steps of the recursion to understand how it works. – Misery May 25 '15 at 00:41
1

For the moment, disregard the digits.

Say you now have x characters. If x=3(suppose), then consider numbers from 0 to 7, since 2^3 - 1 is 7 (-1 because you have to take 0 into account as a state).

Then you have to iterate through all numbers and capitalize a letter whenever its bit is 1.

Example:

  • abc - 000 (0)
  • abC - 001 (1)
  • aBc - 010 (2)
  • aBC - 011 (3)
  • Abc - 100 (4)

Here's the code for it, for those who could not follow the theoretical explanation.

void enumerate (String input) {

    int count = 0;
    //count the number of non-digit characters
    for(int i=0; i<input.length(); i++)
        if(!Character.isDigit(input.charAt(i))) {
            count++;
        }

   count =(int) Math.pow(2,count); 
   //printing all the combinations.
   int i=0, digit=0;
   while(count--> 0) {
       String output = ""; 
       for(int j=input.length()-1; j>=0; j--) {
           char c = input.charAt(j);   
           if(Character.isDigit(c))
               output = (char)c + output;
           else {
               output = (char) (((i&1) == 1)? c-32 : c) + output;
               i = i>>1;
           }
       }
       System.out.println(output);
       i = ++digit;

   }
}
Anindya Dutta
  • 1,972
  • 2
  • 18
  • 33