作者ssccg (23)
看板C_Sharp
标题Re: [问题] 不重覆的排列组合
时间Fri Jun 8 14:03:42 2012
※ 引述《dlikeayu (太阳拳vs野球拳)》之铭言：
: ※ [本文转录自 Prob_Solve 看板 #1Fq9QlzU ]
: 作者: dlikeayu (太阳拳vs野球拳) 看板: Prob_Solve
: 标题: [问题] 不重覆的排列组合
: 时间: Thu Jun 7 19:55:22 2012
: 有个问题想要请较大家
: 我有两组SET
: 甲 {A,B,C}优先权低
: 乙{A,D,E}优先权高
: 然後我有一串值
: {B,C,E,B,A,D,E}
: 我要从中选出来
: 甲或乙各有几组
: 被选走的就不能再被用
: 所以要是乙跟甲都能组合的话
: 乙会优先抽走
: 因为值很少
: 可以自己算出
: 甲 0 组
: 乙 1 组
: 剩BBCE
: 请问用算的这种有什麽演算法能适用解决呢？
1F：→ ssccg:既然有优先顺序，不就算出最多能抽几组乙，减掉这数量再算06/07 20:13
2F：→ ssccg:最多几组甲就好了?06/07 20:13
: 如果这是个function ，那要怎麽知道有几组乙(不重覆)，asp.net的方法我不太熟
: 然後去执行交集运算C#(刚从数学版得到的资讯 )几次
: http://msdn.microsoft.com/zh-tw/library/system.linq.enumerable.except.aspx
: 又集合了几个网友的资讯
: C# ASP.NET 有 counting sort的函式可用吗？
: 先排出优先权最高的set放进一List或array
: 然後再counting sort知道有n组 乙set
: 差集运算 n 次
: 下一个set
: loop
如果你只是要算数量
其实不需要管set，直接根据数量统计就好了
先统计各个值可被取的数量
然後依优先顺序对每个set找出该set包含的值哪个的可取数量最少
这个数量就是set最大组数
把可取数量有被取走的值都减掉这个组数再算下一个set
就可以得到所有set的组数了
以下假设值是string:
// 依优先权排好的set
HashSet<string>[] setQueue = { 乙, 甲, ... };
// 一串值
string[] valuePool = {"B","C","E", ...};
// 结果
int[] result = new int[setQueue.Length];
Dictionary<string,int> valueCounts = valuePool.GroupBy(v => v)
.ToDictionary(g => g.Key, g => g.Count());
for(int i = 0; i < setQueue.Length; ++i)
{
result[i] = setQueue[i].Min(val =>
valueCounts.Keys.Contains(val) ? valueCounts[val] : 0
);
if(result[i] > 0)
foreach (string val in setQueue[i])
valueCounts[val] -= result[i];
}
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 220.130.236.108
※ 编辑: ssccg 来自: 220.130.236.108 (06/08 14:21)