StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>Assuming:</p> <p>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?</p> <p>2) Your input is all lowercase.</p> <p>3) Your input is < 32 characters long. (# of usable bits in the permutation counter, i)</p> <pre><code> 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; } </code></pre> <p>Note: I haven't compiled or tested this code. This is also implementing the bitwise compare that sharptooth suggested above.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload