Re: [問題] 不重覆的排列組合

[ssccg (23)]

※ 引述《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
: 請問用算的這種有什麼演算法能適用解決呢？

→ ssccg:既然有優先順序，不就算出最多能抽幾組乙，減掉這數量再算
→ ssccg:最多幾組甲就好了?
: 如果這是個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)