[代码共享] 一些集合算法...

ChrisAK 2011-06-10 01:00:59
加精
最近好像看到好几个集合算法相关的帖子...
想想把这个文件共享下好了:)

SetAlgorithms.cs
using System;

namespace Rabbit.Tools

{

    public static class SetAlgorithms

    {

        /// <summary>

        /// 集合算法的回调

        /// </summary>

        /// <param name="result">运算结果</param>

        /// <param name="length">运算结果有效长度</param>

        /// <returns>控制算法是否继续,如果要结束算法,返回false</returns>

        /// <remarks>回调中不要修改result中的值,否则可能引起不可预知的后果</remarks>

        public delegate bool SetAlgorithmCallback (int[] result,int length);



        //argument check for arrangement and combination

        static bool CheckNM(int n, int m)

        {

            if (m > n || m < 0 || n < 0)

                throw new ArgumentException();



            if (m == 0 || n == 0)

                return false;

            return true;

        }



        static bool Arrangement(int n, int rlen, int[] result, SetAlgorithmCallback callback)

        {

            if (rlen == result.Length)

                return callback(result, rlen);



            for (var i = 0; i < n; ++i)

            {

                //skip used element

                bool skip = false;

                

                for (var j = 0; j < rlen; ++j)

                {

                    if (result[j] == i)

                    {

                        skip = true;

                        break;

                    }

                }



                if (skip)

                    continue;

                //set element index

                result[rlen] = i;

                //recurrent next

                if (!Arrangement(n, rlen + 1, result, callback))

                    return false;

            }

            return true;

        }

        /// <summary>

        /// 求排列A(n,m)

        /// </summary>

        /// <param name="n">集合元素个数</param>

        /// <param name="m">取出元素个数</param>

        /// <param name="callback">回调</param>

        public static void Arrangement(int n, int m, SetAlgorithmCallback callback)

        {



            if (!CheckNM(n, m))

                return;



            var result = new int[m];

            for (var i = 0; i < n; ++i)

            {

                result[0] = i;

                if (!Arrangement(n, 1, result, callback))

                    return;

            }

        }



        static bool Combination(int n,int m, int i, int rlen, int[] result, SetAlgorithmCallback callback)

        {

            if (rlen == m)

                return callback(result, rlen);



            for (var j = ++i; j < n; ++j)

            {

                result[rlen] = j;

                if (!Combination(n,m, j, rlen + 1, result, callback))

                    return false;

            }

            return true;

        }

        /// <summary>

        /// 求组合C(n,m)

        /// </summary>

        /// <param name="n">集合元素个数</param>

        /// <param name="m">取出元素个数</param>

        /// <param name="callback">回调</param>

        public static void Combination(int n, int m, SetAlgorithmCallback callback)

        {

            if (!CheckNM(n, m))

                return;



            int[] result;



            result = new int[n];

            for (var i = 0; i < n; ++i)

            {

                result[0] = i;



                if (!Combination(n,m, i, 1, result,callback))

                    return;

            }

        }



        static bool SubSet(int n, int i, int rlen, int[] result, SetAlgorithmCallback callback)

        {

            if (!callback(result, rlen))

                return false;



            if (rlen == n - 1)

                return true;



            for (var j = ++i; j < n; ++j)

            {

                result[rlen] = j;

                if (!SubSet(n, j, rlen + 1, result, callback))

                    return false;

            }

            return true;

        }

        /// <summary>

        /// 求除空集外包含n个元素的集合的真子集

        /// </summary>

        /// <param name="n">集合元素个数</param>

        public static void SubSet(int n, SetAlgorithmCallback callback)

        {

            if (n < 0)

                throw new ArgumentException();

            if (n == 0)

                return;



            var result = new int[n - 1];

            for (var i = 0; i < n; ++i)

            {

                result[0] = i;

                if (!SubSet(n, i, 1, result, callback))

                    return;

            }

        }



        static bool CartesianProduct(int[] sets, int i, int[] result, SetAlgorithmCallback callback)

        {

            for (var j = 0; j < sets[i]; ++j)

            {

                result[i] = j;

                if (i == sets.Length - 1)

                {

                    if (!callback(result, result.Length))

                        return false;

                }

                else

                {

                    if (!CartesianProduct(sets, i + 1, result, callback))

                        return false;

                }

            }

            return true;

        }

        /// <summary>

        /// 求集合笛卡尔积

        /// </summary>

        /// <param name="sets">包含集合元素个数的数组</param>

        /// <param name="callback">回调函数</param>

        public static void CartesianProduct(int[] sets, SetAlgorithmCallback callback)

        {

            int[] result = new int[sets.Length];

            CartesianProduct(sets, 0, result, callback);

        }

    }

}


提供了以下几个通用的算法:

求排列
求组合
求集合真子集
求集合笛卡尔积

没啥技术性,主要是泛用性.

例如:
已知3个集合
{"帽子1","帽子2","帽子3"}
{"上衣1","上衣2","上衣3"}
{"裤子a","裤子b"}

求所有的着装组合.可以使用笛卡尔积算法:

            var c1= new string[]{"帽子1","帽子2","帽子3"};

            var c2 = new string[] { "上衣1", "上衣2", "上衣3" };

            var c3 = new string[] { "裤子a", "裤子b" };

            SetAlgorithms.CartesianProduct(new int[] { c1.Length, c2.Length, c3.Length }, (result, len) =>

            {

                Console.WriteLine("{0},{1},{2}", c1[result[0]], c2[result[1]], c3[result[2]]);

                return true;

            });

输出
帽子1,上衣1,裤子a

帽子1,上衣1,裤子b

帽子1,上衣2,裤子a

帽子1,上衣2,裤子b

帽子1,上衣3,裤子a

帽子1,上衣3,裤子b

帽子2,上衣1,裤子a

帽子2,上衣1,裤子b

帽子2,上衣2,裤子a

帽子2,上衣2,裤子b

帽子2,上衣3,裤子a

帽子2,上衣3,裤子b

帽子3,上衣1,裤子a

帽子3,上衣1,裤子b

帽子3,上衣2,裤子a

帽子3,上衣2,裤子b

帽子3,上衣3,裤子a

帽子3,上衣3,裤子b


其余的调用方法也类似.
举个更实际的例子,例如这帖的问题:
http://topic.csdn.net/u/20110527/15/3f9ef827-988c-454c-8bf4-c44f48ec1fa2.html

例如，商品属性：

品牌： 海尔 LG 三星 索尼 夏普 TCL 创维 长虹 飞利浦 康佳

尺寸： 60寸以上 55寸 52寸 5 0寸 47寸 46寸 42寸

液晶面板 ： IPS硬屏面板 VA面板 ASV面板 黑水晶面板 X-GEN超晶面板


每个属性都是一个集合，列举出所有筛选可能，包括只选一个条件，现在是3个属性，如果属性个数不确定怎么实现

对于这个问题.除去有未选的情况,我可以将结果集看做几个集合的笛卡尔集.
那对于未选状态怎么处理呢?我可以人为的为它的头部加上一个"未选"元素.例如品牌就变成了:

未选 海尔 LG 三星 索尼 夏普 TCL 创维 长虹 飞利浦 康佳

var bands = new string[] { "海尔", "LG", "三星", "索尼", "夏普", "TCL", "创维", "长虹", "飞利浦", "康佳" };



            var size = new string[] { "60寸以上", "55寸", "52寸", "50寸", "47寸", "46寸", "42寸" };



            var types = new string[] {"IPS硬屏面板", "VA面板", "ASV面板", "黑水晶面板", "X-GEN超晶面板" };



            var array = new string[][] { bands, size, types };

            SetAlgorithms.CartesianProduct(new int[] { bands.Length + 1, size.Length + 1, types.Length + 1 }, (result, len) =>

            {

                for (var i = 0; i < array.Length; ++i)

                {

                    if (result[i] == 0)//跳过"未选"

                        continue;

                    Console.Write("{0} ", array[i][result[i]-1]);

                }

                Console.WriteLine();

                return true;

            });

输出....太长,有兴趣的可以自己编译跑一下看看.
...全文
4036 217 打赏 收藏 转发到动态 举报
写回复
用AI写文章
217 条回复
切换为时间正序
请发表友善的回复…
发表回复
落魄骚年 2012-03-14
  • 打赏
  • 举报
 回复
技术有限，虽然看得不太懂，但是感觉很牛逼
koumingjie 2011-09-05
  • 打赏
  • 举报
 回复
收藏了
yayiba2020 2011-09-05
  • 打赏
  • 举报
 回复
学习算法
星小野 2011-08-30
  • 打赏
  • 举报
 回复
强烈支持[Quote=引用 1 楼 bdmh 的回复:]
支持，必须支持
[/Quote]
mnljf 2011-08-27
  • 打赏
  • 举报
 回复
挺有用的东西
louisit 2011-08-06
  • 打赏
  • 举报
 回复
强帖留名 支持分享 研究研究
End 2011-07-26
  • 打赏
  • 举报
 回复
好帖，绝对的好帖，刚解决了困扰了1整天的问题，谢了
xufeng1231985 2011-06-21
  • 打赏
  • 举报
 回复
研究一下！！！！！！
Zach_ZhouY 2011-06-21
  • 打赏
  • 举报
 回复
算法是一定要看的
yuxiangqq 2011-06-21
  • 打赏
  • 举报
 回复
学到了
seven_and_one 2011-06-21
  • 打赏
  • 举报
 回复
mark一下，将来可能用上
a474841314 2011-06-21
  • 打赏
  • 举报
 回复
mark
lishaowen1314 2011-06-21
  • 打赏
  • 举报
 回复
学习学习，都来看看
zl194 2011-06-20
  • 打赏
  • 举报
 回复
学习。学习。学习。学习。学习。学习。学习。学习。
aoguanhai 2011-06-20
  • 打赏
  • 举报
 回复
good~~
netaass123 2011-06-20
  • 打赏
  • 举报
 回复
此贴不能沉！
顶起！
BATTLERxANGE 2011-06-20
  • 打赏
  • 举报
 回复
mark
luluyy 2011-06-20
  • 打赏
  • 举报
 回复
收藏 回复内容太短了！
linqiqing 2011-06-20
  • 打赏
  • 举报
 回复
看看！！！
偶像-阿里巴巴-马云 2011-06-20
  • 打赏
  • 举报
 回复
路过，学习中。。。
加载更多回复（181）
密码学实验 | shamir门限秘密共享算法（python）
shamir门限秘密共享算法一、实验原理二、实验代码三、实验结果四、实验总结 一、实验原理 (t，n)门限秘密共享方案，该方案是Shamir和Blakley在1979年各自独立地提出。 (t，n)门限方案是基于(t.n)门限访问结构上的秘密共享方案，而(t，n)门限访问结构包括所有t个或t个以上的参与者子集所构成的集合。 1. Shamir (t，n)门限方案是通过构造一个t-1次多项式，并将需共享的秘密作为该多项式的常数项，将秘密分成n部分分别给n个参与者，使t个参与者联合可恢复秘密，但少于t个参与者联合
在线机器学习算法及其伪代码
机器学习：需要从已知的数据 学习出需要的模型 在线算法：需要及时处理收集的数据，并给出预测或建议结果，并更新模型 通用的在线学习算法步骤如下： 1. 收集和学习现有的数据 2. 依据模型或规则，做出决策，给出结果 3. 根据真实的结果，来训练和学习规则或模型 常用的在线学习算法： Perceptron: 感知器 PA: passive aggressive Perceptron PA-I PA-II ...
基本粒子群算法小结及算法实例（附Matlab代码）
1、基本粒子群算法 假设在一个 D 维的目标搜索空间中，有 N 个粒子组成一个群落，其中第i 个 粒子表示为一个 D 维的向量： $$ X_i=(x_{i1},x_{i2}, \cdots ,x_{iD}), \quad i=1,2, \cdots ,N \quad \text {(1)} $$ 第i个粒子的“飞行”速度也是一个 D 维的向量，记为: $$ V_i=(v_{i1},v_{i2}, \cdots ,v_{iD}), \quad i=1,2, \cdots ,N \quad \te...
银行家算法——C++实现 [ 开源代码 + 详细解析 ]
关键词：运行结果图、银行家算法简介(Dijkstra在1965年提出)、安全状态、算法实质与思想、算法所需的相关数据结构、算法的设计思想、算法样例、完整代码 —— C++版本
自古帝王多短命，假如皇帝也懂负载均衡算法...
大家都知道古代皇帝各个都是后宫佳丽三千，而皇帝身上都天然的带着雨露均沾的精神，不想单独的宠爱一人！ 弱水三千，又怎舍得只取一瓢饮？据传皇帝们晚上睡觉个个都怕冷，因此每晚都需要有人侍寝，那么这么多后宫，该翻谁牌子、怎么分配侍寝名额呢？ 还别说，皇帝行房事竟还挺讲究的！早在《春秋》就有记载“晦阴惑疾，明谣心疾，以辟六气”。 九嫔以下，每九人中进御一人，八十一女御占九个晚上，世妇二十七人占三个...
C#

110,525

社区成员

642,571

社区内容

发帖
与我相关
我的任务
社区描述
.NET技术 C#
社区管理员
  • C#
  • Web++
  • by_封爱
加入社区
  • 近7日
  • 近30日
  • 至今

加载中

查看更多榜单
社区公告

让您成为最强悍的C#开发者

试试用AI创作助手写篇文章吧

+ 用AI写文章