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

Radinka ·

更新时间:2024-11-14

· 663 次阅读

可以扩展到多个集合的情况。类似的例子有，如果A表示某学校学生的集合，B表示该学校所有课程的集合，则A与B的笛卡尔积表示所有可能的选课情况

代码如下:
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;

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

您可能感兴趣的文章:C# 生成高质量缩略图程序—终极算法C#的3DES加密解密算法实例代码C#常见算法面试题小结asp.net(c#)两种随机数的算法，可用抽考题c#汉诺塔的递归算法与解析C#加密算法汇总(推荐)基于C#代码实现九宫格算法横竖都等于4c# 实现MD5,SHA1,SHA256,SHA512等常用加密算法源代码基于私钥加密公钥解密的RSA算法C#实现方法c#哈希算法的实现方法及思路C#数据结构与算法揭秘五栈和队列C#实现的海盗分金算法实例

C# 笛卡尔 net 算法 .NET list

1024 个赞