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

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

C#教程相关栏目本月热门文章