使用对象的 min/max 值制作对象组（组合）

Question

首先，这是我的第一个问题，你可以告诉我如何改进它，使用什么标签。

我想做的是我有一堆对象，它们具有最小值和最大值，您可以通过这些值推断出两个对象是否具有某种重叠值，因此可以将它们放在一个组中

这道题可能需要动态规划来解答。

示例对象：

1 ( min: 0, max: 2 )
2 ( min: 1, max: 3 )
3 ( min: 2, max: 4 )
4 ( min: 3, max: 5 )

对象 1 可以与对象 2、3 分组
对象 2 可以与对象 1、3、4 分组
对象 3 可以与对象 1、2、4 分组
对象 4 可以与对象 2、3 分组

如您所见，有多种方法可以对这些元素进行分组

[1, 2]
[3, 4]

[1]
[2, 3]
[4]

[1]
[2, 3, 4]

[1, 2, 3]
[4]

现在应该有某种规则来推断哪个解决方案是最佳解决方案

例如最少的组数

[1, 2] [3, 4]

或

[1] [2, 3, 4]

或

[1, 2, 3] [4]
或一组中的大多数对象

[1] [2, 3, 4]

或

[1, 2, 3] [4]
或任何其他使用所述对象的另一个属性来比较解决方案的规则

我现在拥有的：

$objects = [...objects...];

$numberOfObjects = count($objects);
$groups    = [];
for ($i = 0; $i < $numberOfObjects; $i++) {
    $MinA           = $objects[$i]['min'];
    $MaxA           = $objects[$i]['max'];
    $groups[$i]    = [$i];
    for ($j = $i + 1; $j < $numberOfObjects; $j++) {
        $MinB = $objects[$j]['min'];
        $MaxB = $objects[$j]['max'];
        if (($MinA >= $MinB && $MinA <= $MaxB) || ($MaxA >= $MinB && $MaxA <= $MaxB) || ($MinB >= $MinA && $MinB <= $MaxA)) {
            array_push($groups[$i], $j);
        }
    }
}

这基本上创建了一个数组，其中包含可以组合在一起的对象的索引

从这一点开始，我不知道如何进行，如何生成所有解决方案，然后检查每个解决方案的好坏，然后选择最好的一个

或者也许有更好的解决方案不使用这些？

PHP 解决方案是首选，尽管这个问题不是 PHP-specific

Answer 1

当我第一次看到你的算法时，它的效率给我留下了深刻的印象:) 这里重写为 javascript，因为我很久以前就离开了 perl：

function setsOf(objects){
  numberOfObjects = objects.length
  groups    = []
  let i
  for (i = 0; i < numberOfObjects; i++) {
      MinA           = objects[i]['min']
      MaxA           = objects[i]['max']
      groups[i]    = [i]
      for (j = i + 1; j < numberOfObjects; j++) {
          MinB = objects[j]['min']
          MaxB = objects[j]['max']
          if ((MinA >= MinB && MinA <= MaxB) || (MaxA >= MinB && MaxA <= MaxB) || 
            (MinB >= MinA && MinB <= MaxA)) {
              groups[i].push(j)
          }
      }
  }
  return groups
}

如果您碰巧在 javascript 中也想得很好，您可能会发现这种形式更直接（但是它是相同的）：

function setsOf(objects){
  let groups = []
  objects.forEach((left,i) => {
    groups[i]=[i]
    Array.from(objects).splice(i+1).forEach((right, j) => {
      if ((left.min >= right.min && left.min <= right.max) || 
          (left.max >=right.max && left.max <= right.max) || 
          (right.min >= left.min && right.min <= left.max))
        groups[i].push(j+i+1)
    })
  })
  return groups
}

所以如果我们运行它，我们得到：

a = setsOf([{min:0, max:2}, {min:1, max:3}, {min:2, max:4}, {min:3, max: 5}])
[Array(3), Array(3), Array(2), Array(1)]0: Array(3)1: Array(3)2: Array(2)3: Array(1)length: 4__proto__: Array(0)
JSON.stringify(a)
"[[0,1,2],[1,2,3],[2,3],[3]]"

并且它确实令人印象深刻地捕获了复合组 :) 一个弱点是它正在捕获包含比必要更多对象的组，而不是捕获所有可用对象。您似乎有一个非常自定义的选择标准。对我来说，这些组似乎应该是每个最后一个相交的子集，或者只是组中每个元素提供独特覆盖的子集：[0,1], [0,2], [1,2], [1,3], [2,3], [0,1,3]

该算法可能涉及更多。这是我的方法，它远没有你的方法简洁和优雅，但它有效：

function intersectingGroups (mmvs) {
  const min = []
  const max = []
  const muxo = [...mmvs]

  mmvs.forEach(byMin => {
    mmvs.forEach(byMax => { 
      if (byMin.min === byMax.min && byMin.max === byMax.max) {
        console.log('rejecting identity', byMin, byMax)
        return // identity
      }
      if (byMax.min > byMin.max) {
        console.log('rejecting non-overlapping objects', byMin, byMax)
        return // non-overlapping objects
      }
      if ((byMax.max <= byMin.max) || (byMin.min >= byMax.min)) {
        console.log('rejecting non-expansive coverage or inversed order', 
          byMin, byMax)
        return // non-expansive coverage or inversed order
      }
      const entity = {min: byMin.min, max: byMax.max, 
        compositeOf: [byMin, byMax]}
      if(muxo.some(mv => mv.min === entity.min && mv.max === entity.max))
        return // enforcing Set
      muxo.push(entity)
      console.log('adding', byMin, byMax, muxo)
    })
  })

  if(muxo.length === mmvs.length) {
    return muxo.filter(m => 'compositeOf' in m)
    // solution
  } else {
    return intersectingGroups(muxo)
  } 
}

现在应该有某种规则来推断哪个解决方案是最佳解决方案

是的，所以，通常对于谜题或您要满足的规范，这将作为问题的一部分给出。实际上，您需要一种适应性强的通用方法。最好做一个可以配置结果和接受规则的对象，然后加载你感兴趣的规则，和搜索的结果，看看哪些规则匹配到哪里。例如，使用您的算法和示例标准：

最少的组数

从以下代码开始：

let reviewerFactory = {
  getReviewer (specification) { // generate a reviewer
    return { 
      matches: [], // place to load sets to
      criteria: specification,
      review (objects) { // review the sets already loaded
        let group
        let results = {}
        this.matches.forEach(mset => {
          group = [] // gather each object from the initial set for each match in the result set
          mset.forEach(m => {
            group.push(objects[m])
          })
          results[mset] = this.criteria.scoring(group) // score the match relative to the specification
        })
        return this.criteria.evaluation(results) // pick the best score
       }
    }
  },
  specifications: {}
}

现在您可以为最少数量的组添加这样的规范：

reviewerFactory.specifications['LEAST GROUPS'] =  {
  scoring: function (set) { return set.length },
  evaluation: function (res) { return Object.keys(res).sort((a,b) => res[a] - res[b])[0] }
}

然后你可以在集合的评估中使用它：

mySet = [{min:0, max:2}, {min:1, max:3}, {min:2, max:4}, {min:3, max: 5}]
rf = reviewerFactory.getReviewer(reviewerFactory.specifications['LEAST GROUPS'])
Object {matches: Array(0), criteria: Object, review: function}
rf.matches = setsOf(mySet)
[Array(3), Array(3), Array(2), Array(1)]
rf.review(mySet)
"3"

或者，大多数对象：

reviewerFactory.specifications['MOST GROUPS'] =  {
  scoring: function (set) { return set.length },
  evaluation: function (res) { return Object.keys(res).sort((a,b) => res[a] - res[b]).reverse()[0] }
}

mySet = [{min:0, max:2}, {min:1, max:3}, {min:2, max:4}, {min:3, max: 5}]
reviewer = reviewerFactory.getReviewer(reviewerFactory.specifications['MOST GROUPS'])
reviewer.matches = setsOf(mySet)
reviewer.review(mySet)
"1,2,3"

当然这是任意的，但根据 OP 中的定义，标准也是如此。同样，您必须更改此处的算法才能使用我的 intersectingGroups 函数，因为它没有 return 索引。但我相信这就是您要找的东西。

使用对象的 min/max 值制作对象组（组合）

Making groups (combinations) of objects using their min/max values

grouping

combinations

dynamic-programming

combinatorics

示例对象：

我现在拥有的：

现在应该有某种规则来推断哪个解决方案是最佳解决方案

最少的组数