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

[chrisQQ (ＣｈｒｉｓＬｉｕ)]

※ 引述《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
→ chrisQQ:原來 csharp 板有板友回了概念類似的文章了…
推 carlcarl:我直覺的作法也是這樣作@@a
→ chrisQQ:不過原PO有在 csharp 版回覆後面的問題… 也難怪說要找
→ chrisQQ:演算法 XD 後來還有權重和排列組合 hmm
→ dlikeayu:還是感謝，都是學習