c++ - 如何实现去除所有集合内可以组成加法运算的子集
黄舟
黄舟 2017-04-17 15:37:03
0
1
778

给一组数列,若数列内存在一个数等于数列内其他一些数的和,则去除那些数。此删除操作可重复操作直到无法继续找到满足条件的数进行删除。请写出一个函数,输入为整型数组,经过函数内一系列删除操作后得到一个最短数组,返回最短数组的长度。
比如{48,20,1,3,4,6,9,24}由于(4+20+24=48)所以去除4,20,24,48,余下{1,3,6,9}后,由于3+6=9,去除{3,6,9}得到{1},由于数组长度为1,返回1

黄舟
黄舟

人生最曼妙的风景,竟是内心的淡定与从容!

全部回覆(1)
左手右手慢动作

這個問題目測NPC妥妥的。可以分「兩步走」。

  1. 找出所有「加法子集」。取每個元素為可能的和,利用subset sum演算法逐一求解。

  2. 尋找互斥的加法子集的最大並集:參考set packing演算法,用線性規劃求解。

以下用 Mathematica 詳細描述下演算法。

找加法子集

要列舉集合中所有構成加法式子的數字(允許數字是負數,也允許重複數字),首先借subset sum演算法(帶快取的遞歸),列舉出其和是某給定數字的子集。

subsetSum[lst_List, s_] := Block[{q},
  q[k_?NonPositive, x_] := {};
  q[k_?Positive, x_] := q[k, x] =
    Union[q[k - 1, x],
     If[lst[[k]] == x, {{x}}, {}],
     (Append[lst[[k]]] /* Sort) /@ q[k - 1, x - lst[[k]]]];
  q[Length[lst], s]]

程式碼對q進行遞迴呼叫並快取結果。具體的遞歸推導可參考這個問題。注意對求出的加法子集內部進行了排序,最後進行並集操作以刪除重複項。用例:

subsetSum[{1, 2, 3, 4, 5}, 8]
> {{3, 5}, {1, 2, 5}, {1, 3, 4}}

這個給定的數字可能是本問題集合中的任意元素,所以用subsetSum遍歷集合中的每個元素,用它和剩下的元素嘗試組成加式。最後並刪除重複的組合,即為可能的全部加法子集了。

summationList[lst_List] := Union @@ Array[
   i \[Function] Map[Append[lst[[i]]] /* Sort,
     Select[subsetSum[Delete[lst, i], lst[[i]]], Length[#] > 1 &]],
   Length[lst]]

上面程式碼同樣進行了集合內部排序運算,因為把和加入集合時可能打亂順序。而且刪除了加數個數少於2個的情況。用例:

summationList[{1, 2, 3, 4, 5}]
> {{1, 2, 3}, {1, 3, 4}, {1, 4, 5}, {2, 3, 5}}

找互斥最大並集

得到加法子集後,用權重的set packing找出它們中互斥最大並集。用線性規劃語言描述就是

$$array{text{maximize} & sum{|s_i| x_i} & text{最大化並集中的元素個數} \ text{subject to} & sum {m_i x_i} leq 1 & text{選取的集合是互斥的} \ & x_i in {0, 1} & text{$x_i=1$則選擇集合$i$,否則放棄集合$i$}}$$

Mathematica有提供內建的LinearProgramming函數:

pickSumList[lst_List] := Module[{sumlst},
  sumlst = summationList[lst];
  Pick[sumlst,
   LinearProgramming[
    -Length /@ sumlst,
    Outer[MemberQ[#2, #1] & /* Boole, lst, sumlst, 1],
    ConstantArray[{1, -1}, Length[lst]],
    ConstantArray[{0, 1}, Length[sumlst]],
    Integers],
   1]]

測試

題主的例子:

隨機產生一個16個元素的集合。

pickSumList找出結果,並高亮顯示作為和的元素:

剩下的元素:

熱門教學
更多>
最新下載
更多>
網站特效
網站源碼
網站素材
前端模板