(转)一维字符串数组之间组合问题的C#实现

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› Node.js›Node.js教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

如题，最近需要处理一些字符串数组之间相互无重组合的实际问题。
把问题抽象出来，实际就是数学中的排列组合问题，思想很简单，只是在实现上着实花了一些功夫，而且代码尚需进一步优化，写下来希望能和大家一起探讨，欢迎大家提建议，以使程序能进一步优化。
问题描述：
假设现有三组字符，如下
{k1,k2},
{k3,k4},
{k5}
要求三组数据组合，组合的每一个结果必须包含三组中的字符，且不重复。
针对这种少量的数组，通过排列组合我们可以计算出组合数量
N = 2*2*1 = 4 （种）
结果如下：
k5k3k1
k5k4k1
k5k3k2
k5k4k2
思想很简单的，我实际问题抽象成了二维数组，实际就是一维数组中n个一维数组的组合问题。
但是在使用C#实现时，走了不少弯路，个人觉得代码冗长了，需要改善的地方很多，
我想集众人的智慧肯定能获得一个更加精悍、性能更优的代码！
这里直接是建的控制台应用程序
程序如下(关键之处程序中已加注释)：

using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace testString
{
    /// <summary>
    /// 一维数组之间组合问题的C#实现
    /// Author:Lucky Hu
    /// Date:2012-05-08
    /// </summary>
    class Program
    {
        static void Main(string[] args)
        {
            //构造一个二维数组
            Dictionary<string, string> dk = new Dictionary<string, string>();
            dk.Add("k1", "A");
            dk.Add("k2", "A");
            dk.Add("k3", "B");
            dk.Add("k4", "B");
            dk.Add("k5", "C");
            //dk.Add("k6", "C");
            //dk.Add("k7", "D");
            //dk.Add("k8", "D");
            //dk.Add("k9", "E");
            List<string> s3 = new List<string>();
            List<List<string>> s2 = new List<List<string>>();
            foreach (var k in dk)
            {
                Console.WriteLine("Key:{0},Value:{1}", k.Key, k.Value);
                string keys = "";
                var key_by_value = dk.Where(p => p.Value == k.Value).Select(p => p.Key);
                List<string> dd = new List<string>();
                foreach (var key in key_by_value)
                {
                    keys += "," + key;
                }
                string newkeys = keys.Remove(0, 1);
                if (s3.Contains(newkeys) == false)
                {
                    s3.Add(newkeys);
                }
            }
            foreach (var v in s3)
            {
                string[] split = new string[100];//全局
                if (v.Contains(","))
                {
                    //含逗号
                    split = v.Split(new char[] { ',' });
                }
                else
                {
                    //不含逗号
                    split[0] = v;
                }
                List<string> newSplit = new List<string>();
                //////////////因为C#不自带获取数组真实长度的函数，暂时没有想到更好的办法了
                for (int n = 0; n < split.Length; n++)
                {
                    if (split[n] != null)
                    {
                        newSplit.Add(split[n]);
                    }
                }

                List<string> s4 = new List<string>();
                for (int i = 0; i < newSplit.Count; i++)
                {
                    //s4.Add(split[i]);
                    s4.Add(newSplit[i]);
                }
                s2.Add(s4);//构造数组结束
            }
            List<List<string>> res = new List<List<string>>();
            res = combine(s2, 0);
            Console.WriteLine("组合结果:");
            foreach (var r in res)
            {
                foreach (var rr in r)
                {
                    Console.WriteLine(rr);
                }
            }
            Console.ReadKey();
        }
        /// <summary>
        /// 组合函数（递归）
        /// </summary>
        /// <param name="a">一个二维数组</param>
        /// <param name="idx">索引</param>
        /// <returns>返回一个二维数组</returns>
        public static List<List<string>> combine(List<List<string>> a, int idx)
        {
            List<List<string>> b = new List<List<string>>();
            List<List<string>> s = new List<List<string>>();
            if (idx >= (a.Count) - 1)
            {
                s.Add(a[idx]);
                return s;
            }
            else
            {
                List<List<string>> low_b = combine(a, idx + 1);
                foreach (var ch in a[idx])
                {
                    foreach (var low_arr in low_b)
                    {
                        foreach (var tt in low_arr)
                        {
                            string t = "";
                            t += (tt + ch);
                            List<string> s5 = new List<string>();
                            s5.Add(t);
                            b.Add(s5);
                        }
                    }
                }
            }
            return b;
        }
    }
}