Capitalization reshuffle

Question

I want to build a list containing all the possible permutations of the capital letters of the word. so it would be

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

Say I put in "happy" I have to get the array back

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

I know many functions that capitalize the first letter, but how do I make an arbitrary letter in a word?

Answer 1

You can change individual characters if you convert a string to a char array. 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 2

Keep in mind that although the accepted answer is the easiest way to capitalize an arbitrary letter, if you intend to repeatedly change capitalization on the same set of letters (for example, 32 times “happy” and grow exponentially for longer words), there will be more effectively turn the string into char [], set the corresponding letter and build the string from the array.

Answer 3

To "rearrange" your string (technically this is not a permutation, since you do not change the order of anything, but I do not want to be treated as * l-retentive :-), I would use a recursive approach that basically "rearranges" "string minus the first character and appends it to the upper and lower variants of that character.

Something like (in C, my C # doesn't actually match the parameter, so you 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; } 

Doing this as "permute Pax1" returns:

 pax1 paX1 pAx1 pAX1 Pax1 PaX1 PAx1 PAX1 

Answer 4

I managed to create a console application that does this ..

  public static class Program { static void Main() { Console.WriteLine("Enter string"); string value = Console.ReadLine(); value = value.ToLower(); List<string> list = new List<string>(); var results = from e in Enumerable.Range(0, 1 << value.Length) let p = from b in Enumerable.Range(0, value.Length) select (e & (1 << b)) == 0 ? (char?)null : value[b] select string.Join(string.Empty, p); foreach (string s in results) { string newValue = value; s.ToLower(); foreach(char c in s) { var Old = c.ToString().ToLower(); var New = c.ToString().ToUpper(); newValue=ReplaceFirstOccurrence(newValue, Old, New); } list.Add(newValue); } foreach(string s in list) { Console.WriteLine(s); } Console.ReadKey(); } public static string ReplaceFirstOccurrence(string Source, string Find, string Replace) { int Place = Source.IndexOf(Find); string result = Source.Remove(Place, Find.Length).Insert(Place, Replace); return result; } } 

I got a list of all possible subsets of characters in a string, then for each character in each subset I replaced them with uppercase counterparts in the original string, and then made a list of them. Must have a custom function Replace as a regular string. Replacing will replace any occurrence of a character.

This is probably not the cleanest code, but it does its job. This was called as a means of dynamically searching encrypted fields, and I wanted to see how crazy it could be.

Answer 5

In short, something like below. I may have ranges for one, but the idea sounds.

 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 6

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

This approach is better than a recursive algorithm because it is not prone to stack overflow on long words.

Answer 7

Assuming that:

1) You don't care what it is O (n * 2 ^ n) ... although I am curious to know: what is the best asymptotic runtime for this type of problem?

2) Your input is all lowercase letters.

3) Your input is <32 characters. (the number of bits used 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 have not compiled or tested this code. It also implements the bitwise comparison suggested above by sharptooth.

Answer 8

If order doesn't matter, you can try Linq. We list all binary numbers in the range [0..2**word.Length] . and treat each number as a mask: 0 - lower case, 1 - upper case. FDor instance for happy we have

 mask string ---------------- 00000 -> happy 00001 Happy 00010 hAppy 00011 HAppy 00100 haPpy 00101 HaPpy ... 11111 HAPPY 

Code:

  using System.Linq; ... List<string> permutate(string word) => Enumerable .Range(0, 1 << word.Length) .Select(mask => string.Concat(word.Select((c, i) => (mask & (1 << i)) == 0 ? c : char.ToUpper(c)))) .ToList(); 

Demo version:

  Console.Write(string.Join(", ", permutate("happy"))); 

Result:

 happy, Happy, hAppy, HAppy, haPpy, HaPpy, hAPpy, HAPpy, hapPy, HapPy, hApPy, HApPy, haPPy, HaPPy, hAPPy, HAPPy, happY, HappY, hAppY, HAppY, haPpY, HaPpY, hAPpY, HAPpY, hapPY, HapPY, hApPY, HApPY, haPPY, HaPPY, hAPPY, HAPPY