请教一下字符串替换的算法问题？
有一个字符串"123457091"，我想把其中'1'->'2'，所以存在可能性为：123457092
223457091
223457092
请问下有没有高效的算法枚举出所有替换的可能性？ --------------------编程问答-------------------- 你把里面的1都找出来，记住位置，搞个排列组合吧 --------------------编程问答--------------------
我就是想知道，什么排列组合的算法高效呀？ --------------------编程问答-------------------- http://bbs.csdn.net/topics/390352804 --------------------编程问答-------------------- 想到一个奇葩的方法，效率不高的，不过奇葩，吃完饭实现看看 --------------------编程问答--------------------
写了个奇葩方法实现楼主的需求：
从楼主的需求知道，需要把1替换成2，如"123457091"就有如下替换情况：
"123457092"
"223457091"
"223457092"
把注意力放在需要替换的位置上，也就是把"11"其中的"1"替换成"2"，有以下3个替换组合：
"12"
"21"
"22"
观察替换结果与原来的"11"相比，把它们看作是整数，求差值：
12-11 = 01
21-11 = 10
22-11 = 11
以上结果先保留，再看一组数据，其中字符串有三个"1"的组合情况：
"112" "121" "211" "122" "212" "221" "222"
有7种组合情况（2的"1"个数次羃减一），再与111的差值如下：
112-111 = 001
121-111 = 010
122-111 = 011
211-111 = 100
212-111 = 101
221-111 = 110
222-111 = 111
由此可推知：
第N种组合的值为11...（字符串"11.."的整数表示）与N的二进制整数表示（非二进制转十进制）的值之和，如"111"求其第二种组合情况就是：
111+ToBinaryInt(2^2-1)，即 111+011 = 122
求得所有组合后，把每一个组合结果映射回字符串即可：
原字符串：123457091
组合数： 22
映射索引：{8,0}
替换结果：223457092
具体实现如下：
//把第N转换成二进制的整数表示 如3==>11 7==>111
static long ToBinaryInt(int dec)
{
long[] buffer = new long[(int)Math.Ceiling((double)dec / 2 + 0.5)];
long result = 0;
int r = dec;
int i = 0;
while (r > 0)
{
buffer[i++] = r % 2;
r = r / 2;
}
for (i = buffer.Length - 1; i >= 0; i--)
result = result * 10 + buffer[i];
return result;
}
//字符串的"1"的个数组成的整数
static long ToOnes(int counter)
{
long result = 0;
for (int i = counter - 1; i >= 0; i--)
result = result * 10 + 1;
return result;
}
//求字符串"1"-->"2"替换组合结果
static IList<string> GetCombinaStrings(string inputStr)
{
IList<string> combinStrings = new List<string>();
//获取所有"1"字符索引位置，用于映射
var indexs = inputStr.Select((a, index) => new { a, index }).Where(a => a.a == '1').ToList();
//"1"的个数组合成的整数
long oneCounter = ToOnes(indexs.Count);
//求所有组合结果
long[] binary = new long[(int)Math.Pow(2, indexs.Count) - 1];
for (int i = 0; i < binary.Length; i++)
binary[i] = oneCounter + ToBinaryInt(i + 1);
//根据组合结果映射回字符串
char[] buffer = inputStr.ToCharArray();
for (var i = 0; i < binary.Length; i++)
{
string temp = binary[i].ToString();
for (int j = 0; j < temp.Length; j++)
{
buffer[indexs[j].index] = temp[j];
}
combinStrings.Add(new string(buffer));
}
return combinStrings;
}
//测试
static void Main(string[] args)
{
string inputStr = "123457091";
IList<string> combinStrings = new List<string>();
combinStrings = GetCombinaStrings(inputStr);
Console.WriteLine("输入的字符串：" + inputStr);
foreach (string str in combinStrings)
Console.WriteLine(str);
inputStr = "1111";
combinStrings = GetCombinaStrings(inputStr);
Console.WriteLine("输入的字符串：" + inputStr);
foreach (string str in combinStrings)
Console.WriteLine(str);
Console.ReadLine();
}
测试结果：
总结：
无意想到的实现方法，就把它写写看。。 --------------------编程问答-------------------- 路过，顶，版主辛苦了
补充：.NET技术 , C#
