net C# 实现任意List的笛卡尔乘积算法

namespace 算法
{
    public static class 算法
    {
        /// <summary>
        /// 笛卡尔乘积
        /// </summary>
        public static List<List<T>> CartesianProduct<T>(this List<List<T>> lstSplit)
        {
            int count = 1;
            lstSplit.ForEach(item => count *= item.Count);
            //count = lstSplit.Aggregate(1, (result, next) => result * next.Count);

            var lstResult = new List<List<T>>();

            for (int i = 0; i < count; ++i)
            {
                var lstTemp = new List<T>();
                int j = 1;
                lstSplit.ForEach(item =>
                {
                    j *= item.Count;
                    lstTemp.Add(item[(i / (count / j)) % item.Count]);
                });
                lstResult.Add(lstTemp);
            }
            return lstResult;
        }
    }

    class Program
    {
        public static void Main()
        {
            StringDemo();
            根据Sector生成Routing的Demo();
            根据Sector生成Routing的Demo2();
        }

        /// <summary>
        /// 简单字符串 笛卡尔乘积
        /// </summary>
        private static void StringDemo()
        {
            var lstSource = new List<List<string>>
            {
                new List<string>() { "A","B","C"},
                new List<string>() { "D","E","F"},
                new List<string>() { "G","H","I"},
            };

            var sw = new Stopwatch();
            sw.Start();
            var lstResult = lstSource.CartesianProduct();
            Console.WriteLine(sw.Elapsed);
        }

        private static void 根据Sector生成Routing的Demo()
        {
            //默认允许输入多个BookingClass,表示使用任意一个都可以。
            var lstSectorDef = new List<Sector>
            {
                new Sector{ SeqNO=1, BookingClass="A/A1/A2"},
                new Sector{ SeqNO=2, BookingClass="B/B1/B2"},
                new Sector{ SeqNO=3, BookingClass="C/C1/C2"},
                //.....数量不定
            };

            var sw = new Stopwatch();
            sw.Start();

            var lstSectorGroup = new List<List<Sector>>();
            lstSectorDef.ForEach(item =>
            {
                var lstSector = new List<Sector>();
                foreach (var bookingClass in item.BookingClass.Split('/'))
                {
                    var sector = item.Clone();
                    sector.BookingClass = bookingClass;

                    lstSector.Add(sector);
                }
                lstSectorGroup.Add(lstSector);
            });

            var lstRouting = lstSectorGroup.CartesianProduct();

            Console.WriteLine(sw.Elapsed);
        }

        private static void 根据Sector生成Routing的Demo2()
        {
            //默认允许输入多个BookingClass,表示使用任意一个都可以。
            var lstSectorDef = new List<Sector>
            {
                new Sector{ SeqNO=1, BookingClass="A1/A2/A3"},
                new Sector{ SeqNO=2, BookingClass="B1/B2/B3"},
                new Sector{ SeqNO=3, BookingClass="C1/C2/C3"},
                //.....数量不定
            };

            var sw = new Stopwatch();
            sw.Start();

            var lstTemp = new List<List<string>>();
            lstSectorDef.ForEach(item =>
            {
                lstTemp.Add(item.BookingClass.Split('/').ToList());
            });

            var lstBookingClassGroup = lstTemp.CartesianProduct();

            var lstRouting = new List<List<Sector>>();
            for (int i = 0; i < lstBookingClassGroup.Count; i++)
            {
                var lstSector = new List<Sector>();
                for (int j = 0; j < lstSectorDef.Count; j++)
                {
                    var sector = lstSectorDef[j].Clone();
                    sector.BookingClass = lstBookingClassGroup[i][j];
                    lstSector.Add(sector);
                }
                lstRouting.Add(lstSector);
            }

            Console.WriteLine(sw.Elapsed);
        }

    }

    [DebuggerDisplay("Sector:SeqNO={SeqNO},BookingClass={BookingClass}")]
    public class Sector
    {
        public int SeqNO { get; set; }
        public string BookingClass { get; set; }

        public Sector Clone()
        {
            return this.MemberwiseClone() as Sector;
        }
    }
}