拆分數組均勻分佈的塊

我在尋找一種有效的方式將數組分割成具有相似的直方圖塊。拆分數組均勻分佈的塊

例如，給定陣列：

l = np.array([1, 2, 3, 4, 1, 1, 1, 2, 3, 4, 55, 5, 5, 5, 5, 5, 3, 2, 2, 21, 2])

我想獲得：

c1 = np.array([1, 4, 1, 5, 5, 3, 2]) 
c2 = np.array([2, 1, 3, 4, 5, 5, 2]) 
c3 = np.array([3, 1, 2, 55, 5, 2, 21])

不僅如此，但是每個塊應該對一個給定的功能的類似的尺寸和類似的總和F：

1. |sum(ci, f) - sum(cj, f)| < e, for i != j 
2. |len(ci) - len(cj)| < e, for i != j

其中

sum(c, f) = f(c[0]) + ... + f(c[len(c)])

編輯： 澄清這個意圖。我想通過列表並行化一個進程到n子進程，但成本必須在每個子進程之間均勻分配。處理在該列表中的元素的成本是在陣列l，其中f是該方法的計算複雜度相同位置的整數的函數f。例如，f(i)=i^2。所以，我希望所有進程具有相同的計算成本，不要讓進程過早完成，而其他進程永遠持續。

來源

2014-04-04 synack

請分享你如何得到C1，C2和C3以上。 – emeth

最後，終於。謝謝，先生，給出一個_minimal_例子。 –

@mskimm：我手動完成了。獲取它們的方式正是我所要求的... – synack

讓我們先從一個非常弱的假設：類似直方圖在接下來的初步方式定義：一個整數集S1的，直方圖H(S1)類似於一套S2如果sum(S1) = sum(S2)的直方圖H(S2)。

一般來說你發現子集的數組一個這樣f(S1) = f(S2) = ... = f(SN)的S1，S2，...，SN後，並根據我們的假設f=sum哪裏。不幸的是，你已經有了自己k-Partition problem，這是NP難的，如果你讓別人找到一種有效的方式（即多時間），要做到這一點，因爲你的要求，結果將是P=NP是被證明是第一個真正的stackoverflow！

來源

2014-04-04 12:21:26 mockinterface

我認爲我不需要有這樣一個確切的分區。我可以放鬆這個問題並有一些近似。例如，我可以循環（以某種聰明的方式）通過排序列表來均勻分佈在一組塊上。因此，例如：'升= [20，19，7,7，4，3，2，1，1]' - >'C1 = [20，3,2]，C 2 = [19，4,1 ]，c3 = [7,7,1]'。在這裏，我改變了每3個步驟分塊的方向。你怎麼看？ – synack

@ Kits89放寬問題並進行多次逼近是不同的事情。這可能是因爲在放鬆問題之後，存在一個多項式解，不需要近似，當某些條件或假設改變時，許多NP難問題變成多項式。除此之外，你可以從這裏開始3-PARTITION：http://mathoverflow.net/questions/82332/seeking-a-solution-algorithm-to-the-3-partition-problem，並按照鏈接，看看你是否可以適應您的特定情況的近似值。 – mockinterface

拆分數組均勻分佈的塊

回答

相關問題