algorithm - 合并两个组

Question

我有很多组，每个组都有它们可以适应的最小范围和最大范围。这些范围在不同组之间重叠

例如

    Group1  Min Range 3.125 , Max Range 3.5
    Group2  Min Range 3.25 , max Range 3.75
    Group 3 Min Range 3.5, max range 4.0

我需要合并这些组以形成最少数量的组。

喜欢

Group1  Min Range 3.125 , Max Range 3.5
              Item 1 value 3.125
              Item 2 value 3.3
              Item 3 value 3.5

Group2  Min Range 3.25 , max Range 3.75
              Item 1 value 3.25
              Item 2 value 3.3

我可以将这两个组合并到 Group1 中。

这是我在做的事情

for( size_t TopIndex = 0; TopIndex < GroupVector.Size(); TopIndex++)
{
    Group& CurrentGroup = GroupVector[TopIndex];
    for( size_t InnerIndex = TopIndex +1; InnerIndex < GroupVector.Size(); InnerIndex++)
    {
        Group& InnerGroup  = GroupVector[InnerIndex];
        MergeGroup(CurrentGroup,InnerGroup);
    }
}

在合并组中，

1.  Move items from Group 1 to Group 2 , Save total number of group after merge (I will stop if number of group is 1)
2.  Move items from Group 2 to Group 1 , Save total number of group after merge
3.  Compare number of group form step 1 &2  and accept an option which results in less number of groups.

我要合并的组数很大，我正在尝试寻找是否有更好的方法。

Answer 1

可以有多种算法来执行您想要的操作。Personnaly，我会首先通过检查最小和最大范围来检查一个组是否可以被其他组“吸收”。

例子:

group1 min 1.00, max 2.00
group2 min 1.50, max 2.50
group3 min 1.25, max 2.25

group3 的所有项目都可以合并到 group 2 和 group 3。

这将是第一个最小的减少。然后我会检查其他组的项目

Group1  Min Range 3.10 , Max Range 3.50
              Item 1 value 3.12
              Item 2 value 3.30
              Item 3 value 3.50

Group2  Min Range 3.25 , max Range 3.75
              Item 1 value 3.25
              Item 2 value 3.30

Group3  Min Range 3.30 , max Range 3.90
              Item 1 value 3.40
              Item 2 value 3.50

用一种算法来检查项目是否可以合并到下一组像这样的东西:

foreach (groups as group){
    foreach(group.items as item){
        tryToInsertItemIntoOtherGroups(item);
        if(group is empty){
            delete groupe;
        }
    }
}

第一个循环(对于第一组)会像这样改变:

Group1  Min Range 3.10 , Max Range 3.50
              Item 1 value 3.12

Group2  Min Range 3.25 , max Range 3.75
              Item 1 value 3.25
              Item 2 value 3.30
              Item 3 value 3.30
              Item 4 value 3.50

Group3  Min Range 3.30 , max Range 3.90
              Item 1 value 3.40
              Item 2 value 3.50

第二个循环(对于第二组)将导致删除第 2 组:

Group1  Min Range 3.10 , Max Range 3.50
              Item 1 value 3.12
              Item 2 value 3.25
              Item 3 value 3.30
              Item 4 value 3.30
              Item 5 value 3.50

Group3  Min Range 3.30 , max Range 3.90
              Item 1 value 3.40
              Item 2 value 3.50

第三个循环(对于第三组)将导致删除第 3 组:

Group1  Min Range 3.10 , Max Range 3.50
              Item 1 value 3.12
              Item 2 value 3.25
              Item 3 value 3.30
              Item 4 value 3.30
              Item 5 value 3.50
              Item 6 value 3.40
              Item 7 value 3.50