线性排列算法

Question

我不确定标题是否正确。

我有几个标签，它们在y轴上设置了位置范围:

range = [0, 100px]

例如：5个标签在以下位置：

positions = [5px, 6px, 8px, 72px, 76px]

现在我希望我的算法能够纠正这些位置，使它们之间的距离不小于10像素，并做出最小的调整。

我期望调用函数的方式如下：

result = calculateNewPositions(range, positions, min(10px, 100px / positions.length))

在这种情况下，结果应该是：

[0px, 10px, 20px, 69px, 79px]

这个算法的名称是什么或者如何实现它？

- gkucmierz

---

我没想到这是一个排序算法。 我还没有尝试过任何东西，因为我不知道如何高效地做到这一点。 - gkucmierz

@Pogrindis 在问题和标题中使用 cmd+F 搜索 "sort"，结果为0。 - Joseph Marikle

@JosephMarikle 谢谢，提到“arrangement”时有些不确定性。 - Pogrindis

只针对前两个项目（5px，6px），您可以在每个项目的右侧或左侧添加空间。您似乎将第一个设置为0px，第二个设置为10px，但这相当随意。为什么不是“5px，15px，25px”？编辑：显然，flex不是一个选项。我使用它作为一个例子，说明有人曾经在确定如何在类似环境中排列内容时有过与您相同的问题。您需要考虑类似的逻辑来解决您的问题。 - Joseph Marikle

@NinaScholz 谢谢！现在问题和期望的结果更加清晰了！ - Pogrindis

Answer 1

这是一个算法，对大多数情况都有效，并尽可能地减少对原始值的调整。

1. 遍历每一对元素。
2. 如果空间不足，则将它们相互分离1个单位，确保不违反范围。
3. 重复执行，直到所有元素之间都有足够的空间。

以下是示例实现：

function calculateNewPositions(positions, minSpacing, rangeMin, rangeMax) {
  var temp = positions.slice(0);
  var madeChange;
  do {
    madeChange = false;
    for (var i = 0; i < temp.length - 1; i++)
      if (temp[i + 1] - temp[i] < minSpacing) {
        if (temp[i] > rangeMin) { temp[i]--; madeChange = true; }
        if (temp[i + 1] < rangeMax) { temp[i + 1]++; madeChange = true; }
      }
  } while (madeChange);
  return temp;
}

演示: https://jsfiddle.net/aaxmuw2t/

示例结果: [0, 10, 20, 69, 79]

请注意，这个算法非常简单，对于具有大量接近数字的复杂数组可能不总是产生最佳结果。例如，如果您输入[33, 34, 35, 36]，则会得到[19, 29, 40, 50]，其中有一个额外的不必要空格。

- mellamokb

---

对于这个输入：[95, 94, 92, 28, 24]，它应该返回输出：[100, 90, 80, 31, 21]。 - gkucmierz

@gkucmierz：我的算法假设数字以升序为前提条件，因为这是您提供的唯一用例的真实情况。处理降序数字应该很容易 - 只需先反转它，运行算法，然后再次反转即可获得预期结果。我认为您应该能够处理它 :) - mellamokb

你是对的 @mellamokb，它在那种情况下也能工作：https://jsfiddle.net/aaxmuw2t/3/ 但是有很多情况下这段代码不会按照我的期望工作。 我目前正在处理另一个函数。 - gkucmierz

@gkucmierz：不幸的是，我认为解决这个问题的最优解是NP难问题。因此，您需要一些在常见用例下有效的启发式算法。祝你好运！ :) - mellamokb

@gkucmierz：出于好奇，我很想知道一些并不按预期工作的案例。你能提供几个吗？ - mellamokb

Answer 2

calculateNewPositions = function(positions, minDelta) {
   var newPositions = [0]
   positions.slice(1).forEach(function(pos, index) {
     var delta = positions[index + 1] - positions[index]
     newPositions.push(newPositions[index] + Math.max(delta, minDelta))
   })
   return newPositions
}

https://tonicdev.com/lipp/pos-diff

- lipp

---

这个函数有问题。它不能正确地处理我的输入。 - gkucmierz

数组中不应包含px。[5px, 6px] ---> [5,6] 你试过这个链接吗？这难道不是你所描述的吗？ - lipp

现在返回的是：[0，10，20，84，94] 在这种情况下，我需要[0，10，20，64，74] - gkucmierz

这个64是从哪里来的？原始差值为72px - 8px = 64px。20px上的64px差异为84px。只要它不小于minDelta，难道你不想让差异保持不变吗？ - lipp

我目前得到的是 [0, 10, 10, 64, 10]。 - Georgy

Answer 3

我最终做了这样的事情：

var fixPositions = function(range, pos, delta, strict) {
  var i;
  var leftSpaces = [];
  var halfDelta = strict ? delta / 2 : 0;
  delta = Math.min(delta, (range[1] - range[0] / (pos.length + (strict ? 0 : 1))));

  // calculate all spaces that are greater than delta
  leftSpaces.push(Math.max(pos[0] - range[0] - halfDelta, 0));
  for (i = 1; i < pos.length; i++) {
    leftSpaces.push(Math.max(pos[i] - pos[i-1] - delta, 0));
  }
  leftSpaces.push(Math.max(range[1] - pos[pos.length-1] - halfDelta, 0));

  // save indexes of big spaces
  var nonZeroSpacesIdx = [];
  leftSpaces.map(function(space, i) {
    if (space > 0) {
      nonZeroSpacesIdx.push(i);
    }
  });

  // sort indexes by spaces sizes (start from smaller)
  nonZeroSpacesIdx.sort(function(a, b) {
    return leftSpaces[a] - leftSpaces[b];
  });

  // loop until spaces sum are greater than range
  var spacesSum = Infinity;
  while (nonZeroSpacesIdx.length > 0 && spacesSum > 0) {
    spacesSum = 0;
    for (i = 0; i < nonZeroSpacesIdx.length; i++) {
      spacesSum += leftSpaces[nonZeroSpacesIdx[i]];
    }
    var missingDiff = (spacesSum + (pos.length - 1) * delta + halfDelta * 2) - (range[1] - range[0]);

    if (missingDiff <= 0) {
      break;
    }
    // find min diff which can be substracted from all spaces
    var minDiff = Math.min(missingDiff / nonZeroSpacesIdx.length, leftSpaces[nonZeroSpacesIdx[0]]);
    for (i = 0; i < nonZeroSpacesIdx.length; i++) {
      leftSpaces[nonZeroSpacesIdx[i]] -= minDiff;
    }
    // remove index of first space if its equal zero
    if (leftSpaces[nonZeroSpacesIdx[0]] <= 0) {
      nonZeroSpacesIdx.shift();
    }
  }

  // reconstruct new positions
  var newPos = [];
  newPos.push(range[0] + leftSpaces[0] + halfDelta);
  for (i = 1; i < leftSpaces.length - 1; i++) {
    newPos[i] = newPos[i-1] + leftSpaces[i] + delta;
  }

  return newPos;
};

// result should be from range: [5, 95]
console.log(fixPositions([0, 100], [5, 6, 8, 72, 76], 10, true));

// result should be from range: [0, 100]
console.log(fixPositions([0, 100], [5, 6, 8, 72, 76], 10, false));

https://jsfiddle.net/fcwu1oyu/14/

它并没有给出我输入的完全相同的值，但它对我的饼图起到了作用。

- gkucmierz

Answer 4

一个正在进行中的解决方案

该代码将两个过于接近的元素分别推向两侧。这是对称的，有时会导致推得太远的值，但可以进行校正。

function disperse(values, threshold, range) {
    var delta = Array.apply(null, { length: values.length }).map(function () { return 0; }),
        converged = false;

    while (!converged) {
        converged = true;
        delta = delta.map(function (d, i, dd) {
            if (i < dd.length - 1 && dd.length > 1 && values[i + 1] + dd[i + 1] - values[i] - d < threshold) {
                converged = false;
                dd[i + 1] += 1;
                return d - 1;
            }
            return d;
        });
    }
    converged = false;

    // try to minimise difference
    while (!converged) {
        converged = true;
        delta = delta.map(function (d, i) {
            var space;
            if (i < delta.length - 2) {
                space = values[i + 1] + delta[i + 1] - values[i] - d;
                if (d < 0 && space > threshold) {
                    converged = false;
                    return d + space - threshold;
                }
            }
            return d;
        });
    }

    // respect lower range
    delta.reduce(function (r, d, i, dd) {
        if (values[i] + d < r) {
            dd[i] = r - values[i];
            return r + threshold;
        }
        return values[i] + threshold + d;
    }, range[0]);

    // respect upper range
    delta.reduceRight(function (r, d, i, dd) {
        if (values[i] + d > r) {
            dd[i] = r - values[i];
            return r - threshold;
        }
        return values[i] + d;
    }, range[1]);

    return values.map(function (v, i) {
        return v + delta[i];
    });
}

document.write('<pre>' + JSON.stringify(disperse([5, 6, 8, 72, 76], 10, [0, 100]), 0, 4) + '</pre>');
document.write('<pre>' + JSON.stringify(disperse([5, 6, 7, 8, 72, 76], 10, [0, 100]), 0, 4) + '</pre>');
document.write('<pre>' + JSON.stringify(disperse([24, 28, 92, 94, 95], 10, [0, 100]), 0, 4) + '</pre>');

- Nina Scholz

---

你的答案似乎与我的完全相同，只是你没有正确检查范围（0到100）...请尝试在我的答案下面发布的示例OP：24,28,92,94,95。你的代码似乎返回了21,31,83,94,104，但104> 100。 - mellamokb

如果是这样，那么我在你之前写了它一年。 :) - Nina Scholz

最后一个值不在范围内。这是一个前提条件，所有的值必须先在范围内。 - Nina Scholz

我看到的是 result: 0,10,20,69,79,90,100，这是在范围内的。100只是为了证明算法。 - Nina Scholz

抱歉，我想我没有解释清楚 :) 或许这个链接可以帮助你：https://jsfiddle.net/7th90daa/。请注意，输入值都在范围内，但是你的代码输出了一个超出范围的结果（104）。明白了吗？ - mellamokb