我想建立一个包含单词大写所有可能排列的列表。所以它会是
List<string> permutate(string word)
{
List<string> ret = new List<string>();
MAGIC HAPPENS HERE
return ret;
}
所以说我输入"happy"我应该得到一个数组
{happy, Happy, hAppy, HAppy, haPpy, HaPpy ... haPPY, HaPPY, hAPPY, HAPPY}
我知道有很多函数会将第一个字母大写，但我如何在单词中添加任意字母？
如果将字符串转换为 char 数组，则可以修改单个字符。像这样的东西应该可以解决问题......
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;
}
请记住，虽然公认的答案是将任意字母大写的最直接方法，但如果您要在同一组字母上反复更改大写（例如，“快乐”中的 32 次，并且对于更长的单词呈指数增长） ，将字符串转换为 char[]，设置适当的字母，并从数组构造字符串会更有效。
要“置换”你的字符串（从技术上讲，这不是置换，因为你没有改变任何东西的顺序，但我不想被视为一个 *l-retentive :-)，我会使用递归方法，它基本上“置换”字符串减去第一个字符，并将它们附加到该字符的上下变化。
类似的东西（在 C 中，我的 C# 并没有真正达到标准，所以你必须转换它）：
#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;
}
运行此作为"permute Pax1"返回：
pax1
paX1
pAx1
pAX1
Pax1
PaX1
PAx1
PAX1
我能够创建一个控制台应用程序来执行此操作..
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;
}
}我得到了字符串中所有可能的字符子集的列表，然后对于每个子集中的每个字符，将它们替换为初始字符串中的大写对应字符，然后列出这些字符。必须有一个自定义替换函数作为普通字符串。替换将替换任何出现的字符。
它可能不是最干净的代码，但它可以完成工作。这是作为动态搜索加密字段的一种手段提出来的，我想看看这到底有多疯狂……
如果顺序无关紧要，您可以尝试Linq。我们枚举范围内的所有二进制数[0..2**word.Length]。并将每个数字视为掩码：0- 小写，1- 大写。例如happy我们有
mask string
----------------
00000 -> happy
00001 Happy
00010 hAppy
00011 HAppy
00100 haPpy
00101 HaPpy
...
11111 HAPPY
代码：
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
? char.ToLower(c)
: char.ToUpper(c))))
.ToList();
演示：
Console.Write(string.Join(", ", permutate("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, HAPPY
粗略地说，如下所示。我可能会将我的范围缩小一倍，但这个想法是合理的。
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
使用按位运算。对于长度为 N 的单词，您需要一个由 N 位表示的整数类型。如果单词更长 - 拆分它。遍历从 0 到 2 N -1 的值并检查从 0 到 N-1 的每个位。如果该位是 1 - 大写 ( Char.ToUpper()) 对应于该位的字母。
这种方法比递归算法更好，因为它不容易在长字上发生堆栈溢出。
假设：
1）你不太关心这是O（n * 2 ^ n）......虽然我很想知道：这类问题的最佳渐近运行时间是多少？
2）你的输入都是小写的。
3) 您的输入长度小于 32 个字符。（排列计数器中可用位的数量，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;
}
注意：我没有编译或测试过这段代码。这也实现了上面建议的尖牙的按位比较。