按'等於'分組

Question

我試圖拿一個數字列表，並將它們放入> = N個組，使得每個組的總和大約（但不一定完全相等），並且「異常值」可以成爲他們自己的一羣。

所以對於3組的目標和的類似的輸入：

[3, 2, 1, 4, 2, 5] 

輸出可能是：

[[5,1], [4,2], [3,2]] 

每個基團是所述的各個和

6, 6, 5 

我認爲我已經掌握了方法，因爲僞代碼看起來像這樣：

let target = Ceil(Sum(Series)/NumberOfTargetGroups) //The ideal size of each group 

while (count(UnpickedNumbers) > 0) 
    let CurrentGroup = new group 
    while (sum(CurrentGroup) < target) 
     for each Unpicked in sortDesc(UnpickedNumbers) 
      if (sum(CurrentGroup) + Unpicked) 
       Add Unpicked to current group 
       Remove unpicked from available numbers 

我想不通的是如何把這一邏輯爲GroupBy(n => ...) - 之所以想這樣做在於號碼列表實際上是由一系列對象的屬性來，我希望以這種方式進行分組。

Answer 1

分區是NP完全問題。 我preapred片段：

public IEnumerable<IEnumerable<TObject>> Algo<TObject>(IEnumerable<TObject> source, int groups, 
                 Func<TObject, int> intSelector) 
{ 
    if (source == null) 
    { 
     throw new ArgumentNullException("source"); 
    } 

    source = source.OrderByDescending(intSelector); 
    var evaluated = source as IList<TObject> ?? source.ToList(); 
    if (groups > evaluated.Count()) 
    { 
     throw new ArgumentException("Invalid group count."); 
    } 

    var result = new List<List<TObject>>(); 
    for (var i = 0; i < groups; i++) 
    { 
     result.Add(new List<TObject> { evaluated[i] }); 
    } 

    for (var i = groups; i < evaluated.Count(); i++) 
    { 
     var bestIndex = 0; 
     var bestSum = result[bestIndex].Sum(intSelector); 
     for (var j = 1; j < result.Count; j++) 
     { 
      var sum = result[j].Sum(intSelector); 
      if (sum < bestSum) 
      { 
       bestSum = sum; 
       bestIndex = j; 
      } 
     } 

     result[bestIndex].Add(evaluated[i]); 
    } 

    return result; 
} 

效率不高（有許多方法來優化它），結果並不總是optimial。但希望它會成爲你的算法的基礎（可能對你來說大概已經足夠了 - 測試它！）。

編輯： 我修改了你的代碼片段 - 你不必使用GroupBy。使用方法：

var widgets = new List<Widget> { W1, W2, etc. }; 
var result = Algo(widgets, groups: 3, intSelector: widget => widget.Height);