非负集减 [英] Non negative set subtraction

问题描述

这适用于任何语言，但是我会在node中实现它.

This applies to any language, but I'd be implementing it in node.

我有一组整数，并且需要从该组总和中减去一个值.

I have a set of integers, and a value that I need to subtract from the sum of the set.

[4, 5, 6, 7, 8] - 25

如果我们从每个数字中平均减去，我们将得到:

If we subtract from every number evenly, we'd get:

[-1, 0, 1, 2, 3]

但是，我不希望任何数字小于0.因此，如果我正在编写算法来执行此操作，则负数将平均溢出到其余数字中，而我们现在拥有:

However, I don't want any numbers less than 0. So, if I were writing an algorithm to do this, the negative numbers would overflow equally into the remaining numbers, and we'd now have:

[0, 0, 1, 2, 3] - 1

制作结果集:

[0, 0, 1 - 0.333, 2 - 0.333, 3 - 0.333]

有没有快速的操作或一系列不涉及循环直到完成以解决此问题的操作?

Is there any fast operation or series of operations that don't involve looping until completion to solve this problem?

请注意，这正是我想要的结果.所有的负值甚至会溢出到其余的正值中.

Note that this is exactly the outcome I want. All of the negative values overflow EVENLY into the remaining positive values.

我使用Lodash，所以用Lodash回答是可以接受的.

I use Lodash so an answer in Lodash would be acceptable.

推荐答案

假设设置了数字

1. 仅具有正值
2. 集合的总和大于要减去的值
3. 可以排序.

关于第3点，您在评论中说可以对此进行排序，所以这是我想到的算法.就变量名而言，它很冗长，但希望可以使它更清晰.总而言之，它并不太复杂:

On point 3. you said in comments that it's fine to sort this, so here is the algorithm I have in mind. It's verbose in terms of variable names but hopefully it makes it clearer. All in all, it's not too complex:

const result = subtractFromSet([4, 5, 6, 7, 8], 25);
console.log(result)

function subtractFromSet(numberSet, totalToSubtract) {
  return numberSet.map((currentMember, index, wholeSet) => {
    const remainingElements = wholeSet.length - index
    const averageToSubtract = totalToSubtract / remainingElements;
    
    const toSubtract = Math.min(averageToSubtract, currentMember);
    //modify both the total remaining to subtract and the current element
    totalToSubtract -= toSubtract;
    return currentMember - toSubtract;
  })
}

要用语言解释，这就是发生的事情

To explain it in words, here is what is happening

1. 从集合的总和中减去一个值与从每个成员中减去该值除以集合的大小相同.因此 [4、5、6、7、8]-25 将是 4-5 ， 5-5 ， 6-5 等.
2. 如果我们不希望出现负数，那么我们只减去到当前成员.因此，在当前成员为 4 且平均值为 25/5 = 5 的情况下，我们只能减去 4 .
3. 为了分散余数，我们只需将其加回到余数中即可减去其余成员.因此，当我们到达第二个成员 5 时，平均值现在为(25-4)/(5-1-1)，因为我们无法减去完整的第一次平均5 ，只有 4 ，其余元素少一个.这将产生 5.25 .

1. Subtracting a value from the sum of the set is the same as subtracting the value divided by the size of the set from each member. So [4, 5, 6, 7, 8] - 25 would be 4 - 5, 5 - 5, 6 - 5, etc.
2. If we don't want negatives, then we only subtract up to the current member. So with current member 4 and the average being 25 / 5 = 5, we can only subtract 4.
3. In order to spread the remainder, we simply add it back to the total remaining to subtract for the rest of the members. So when we get to the second member 5, the average is now (25 - 4) / (5 - 1) because we couldn't subtract the full 5 average the first time, only 4, and the remaining elements are one less. This yields 5.25.

因此，当遍历每个成员并调整总和然后减去所需的平均值时，我们得到正确的结果.尽管请注意编程中的浮点算法，因为它可能导致结果稍微关闭.如果您舍入足够的重要数字来满足需要，则可以避免这种情况.

And so when going through each member and adjusting the total then average needed to subtract, we get the correct result. Although, be aware of floating point arithmetic in programming, as it can lead to results that are slightly off. If you round up to enough significant figures for your needs, you can largely avoid that.

最后一件事情-正如我所说，输入必须进行排序.可以很容易地做到这一点，就像这样:

One final thing - as I said, the input has to be sorted. This can be easily done like so:

const unsortedArray = [6, 4, 7, 8, 5];
const sortedArray = unsortedArray.sort((a, b) => a - b)

console.log(sortedArray);

我在上面的算法中忽略了它，而是专注于我们对排序后的输入实际执行的操作.

I left it out from the above algorithm to focus on what we actually do with the sorted input.

此算法的总复杂度相当不错-合理的排序将使您节省 O(n log(n))时间复杂度.取决于排序的实现方式和数据集-5个元素很可能通过 O(n ^ 2) Bubblesort进行排序，但同样，它是5个元素，因此可能不会产生影响.运行减法算法是一个简单的 O(n).相减的空间复杂度为 O(2n)，因为 .map()会复制数组.我选择它是因为它比较干净，因为您仍然可以输入.但是，您也可以通过最小的更改就地进行减法，这将使您获得 O(n)空间复杂度.

The total complexity of this algorithm is pretty decent - a decent sorting would net you O(n log(n)) time complexity. Depends on the sorting implementation and the dataset - 5 elements are likely to be sorted via an O(n^2) Bubblesort but then again, it's 5 element, so it's probably not going to have an impact. Running the subtraction algorithm is a simple O(n). The space complexity for subtraction is O(2n) because .map() makes a copy of the array. I chose this as it's a bit cleaner because you still have the input. But you can also do the subtraction in-place with minimal changes and it would net you a O(n) space complexity.

const input = [4, 5, 6, 7, 8];
subtractFromSet(input, 25);
console.log(input);

function subtractFromSet(numberSet, totalToSubtract) {
  numberSet.forEach((currentMember, index, wholeSet) => { //using .forEach instead of .map
    const remainingElements = wholeSet.length - index
    const averageToSubtract = totalToSubtract / remainingElements;
    
    const toSubtract = Math.min(averageToSubtract, currentMember);
    //modify both the total remaining to subtract and the current element
    totalToSubtract -= toSubtract;
    wholeSet[index] = currentMember - toSubtract; //modify the array directly
  })
}

这篇关于非负集减的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！