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;
        }
    }
}