题目来自http://topic.csdn.net/u/20090219/17/febac6e8-ab35-4dda-ad73-ad7314ed487e.html上面的一题
题目： 给定一个字符串，里面用空格分开为6个或者更多的子单元，如：01 02 03 04 05 06 07 08... 写一函数，返回任6个进行组合的所有字符串。(
对于8选6下面是我利用位操作的方法实现
using System;
namespace Test
{
class Program
{
static void Main(string[] args)
{
string str = "01 02 03 04 05 06 07 08";
string[] set = str.Split(' ');
int n = set.Length;
int m = 6;
int min = (0x01 << m) - 1;//00111111
int max = min << (n - m);//11111100
int j;
int k;
for (int i = min; i <= max; i++)
{
j = 0;
k = i;
while (k>0)
{
j += (int)(k & 0x01);
k >>= 1;
if (j > m)
{
break;
}
}
if (j == m)
{
k = 0x01;
for (int l = n-1; l>=0; l--)
{
if ((k & i) == k)
{
Console.Write(set[l] + "\t");
}
k <<=1;
}
Console.WriteLine();
}
}
}
}
}输出：
08 07 06 05 04 03
08 07 06 05 04 02
08 07 06 05 03 02
08 07 06 04 03 02
08 07 05 04 03 02
08 06 05 04 03 02
07 06 05 04 03 02
08 07 06 05 04 01
08 07 06 05 03 01
08 07 06 04 03 01
08 07 05 04 03 01
08 06 05 04 03 01
07 06 05 04 03 01
08 07 06 05 02 01
08 07 06 04 02 01
08 07 05 04 02 01
08 06 05 04 02 01
07 06 05 04 02 01
08 07 06 03 02 01
08 07 05 03 02 01
08 06 05 03 02 01
07 06 05 03 02 01
08 07 04 03 02 01
08 06 04 03 02 01
07 06 04 03 02 01
08 05 04 03 02 01
07 05 04 03 02 01
06 05 04 03 02 01
思路是从最小含6个“1”的00111111到最大的11111100，只有6个1,即按位判断为1输出，
上面我用的是int,
现在问题来了，如果给出的组合元素个数超过32,这样改成long
但是甚至超过64或更大呢，如何利用这个思路呢？
题目： 给定一个字符串，里面用空格分开为6个或者更多的子单元，如：01 02 03 04 05 06 07 08... 写一函数，返回任6个进行组合的所有字符串。(
对于8选6下面是我利用位操作的方法实现
using System;
namespace Test
{
class Program
{
static void Main(string[] args)
{
string str = "01 02 03 04 05 06 07 08";
string[] set = str.Split(' ');
int n = set.Length;
int m = 6;
int min = (0x01 << m) - 1;//00111111
int max = min << (n - m);//11111100
int j;
int k;
for (int i = min; i <= max; i++)
{
j = 0;
k = i;
while (k>0)
{
j += (int)(k & 0x01);
k >>= 1;
if (j > m)
{
break;
}
}
if (j == m)
{
k = 0x01;
for (int l = n-1; l>=0; l--)
{
if ((k & i) == k)
{
Console.Write(set[l] + "\t");
}
k <<=1;
}
Console.WriteLine();
}
}
}
}
}输出：
08 07 06 05 04 03
08 07 06 05 04 02
08 07 06 05 03 02
08 07 06 04 03 02
08 07 05 04 03 02
08 06 05 04 03 02
07 06 05 04 03 02
08 07 06 05 04 01
08 07 06 05 03 01
08 07 06 04 03 01
08 07 05 04 03 01
08 06 05 04 03 01
07 06 05 04 03 01
08 07 06 05 02 01
08 07 06 04 02 01
08 07 05 04 02 01
08 06 05 04 02 01
07 06 05 04 02 01
08 07 06 03 02 01
08 07 05 03 02 01
08 06 05 03 02 01
07 06 05 03 02 01
08 07 04 03 02 01
08 06 04 03 02 01
07 06 04 03 02 01
08 05 04 03 02 01
07 05 04 03 02 01
06 05 04 03 02 01
思路是从最小含6个“1”的00111111到最大的11111100，只有6个1,即按位判断为1输出，
上面我用的是int,
现在问题来了，如果给出的组合元素个数超过32,这样改成long
但是甚至超过64或更大呢，如何利用这个思路呢？
算法原理见链接：
http://www.yuanma.org/data/2006/0529/article_506.htm
static void Main(string[] args)
{
string[] data={"01","02","03","04","05","06","07","08","09","10"};
GetZhuHe(data,6);
Console.Read();
}
static void GetZhuHe(string[] data,int count)
{
int len=data.Length;
string start="1".PadRight(count,'1').PadRight(len,'0');
while(start!=string.Empty)
{
for(int i=0;i<len;i++)
if(start[i]=='1') Console.Write(data[i]+"\t");
Console.WriteLine();
start=GetNext(start);
} } static string GetNext(string str)
{
string next=string.Empty;
int pos=str.IndexOf("10");
if(pos<0) return next;
else if(pos==0) return "01"+str.Substring(2);
else
{
int len=str.Length;
next=str.Substring(0,pos).Replace("0","").PadRight(pos,'0')+"01";
if(pos<len-2) next+=str.Substring(pos+2);
}
return next;
}
期待有更优的方法。
比如30,可以提高的百分比应当不到10%,输出部分如果是输出到StringBuilder,也许优化还有一定意义,输出到屏幕就无所谓了如果是输出到char[]应当是最快的,不过要提前定义好char[]的大小,应该会比StringBuilder好一些!http://topic.csdn.net/u/20090106/14/7e1d07fe-32f0-4753-853a-76772b05aaa7.html最近调论这个问题的确实不少!
static void Main(string[] args)
{
createPerArray(new string[] { "00", "01", "02", "03", "04", "05", "06", "07" }, 6);
} static void createPerArray(string[] strArray, int selectCount)
{
int totalCount = strArray.Length;
int[] currentSelect = new int[selectCount];
int last = selectCount - 1; //付初始值
for (int i = 0; i < selectCount; i++)
currentSelect[i] = i; while (true)
{
//输出部分,生成的时候从0计数,所以输出的时候+1
for (int i = 0; i < selectCount; i++)
Console.Write(strArray[currentSelect[i]]); Console.WriteLine(); //如果不进位
if (currentSelect[last] < totalCount - 1)
currentSelect[last]++;
else
{
//进位部分
int position = last; while (position > 0 && currentSelect[position - 1] == currentSelect[position] - 1)
position--; if (position == 0)
return; currentSelect[position - 1]++; for (int i = position; i < selectCount; i++)
currentSelect[i] = currentSelect[i - 1] + 1;
}
}
}
{
string[] data = { "01", "02", "03", "04", "05", "06", "07", "08", "09", "10", "11", "12", "13", "14", "15", "16", "17", "18", "19", "20", "21", "22", "23", "24", "25", "26", "27", "28", "29", "30", "31", "32", "33", "34", "35", "36", "37", "38", "39", "40"};
DateTime dt1 = DateTime.Now;
GetSelectN(data, 6);
DateTime dt2 = DateTime.Now;
Console.WriteLine((dt2 - dt1).TotalMilliseconds);
Console.ReadLine();
} static void GetSelectN(string[] data,int count)
{
Dictionary<string, int> dic = new Dictionary<string, int>();
for (int i = 0; i < data.Length; i++)
{
dic.Add(data[i], i);
}
SelectN(dic,data,count,1);
} static void SelectN(Dictionary<string, int> dd, string[] data, int count, int times)
{
Dictionary<string, int> dic = new Dictionary<string, int>();
foreach (KeyValuePair<string, int> kv in dd)
{
for (int i = kv.Value + 1; i < data.Length; i++)
{
if (times < count - 1)
dic.Add(kv.Key + "\t" + data[i], i);
//else Console.WriteLine(kv.Key + "\t" + data[i]);//不考虑输出，将此句注释掉
}
}
times++;
if (dic.Count > 0) SelectN(dic,data, count,times);
}
代码C(100,20) C(100,80)所花的时间是一样，其实我们应该考虑到这点：C(100,20)=C(100,80)
不过代码下完之后，不大看得懂）；大家可以参考一下
http://www.codeproject.com/KB/recipes/combinations.aspx还有一个用N层满N叉树的排列算法:
http://www.cnblogs.com/star65225692/archive/2008/04/14/1153112.html
6楼的算法很不错，效率挺高的了。确实没有去考虑C(100,20)=C(100,80)，其实C(100,80)就是C(100,20)的逆输出。
比如1楼的算法将if(start[i]=='1')改成if(start[i]=='0')就是了，只需在前面判断一下count的值是否比len/2大。
有些算法可能需要做比较大的改动。
有时间的话真想好好总结一下。。
应该相对还可以,但是算32取1的话,也要循环2^31 * 32次,中间有些判断可能是无用的,因此会让效率下降!min_jie给出的算法,本身属于挺经典的算法,效率也是很高的,但实际上是因为字符串操作的缘故拖累了算法的效率,
直接操作字符串,会造成效率比较大的降低。比如 int pos=str.IndexOf("10");字符串越长,这个效率越低,
因为每次都要从头开始搜索"01"可实际上,如果01在第10位,就要算10次,而实际上这个结果在LZ上一次拼凑字符串的时候,
就已经知道了.所以应该可以有改进的方法,比如用位运算,或添加一个变量保存计数......我给出的算法思路比较普通,不过在进位上处理上,对效率有些影响,从1-2-26-27-28-29-30 进位到1-3-4-5-6-7-8
需要循环5次作进位,又需要循环5次作赋值,所以会对效率有一定的影响。但好在进位的情况出现概率不太高，
因此影响相对有限，又因为输出的时候，实际上从第N到第N+1项，变化的往往只有1个选项（进位时除外），
而我的方法每次都要重新计算生成字符，这会对效率产生比较大的影响，应该有可以优化的地方。
2.代码中直接console.write，这是非常影响效率的，所以实际运行速度要比各位的算法快得多。
GetCombinationF1为我的方法
GetCombinationF2为litaoye的方法
GetCombinationF3为1L的方法
GetCombinationF4为min_jie的方法using System;
using System.Collections.Generic;
using System.Diagnostics;
namespace Test
{
class Program
{
static void Main(string[] args)
{
int n = 40;
int m = 6;
string[] set = new string[n];
for (int i = 0; i < n; i++)
{
set[i] = i.ToString().PadLeft(2, '0');
}
List<string> result; GC.Collect();
Stopwatch watch = new Stopwatch();
using (new AutoWatch(watch))
{
//result = GetCombinationF1(set, m);//n=20 about 130ms;
//result = GetCombinationF2(set, m); //n=20 about 44ms, n=40 about 6s
//result = GetCombinationF3(set, m);//n=20 about 16ms n=40 about 2.5s
result = GetCombinationF4(set, m);//n=20 about 95ms n=40 about 13s
}
Console.WriteLine(watch.ElapsedMilliseconds); //print output
foreach (string s in result)
{
//Console.WriteLine(s);
}
} static List<string> GetCombinationF3(string[] data, int count)
{
Dictionary<string, int> dic = new Dictionary<string, int>();
List<string> output = new List<string>();
for (int i = 0; i < data.Length; i++)
{
dic.Add(data[i], i);
}
SelectN(dic, data, count, 1, ref output);
return output;
} static void SelectN(Dictionary<string, int> dd, string[] data, int count, int times, ref List<string> output)
{
Dictionary<string, int> dic = new Dictionary<string, int>();
foreach (KeyValuePair<string, int> kv in dd)
{
for (int i = kv.Value + 1; i < data.Length; i++)
{
if (times < count - 1)
{
dic.Add(kv.Key + "\t" + data[i], i);
}
else
{
output.Add(kv.Key + "\t" + data[i]);//不考虑输出，将此句注释掉
}
}
}
times++;
if (dic.Count > 0) SelectN(dic, data, count, times,ref output);
}
static List<string> GetCombinationF1(string[] set,int m)
{
int n = set.Length;
int min = (0x01 << m) - 1;//00111111
int max = min << (n - m);//11111100
int j;
int k;
List<string> output = new List<string>();
string s; for (int i = min; i <= max; i++)
{
j = 0;
k = i;
while (k > 0)
{
j += (int)(k & 0x01);
k >>= 1;
if (j > m)
{
break;
}
}
if (j == m)
{
s = "";
k = 0x01;
for (int l = n - 1; l >= 0; l--)
{
if ((k & i) == k)
{
s+=set[l] + "\t";
}
k <<= 1;
}
output.Add(s);
} }
return output;
}
static List<string> GetCombinationF2(string[] strArray, int selectCount)
{
int totalCount = strArray.Length;
int[] currentSelect = new int[selectCount];
int last = selectCount - 1;
List<string> output = new List<string>();
string s; //付初始值
for (int i = 0; i < selectCount; i++)
currentSelect[i] = i; while (true)
{
s = "";
//输出部分,生成的时候从0计数,所以输出的时候+1
for (int i = 0; i < selectCount; i++)
{
s += strArray[currentSelect[i]]+"\t";
}
output.Add(s); //如果不进位
if (currentSelect[last] < totalCount - 1)
currentSelect[last]++;
else
{
//进位部分
int position = last; while (position > 0 && currentSelect[position - 1] == currentSelect[position] - 1)
position--; if (position == 0)
break ; currentSelect[position - 1]++; for (int i = position; i < selectCount; i++)
currentSelect[i] = currentSelect[i - 1] + 1;
}
}
return output;
} static List<string> GetCombinationF4(string[] data, int count)
{
List<string> output = new List<string>();
int len = data.Length;
string start = "1".PadRight(count, '1').PadRight(len, '0');
string s;
while (start != string.Empty)
{
s = "";
for (int i = 0; i < len; i++)
if (start[i] == '1') s+=data[i] + "\t";
output.Add(s);
start = GetNext(start);
}
return output; } static string GetNext(string str)
{
string next = string.Empty;
int pos = str.IndexOf("10");
if (pos < 0) return next;
else if (pos == 0) return "01" + str.Substring(2);
else
{
int len = str.Length;
next = str.Substring(0, pos).Replace("0", "").PadRight(pos, '0') + "01";
if (pos < len - 2) next += str.Substring(pos + 2);
}
return next;
}
public sealed class AutoWatch : IDisposable
{
private Stopwatch watch; public AutoWatch(Stopwatch watch)
{
this.watch = watch;
watch.Start();
} void IDisposable.Dispose()
{
watch.Stop();
}
} }
}
n=40时，litaoye的方法没有min_jie的递归方法快
//result = GetCombinationF1(set, m);//n=15 8ms n=20 about 130ms;
//result = GetCombinationF2(set, m); //n=15 5ms,n=20 about 44ms, n=40 about 6s
//result = GetCombinationF3(set, m);//n=15,4ms,n=20 about 16ms n=40 about 2.5s
result = GetCombinationF4(set, m);//n=15 11ms,n=20 about 95ms n=40 about 13s
不过估计应该还是不如递归的方法，因为递归的方法基本上没有什么多余的运算，
唯一有些不足的地方在于内存占用较大，不过这是可以通过改变实现方法解决的，可以使用类似栈的方式。我不太清楚遍历dictionary的效率，按理说应该是个常数，但是究竟有多大还不太清楚。回过头来，.net里面的字符操作和linq的效率，倒是经常会超出我的估计。
应该比原来好一些，但也有许多不令人满意的地方，
如果想继续提高效率，恐怕需要从根上换一个方法了！
static void createPerArray(string[] strArray, int selectCount)
{
int totalCount = strArray.Length;
int[] currentSelect = new int[selectCount];
int last = selectCount - 1;
int position = 0; List<string> output = new List<string>();
string temp = "";
int position2 = 0; //付初始值
for (int i = 0; i < selectCount; i++)
{
currentSelect[i] = i;
if(i < selectCount - 1)
temp += strArray[currentSelect[i]];
} while (true)
{
output.Add(temp + strArray[currentSelect[last]]); //如果不进位
if (currentSelect[last] < totalCount - 1)
currentSelect[last]++;
else
{
//进位部分
position = last;
position2 = temp.Length - strArray[currentSelect[position - 1]].Length; while (currentSelect[position - 1] == currentSelect[position] - 1)
{
position--;
if (position == 0)
return;
position2 -= strArray[currentSelect[position - 1]].Length;
} currentSelect[position - 1]++;
temp = temp.Remove(position2) + strArray[currentSelect[position - 1]]; for (int i = position; i < selectCount; i++)
{
currentSelect[i] = currentSelect[i - 1] + 1;
if (i < selectCount - 1)
temp += strArray[currentSelect[i]];
}
}
}
}