Permutations of capitalization

Question

I want to build a list containing every possible permutation of capitalization of a word. so it would be

List<string> permutate(string word)
{
    List<string> ret = new List<string>();
    MAGIC HAPPENS HERE
    return ret;
}

So say I put in "happy" I should get an array back of

{happy, Happy, hAppy, HAppy, haPpy, HaPpy ... haPPY, HaPPY, hAPPY, HAPPY}

I know of plenty of functions that will capitalize the first letter but how do I do any arbitrary letter in the word?

Answer 1

Loosely speaking, something like below. I may have my ranges off by one, but the idea is sound.

def cap_n(in_str, pos):
  leading = in_str.substr(0, pos-1)
  trailing = in_str.substr(pos+1) # no second arg implies to end of string
  chr = in_str[pos].to_uppercase()
  return leading + chr + trailing

Answer 2

Use bitwise operations. For a word of length N you need an integer type represented by N bits. If the word is longer - split it. Iterate through values from 0 to 2^N-1 and examine each bit from 0 to N-1. If the bit is 1 - upcase ( Char.ToUpper() ) the letter corresponding to that bit.

This approach is better that a recursive algorithm since it is not prone to stack overflows on long words.

Answer 3

Keep in mind that while the accepted answer is the most straightforward way of capitalizing an arbitrary letter, if you are going to change the capitalization repeatedly on the same set of letters (e.g., 32 times in "happy" and growing exponentially for longer words), it will be more efficient to turn the string into a char[], set the appropriate letter(s), and construct the string from the array.

Answer 4

You can modify individual characters if you convert your string to an array of char. Something like this should do the trick...

public static List<string> Permute( string s )
{
  List<string> listPermutations = new List<string>();

  char[] array = s.ToLower().ToCharArray();
  int iterations = (1 << array.Length) - 1;

  for( int i = 0; i <= iterations; i++ )
  {
    for( int j = 0; j < array.Length; j++ )
    array[j] = (i & (1<<j)) != 0 
                  ? char.ToUpper( array[j] ) 
                  : char.ToLower( array[j] );
    listPermutations.Add( new string( array ) );
  }
  return listPermutations;
}

Answer 5

Assuming:

1) You don't care too much that this is O(n*2^n)... although I'm curious to know: what is the best asymptotic run time for this type of problem?

2) Your input is all lowercase.

3) Your input is < 32 characters long. (# of usable bits in the permutation counter, i)

    List<string> permutate(string word)
{
    List<string> ret = new List<string>();

// MAGIC HAPPENS HERE
Dictionary<char,char> toUppers = new Dictionary<char,char>(26);
toUppers.Add('a', 'A');
toUppers.Add('b', 'B');
toUppers.Add('c', 'C');
toUppers.Add('d', 'D');
toUppers.Add('e', 'E');
toUppers.Add('f', 'F');
toUppers.Add('g', 'G');
toUppers.Add('h', 'H');
toUppers.Add('i', 'I');
toUppers.Add('j', 'J');
toUppers.Add('k', 'K');
toUppers.Add('l', 'L');
toUppers.Add('m', 'M');
toUppers.Add('n', 'N');
toUppers.Add('o', 'O');
toUppers.Add('p', 'P');
toUppers.Add('q', 'Q');
toUppers.Add('r', 'R');
toUppers.Add('s', 'S');
toUppers.Add('t', 'T');
toUppers.Add('u', 'U');
toUppers.Add('v', 'V');
toUppers.Add('w', 'W');
toUppers.Add('x', 'X');
toUppers.Add('y', 'Y');
toUppers.Add('z', 'Z');

char[] wordChars = word.ToCharArray();
int len = wordChars.Length;

// iterate the number of permutations
for(int i = 0; i < 2^len; i++) {
    char[] newWord = new char[len]();

    // apply "i" as a bitmask to each original char
    for(int n = 0; n < newWord.Length; n++) {
     if((1 << n) & i != 0) {
      newWord[n] = toUppers[wordChars[n]]; // or skip the dictionary and just call Char.ToUpper(wordChars[n])
     } else {
      newWord[n] = wordChars[n];
     }
    }
    ret.Add(new String(newWord));
}

    return ret;
}

Note: I haven't compiled or tested this code. This is also implementing the bitwise compare that sharptooth suggested above.

Answer 6

To "permute" your string (technically, this isn't permutation since you're not changing the order of anything, but I don't want to be seen as an an*l-retentive :-), I would use a recursive approach, which basically "permutes" the string minus the first character and attaches those to the upper and lower variations of that character.

Something like (in C, my C# is not really up to par so you'll have to convert it):

#include <stdio.h>
#include <string.h>

static void permute (char *prefix, char *str) {
    char *newPrefix;

    /* End of string, print and return. */

    if (*str == '\0') {
        printf ("%s\n", prefix);
        return;
    }

    /* Allocate space for new prefix. */

    if ((newPrefix = malloc (strlen (prefix) + 2)) == NULL) {
        printf ("ERROR: Cannot allocate memory.\n");
        return;
    }

    /* Do lowercase/sole version and upper version if needed. */

    sprintf (newPrefix, "%s%c", prefix, *str);
    permute (newPrefix, &(str[1]));

    if (islower (*str) {
        sprintf (newPrefix, "%s%c", prefix, toupper(*str));
        permute (newPrefix, &(str[1]));
    }

    /* Free prefix and return. */

    free (newPrefix);
}

 

int main (int argc, char *argv[]) {
    char *str, *strPtr;

    /* Check and get arguments. */

    if (argc < 2) {
        printf ("Usage: permute <string to permute>\n");
        return 1;
    }

    if ((str = malloc (strlen (argv[1]) + 1)) == NULL) {
        printf ("ERROR: Cannot allocate memory.\n");
        return 1;
    }
    strcpy (str, argv[1]);

    /* Convert to lowercase. */
    for (strPtr = s; *strPtr != '\0'; strPtr++)
        *strPtr = toupper (*strPtr);

    /* Start recursion with empty prefix. */

    permute ("", str);

    /* Free and exit. */

    free (str);
    return 0;
}

Running this as "permute Pax1" returns:

pax1
paX1
pAx1
pAX1
Pax1
PaX1
PAx1
PAX1