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

可以扩展到多个集合的情况。

类似的例子有,如果A表示某学校学生的集合,B表示该学校所有课程的集合,则A与B的笛卡尔积表示所有可能的选课情况


复制代码 代码如下:

using System;

using System.Collections.Generic;

using System.Diagnostics;

using System.Linq;

namespace 算法

{

    public static class 算法

    {

        ///


        /// 笛卡尔乘积

        ///


        public static List> CartesianProduct(this List> lstSplit)

        {

            int count = 1;

            lstSplit.ForEach(item => count *= item.Count);

            //count = lstSplit.Aggregate(1, (result, next) => result * next.Count);

            var lstResult = new List>();

            for (int i = 0; i < count; ++i)

            {

                var lstTemp = new List();

                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();

        }

        ///


        /// 简单字符串 笛卡尔乘积

        ///


        private static void StringDemo()

        {

            var lstSource = new List>

            {

                new List() { "A","B","C"},

                new List() { "D","E","F"},

                new List() { "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

            {

                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>();

            lstSectorDef.ForEach(item =>

            {

                var lstSector = new List();

                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

            {

                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>();

            lstSectorDef.ForEach(item =>

            {

                lstTemp.Add(item.BookingClass.Split('/').ToList());

            });

            var lstBookingClassGroup = lstTemp.CartesianProduct();

            var lstRouting = new List>();

            for (int i = 0; i < lstBookingClassGroup.Count; i++)

            {

                var lstSector = new List();

                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;

        }

    }

}

0.210094s