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

看板C_Sharp (C#)作者dlikeayu (太陽拳vs野球拳)時間13年前 (2012/06/08 15:29)推噓0(0推 0噓 2→)

留言2則, 1人參與討論串3/3 (看更多)

※ 引述《ssccg (23)》之銘言： : ※ 引述《dlikeayu (太陽拳vs野球拳)》之銘言： : : 作者: 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:既然有優先順序，不就算出最多能抽幾組乙，減掉這數量再算 06/07 20:13 : → 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]; : } 謝謝後來延伸個更可怕的問題甲乙或是可能多丙丁組合然後優先權還有"級別數" 這邊開始就變可怕了… 假設 (數字愈小愈高) 甲 =1 乙 =2 丙 =3 丁 =1 這樣變成要從一組數裏面先去排列出各種可能然後再算出總合級數是最小的配法要是今天一個比對值裏有一堆 A,B,B,C,D,D,D,A,E,F,G,E,F,H(或更常符合更多組甲~庚) 這樣程式是不是會算到死啊... -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 210.61.247.2