组合算法纠错（高分）

Question

问题描述：http://topic.csdn.net/u/20110615/10/a913bb78-3303-46fb-bc47-820f7489cb40.html
算法初稿（存在问题，请纠错，高分答谢）：public static string Translate(string type, string str)
        {
            StringBuilder sb = new StringBuilder();  
            IList<int> typeList = AnalyzeType(type);  
            foreach (int numType in typeList)  
            {
                BuildResult(numType, AnalyzeStr(str), sb); 
            }
            return sb.ToString();
        }
        public static IList<int> AnalyzeType(string type) 
        { 
            IList<int> typeList = new List<int>();
            Regex reg = new Regex(@"^\d{1}$");           
            Array arr = type.ToArray(); 
            foreach (var character in arr)
            { 
                if (reg.IsMatch(character.ToString())) 
                { 
                    typeList.Add(int.Parse(character.ToString()));
                } 
            } 
            return typeList;
        }        public static IList<string> AnalyzeStr(string str) 
        {
            IList<string> list = new List<string>();
            Regex reg = new Regex(@"^\d{6}$");
            string[] content = str.Split(','); 
            foreach (string everyStr in content)
            {
                if (reg.IsMatch(everyStr)) 
                { 
                    list.Add(everyStr); 
                } 
            } 
            return list; 
        }        public static void BuildResult(int type, IList<string> contentList, StringBuilder sb) 
        {
            if (contentList.Count != 0) 
            {
                string code = contentList.First();
                contentList.Remove(code); 
                Dictionary<int, List<string>> dictionary = new Dictionary<int, List<string>>(); 
                for (int j = 1; j < type; j++) 
                { 
                    string[] list = new string[contentList.Count]; 
                    contentList.CopyTo(list, 0); 
                    List<string> copyList = list.ToList<string>(); 
                    dictionary.Add(j, copyList); 
                } 
                while (dictionary.Values.Last().Count > 0) 
                { 
                    bool addInsb = false;
                    StringBuilder newSb = new StringBuilder(); 
                    newSb.Append("+").Append(code); 
                    foreach (List<string> list in dictionary.Values) 
                    { 
                        if (list != null && list.Count > 0) 
                        { 
                            string listFir = list.First(); //前3位相同的则为一组 
                            if (!list.First().Substring(0, 3).Equals(code.Substring(0, 3))) 
                            { 
                                newSb.Append("+").Append(list.First());
                                addInsb = true; 
                            } 
                            foreach (List<string> listA in dictionary.Values)
                            { 
                                listA.Remove(listFir); 
                            } 
                        } 
                        if (!addInsb) 
                            break; 
                    } 
                    newSb.Append("|"); 
                    if (addInsb)
                    {
                        sb.Append(newSb);
                    }
                    //因为移出了每次的第一个，必须使得循环从头开始
                    BuildResult(type, contentList, sb);
                }
            }
        }

Answer 1

循环次数应该是根据type参数而定吧，怎么能说说二重循环呢？

Answer 2

不就是求组合数么？先去看看这个帖子
http://topic.csdn.net/u/20100827/11/b1b5d0ec-b453-41c0-be56-7ad467755da4.html
然后先把你要求组合的数转换成数组A，想取2个做组合就调用
var result = A.Combination(2, (s1, s2) => s1 + "," + s2).ToList()
result就是一个存放结果的list,每个组合的字符串用逗号隔开，如果想换个输出格式，改一下(s1, s2) => s1 + "," + s2 就可以了。
最后检查下结果是不是对。

Answer 3

看了你那个帖子，就是要去掉前三位重复的，组合后做个过滤就行了：
var result = A..Combination(2, (s1, s2) => s1.StartsWith(s2.Substring(0, 3)) ? null : s1 + "," + s2).Where(s => !String.IsNullOrEmpty(s)).ToList()

Answer 4

原字符串：ostr="001001,001002,001003,002001,002002,002003,003002,003004,004001,004002"
转成数组：Array：
001001,001002,001003
002001,002002,002003
003002,003004
004001,004002
从每一行中取一个出来组合

Answer 5

public static string Translate(string type, string str)
        {
            StringBuilder sb = new StringBuilder();  
            IList<int> typeList = AnalyzeType(type);  
            foreach (int numType in typeList)  
            {
                BuildResult(numType, AnalyzeStr(str), sb); 
            }
            return sb.ToString() + "\n" + (sb.ToString().Split('+').Length - 1).ToString();
        }
        public static IList<int> AnalyzeType(string type) 
        { 
            IList<int> typeList = new List<int>();
            Regex reg = new Regex(@"^\d{1}$");           
            Array arr = type.ToArray(); 
            foreach (var character in arr)
            { 
                if (reg.IsMatch(character.ToString())) 
                { 
                    typeList.Add(int.Parse(character.ToString()));
                } 
            } 
            return typeList;
        }        public static IList<string> AnalyzeStr(string str) 
        {
            IList<string> list = new List<string>();
            Regex reg = new Regex(@"^\d{6}$");
            string[] content = str.Split(','); 
            foreach (string everyStr in content)
            {
                if (reg.IsMatch(everyStr)) 
                { 
                    list.Add(everyStr); 
                } 
            }
            return list;
        }        public static void BuildResult(int type, IList<string> contentList, StringBuilder sb) 
        {
            if (contentList.Count != 0) 
            {
                List<string> li = GetCombinationF(contentList, type);
                foreach (string str in li)
                {
                    string[] strArray = str.Split(',');
                    if (hasSame(strArray))
                        continue;
                    else
                    {
                        sb.Append(str).Append("+");
                    }
                }
            }
        }        public static bool hasSame(string[] strArray)
        {
            string start = string.Empty;
            for (int i = 0; i < strArray.Length; i++)
            {
                start = strArray[i].Substring(0, 3).ToString();
                for (int j = i + 1; j < strArray.Length; j++)
                {
                    if (start == strArray[j].Substring(0, 3))
                        return true;
                }
            }
            return false;
        }
        #region 组合算法(非递归方法)
        public static List<string> GetCombinationF(IList<string> strArray, int selectCount)
        {
            int totalCount = strArray.Count;
            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++)
                {
                    if ((selectCount - i) == 1)
                        s += strArray[currentSelect[i]];
                    else
                        s += strArray[currentSelect[i]] + ",";
                }
                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;
        }
        #endregion