作者chrisQQ (ＣｈｒｉｓＬｉｕ)
看板PHP
標題Re: [問題] 不重覆的排列組合
時間Fri Jun 8 14:48:01 2012
※ 引述《dlikeayu (太陽拳vs野球拳)》之銘言：
: ※ [本文轉錄自 Prob_Solve 看板 #1Fq9QlzU ]
: 剩BBCE
: 請問用算的這種有什麼演算法能適用解決呢？
我直覺想到的方法… 大概就是硬幹吧，算不上什麼演算法 XD
不過我看了推文和 prob_solve 的意見，覺得可以換個角度看原先的 data set
因為這是在 PHP 板，所以以下的程式我用 PHP 回（雖然cshrap也可以 XD）
// 原先的 data set
$a_set = array('A', 'B', 'C');
$b_set = array('A', 'D', 'E');
$data_set = array('B', 'C', 'E', 'B', 'A', 'D', 'E');
// 將 data_set 轉成 key => count 的格式
$converted_data = array();
foreach($data_set as $d) {
$converted_data[$d] ++;
}
// 預設兩個 set 取得的組數
$a_set_count = PHP_INT_MAX;
$b_set_count = PHP_INT_MAX;
// check B set
foreach($b_set as $b) {
$b_set_count = min($converted_data[$b], $b_set_count);
}
foreach($b_set as $b) {
$converted_data[$b] = $converted_data[$b] - $b_set_count;
}
// check A set
foreach($a_set as $a) {
$a_set_count = min($converted_data[$a], $a_set_count);
}
foreach($a_set as $a) {
$converted_data[$a] = $converted_data[$a] - $a_set_count;
}
其實重複的地方可以包成 function 比較好重複利用
不過因為你的範例只有給兩組，所以我偷懶的沒另外包
跑出來結果大概就是這樣
a_set_count = int 0
b_set_count = int 1
剩下的陣列：2B 1C
array (size=6)
'B' => int 2
'C' => int 1
'E' => int 1
'A' => int 0
'D' => int 0
附上 webgrind 的結果
Calls Count Total
php::var_dump @ 45 1 25
php::min @ 26 3 8
php::var_dump @ 42 1 7
php::var_dump @ 43 1 5
php::min @ 35 3 4
Total Self Cost : 228
Total Inclusive Cost: 302
以上單位為 microseconds
運算的時候要維護 array 有點麻煩 -___- 所以我改用這種方法做
效能的話… 不知道該跟什麼比較… 不清楚
只是提供一個想法。
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 219.85.64.11
1F：→ chrisQQ:原來 csharp 板有板友回了概念類似的文章了… 06/08 14:49
2F：推 carlcarl:我直覺的作法也是這樣作@@a 06/09 02:16
3F：→ chrisQQ:不過原PO有在 csharp 版回覆後面的問題… 也難怪說要找 06/09 07:32
4F：→ chrisQQ:演算法 XD 後來還有權重和排列組合 hmm 06/09 07:33
5F：→ dlikeayu:還是感謝，都是學習 06/09 23:46