作者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