63

假设我有一个浮点数数组，按排序（假设升序）顺序，其总和已知为 integer N。我想将这些数字“四舍五入”为整数，同时保持它们的总和不变。换句话说，我正在寻找一种将浮点数数组（调用它 fn）转换为整数数组（调用它in）的算法，这样：

  1. 两个数组的长度相同
  2. 整数数组的总和是N
  3. 每个浮点数fn[i]与其对应的整数之间in[i]的差小于 1（如果确实必须，则等于 1）
  4. 鉴于浮点数按排序顺序 ( fn[i] <= fn[i+1])，整数也将按排序顺序 ( in[i] <= in[i+1])

鉴于满足这四个条件，最小化舍入方差 ( sum((in[i] - fn[i])^2)) 的算法是可取的，但这并不是什么大问题。

例子：

[0.02, 0.03, 0.05, 0.06, 0.07, 0.08, 0.09, 0.1, 0.11, 0.12, 0.13, 0.14]
    => [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]
[0.1, 0.3, 0.4, 0.4, 0.8]
    => [0, 0, 0, 1, 1]
[0.1, 0.1, 0.1, 0.1, 0.1, 0.1, 0.1, 0.1, 0.1, 0.1]
    => [0, 0, 0, 0, 0, 0, 0, 0, 0, 1]
[0.4, 0.4, 0.4, 0.4, 9.2, 9.2]
    => [0, 0, 1, 1, 9, 9] 更可取
    => [0, 0, 0, 0, 10, 10] 是可以接受的
[0.5, 0.5, 11]
    => [0, 1, 11] 很好
    => [0, 0, 12] 在技术上是不允许的，但我会在紧要关头接受它

要回答评论中提出的一些很好的问题：

  • 两个数组中都允许重复元素（尽管我也有兴趣了解仅在浮点数组不包含重复时才有效的算法）
  • 没有单一的正确答案 - 对于给定的浮点输入数组，通常有多个整数数组满足四个条件。
  • 我想到的应用程序是 - 这有点奇怪 - 在马里奥赛车游戏中将积分分配给顶级选手 ;-) 我自己从未真正玩过这款游戏，但在观看其他人时，我注意到有 24 分分布在前 4 名完成者，我想知道如何根据完成时间分配积分（因此，如果某人以较大的领先优势完成比赛，他们将获得更大的积分份额）。游戏将总点数作为整数进行跟踪，因此需要这种四舍五入。

对于好奇的人，这是我用来确定哪些算法有效的测试脚本。

4

13 回答 13

29

您可以尝试的一种选择是“级联舍入”。

对于此算法，您需要跟踪两个运行总计：到目前为止的浮点数之一和迄今为止的整数之一。要获得下一个整数，请将下一个 fp 数添加到运行总数中，四舍五入运行总数，然后从四舍五入的运行总数中减去整数运行总数：-

number  running total   integer integer running total
   1.3       1.3          1           1
   1.7       3.0          2           3
   1.9       4.9          2           5
   2.2       8.1          3           8
   2.8      10.9          3          11
   3.1      14.0          3          14
于 2009-04-27T07:06:50.573 回答
21

这是一种应该完成任务的算法。与其他算法的主要区别在于，这个算法总是以正确的顺序对数字进行四舍五入。最小化舍入误差。

该语言是一些可能源自 JavaScript 或 Lua 的伪语言。应该说明点。请注意基于一个的索引（对于循环，x 到 y 更好。：p）

// Temp array with same length as fn.
tempArr = Array(fn.length)

// Calculate the expected sum.
arraySum = sum(fn)

lowerSum = 0
-- Populate temp array.
for i = 1 to fn.lengthf
    tempArr[i] = { result: floor(fn[i]),              // Lower bound
                   difference: fn[i] - floor(fn[i]),  // Roundoff error
                   index: i }                         // Original index

    // Calculate the lower sum
    lowerSum = lowerSum + tempArr[i].result
end for

// Sort the temp array on the roundoff error
sort(tempArr, "difference")

// Now arraySum - lowerSum gives us the difference between sums of these
// arrays. tempArr is ordered in such a way that the numbers closest to the
// next one are at the top.
difference = arraySum - lowerSum

// Add 1 to those most likely to round up to the next number so that
// the difference is nullified.
for i = (tempArr.length - difference + 1) to tempArr.length
    tempArr.result = tempArr.result + 1
end for

// Optionally sort the array based on the original index.
array(sort, "index")
于 2009-04-27T07:17:01.157 回答
16

一种非常简单的方法是把所有的小数部分加起来。根据您的问题的定义，该数字必须是整数。从最大的数字开始均匀分配该整数。然后给第二大的数字...等等，直到你用完要分发的东西。

请注意，这是伪代码......并且可能会在索引中偏离一个......它已经很晚了，我很困。

float accumulator = 0;

for (i = 0; i < num_elements; i++)  /* assumes 0 based array */
{
   accumulator += (fn[i] - floor(fn[i])); 
   fn[i] =  (fn[i] - floor(fn[i]);
}

i = num_elements;

while ((accumulator > 0) && (i>=0))
{
    fn[i-1] += 1;   /* assumes 0 based array */
    accumulator -= 1;
    i--;
}

更新：还有其他方法可以根据对每个值执行多少截断来分配累积值。这需要保留一个单独的列表，称为 loss[i] = fn[i] - floor(fn[i])。然后，您可以重复 fn[i] 列表并重复给最大损失项 1（之后将 loss[i] 设置为 0）。它很复杂，但我想它有效。

于 2009-04-27T07:05:23.680 回答
4

怎么样：

a) start: array is [0.1, 0.2, 0.4, 0.5, 0.8], N=3, presuming it's sorted
b) round them all the usual way: array is [0 0 0 1 1]
c) get the sum of the new array and subtract it from N to get the remainder.
d) while remainder>0, iterate through elements, going from the last one
   - check if the new value would break rule 3.
   - if not, add 1
e) in case that remainder<0, iterate from first one to the last one
   - check if the new value would break rule 3.
   - if not, subtract 1
于 2009-04-27T07:28:45.497 回答
3

基本上你要做的是在四舍五入后将剩菜分配给最有可能的候选人。

  1. 像往常一样对浮点数进行舍入，但要跟踪从舍入和相关索引到fnand的增量in。
  2. 按增量对第二个数组进行排序。
  3. 虽然sum(in) < N，从最大的负增量向前工作，增加舍入值（确保您仍然满足规则＃3）。
  4. 或者， while sum(in) > N，从最大的正增量向后工作，减少舍入值（确保您仍然满足规则 #3）。

例子：

[0.02, 0.03, 0.05, 0.06, 0.07, 0.08, 0.09, 0.1, 0.11, 0.12, 0.13, 0.14] N=1

1. [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] sum=0
和 [[-0.02, 0], [-0.03, 1], [-0.05, 2], [-0.06, 3], [-0.07, 4], [-0.08, 5],
     [-0.09, 6], [-0.1, 7], [-0.11, 8], [-0.12, 9], [-0.13, 10], [-0.14, 11]]

2.排序会反转数组

3. 从最大的负余数开始计算，得到 [-0.14, 11]。
增加 `in[11]` 得到 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1] sum=1
完毕。
于 2009-04-27T07:11:59.953 回答
1

你可以试试这样的东西吗？

in [i] = fn [i] - int (fn [i]);
fn_res [i] = fn [i] - in [i];

fn_res → 是结果分数。（我认为这是基本的......），我们错过了什么吗？

于 2009-04-27T07:03:51.657 回答
1

嗯，4是痛点。否则，您可以执行诸如“通常向下取整并累积剩余部分；当累加器 >= 1 时向上取整”之类的操作。（编辑：实际上，只要您交换他们的位置，那可能仍然可以？）

可能有一种方法可以通过线性规划来做到这一点？（这是数学“编程”，而不是计算机编程——你需要一些数学来找到可行的解决方案，尽管你可能会跳过通常的“优化”部分）。

作为线性规划的一个例子 - 对于例子 [1.3, 1.7, 1.9, 2.2, 2.8, 3.1] 你可以有规则：

1 <= i < 2
1 <= j < 2
1 <= k < 2
2 <= l < 3
3 <= m < 4
i <= j <= k <= l <= m
i + j + k + l + m = 13

然后应用一些线性/矩阵代数；-p 提示：有一些产品可以基于“Simplex”算法之类的东西来完成上述操作。普通的大学饲料，也是（我在大学为我的期末项目写了一个）。

于 2009-04-27T07:08:09.120 回答
1

在我看来，问题在于没有指定排序算法。或者更像 - 无论它是否稳定。

考虑以下浮点数组：

[ 0.2 0.2 0.2 0.2 0.2 ]

总和为 1。那么整数数组应该是：

[ 0 0 0 0 1 ]

但是，如果排序算法不稳定，它可以将“1”排序到数组中的其他位置......

于 2009-04-27T07:26:42.677 回答
0

使总的差异小于 1，并检查以进行排序。有些人喜欢，

while(i < sizeof(fn) / sizeof(float)) {
    res += fn[i] - floor(fn[i]);
    if (res >= 1) {
        res--;
        in[i] = ceil(fn[i]);
    }
    else
        in[i] = floor(fn[i]);
    if (in[i-1] > in[i])
        swap(in[i-1], in[i++]);
}

（这是纸质代码，所以我没有检查有效性。）

于 2009-04-27T07:26:34.393 回答
0

在@mikko-rantanen 的代码的python 和numpy 实现下面。我花了一点时间把这些放在一起，所以这可能对未来的谷歌人有所帮助，尽管这个话题已经很老了。

import numpy as np
from math import floor

original_array = np.array([1.2, 1.5, 1.4, 1.3, 1.7, 1.9])

# Calculate length of original array
# Need to substract 1, as indecies start at 0, but product of dimensions
# results in a count starting at 1
array_len = original_array.size - 1 # Index starts at 0, but product at 1

# Calculate expected sum of original values (must be integer)
expected_sum = np.sum(original_array)

# Collect values for temporary array population
array_list = []
lower_sum = 0
for i, j in enumerate(np.nditer(original_array)):
    array_list.append([i, floor(j), j - floor(j)]) # Original index, lower bound, roundoff error
# Calculate the lower sum of values
lower_sum += floor(j)

# Populate temporary array
temp_array = np.array(array_list)

# Sort temporary array based on roundoff error
temp_array = temp_array[temp_array[:,2].argsort()]

# Calculate difference between expected sum and the lower sum
# This is the number of integers that need to be rounded up from the lower sum
# The sort order (roundoff error) ensures that the value closest to be
# rounded up is at the bottom of the array
difference = int(expected_sum - lower_sum)

# Add one to the number most likely to round up to eliminate the difference
temp_array_len, _ = temp_array.shape
for i in xrange(temp_array_len - difference, temp_array_len):
    temp_array[i,1] += 1

# Re-sort the array based on original index
temp_array = temp_array[temp_array[:,0].argsort()]

# Return array to one-dimensional format of original array
array_list = []
for i in xrange(temp_array_len):
    array_list.append(int(temp_array[i,1]))
new_array = np.array(array_list)
于 2016-02-11T21:58:32.023 回答
0

计算sum of floor和sum of numbers。四舍五入sum of numbers，减去sum of floor，不同的是我们需要修补多少天花板（我们需要多少+1）。将数组按照上限与数字的差异从小到大进行排序。

对于diff时间（diff是我们需要修补多少天花板），我们将结果设置为ceiling of number。其他人将结果设置为floor of numbers。

public class Float_Ceil_or_Floor {

public static int[] getNearlyArrayWithSameSum(double[] numbers) {

    NumWithDiff[] numWithDiffs = new NumWithDiff[numbers.length];
    double sum = 0.0;
    int floorSum = 0;
    for (int i = 0; i < numbers.length; i++) {
        int floor = (int)numbers[i];
        int ceil = floor;
        if (floor < numbers[i]) ceil++; // check if a number like 4.0 has same floor and ceiling
        floorSum += floor;
        sum += numbers[i];
        numWithDiffs[i] = new NumWithDiff(ceil,floor, ceil - numbers[i]);
    }

    // sort array by its diffWithCeil
    Arrays.sort(numWithDiffs, (a,b)->{
        if(a.diffWithCeil < b.diffWithCeil)  return -1;
        else return 1;
    });

    int roundSum = (int) Math.round(sum);
    int diff = roundSum - floorSum;
    int[] res = new int[numbers.length];

    for (int i = 0; i < numWithDiffs.length; i++) {
        if(diff > 0 && numWithDiffs[i].floor != numWithDiffs[i].ceil){
            res[i] = numWithDiffs[i].ceil;
            diff--;
        } else {
            res[i] = numWithDiffs[i].floor;
        }
    }
    return res;
}
public static void main(String[] args) {
    double[] arr = { 1.2, 3.7, 100, 4.8 };
    int[] res = getNearlyArrayWithSameSum(arr);
    for (int i : res) System.out.print(i + " ");

}

}

class NumWithDiff {
    int ceil;
    int floor;
    double diffWithCeil;
    public NumWithDiff(int c, int f, double d) {
        this.ceil = c;
        this.floor = f;
        this.diffWithCeil = d;
    }
}
于 2016-10-17T08:44:33.930 回答
0

在不最小化方差的情况下，这是一个微不足道的：

  1. 从左到右对值进行排序。
  2. 全部向下舍入到下一个整数。
  3. 让这些整数的总和为 K。将 NK 最右边的值增加 1。
  4. 恢复原来的秩序。

这显然满足您的条件 1.-4。或者，您可以四舍五入到最接近的整数，并增加已向下舍入的 NK。您可以通过原始值和舍入值之间的差异贪婪地做到这一点，但每次舍入值只能从右向左增加，以保持排序顺序。

于 2018-02-28T13:18:03.093 回答
0

如果您可以在改善方差的同时接受总数的微小变化，这将在概率上保留 python 中的总数：

import math
import random
integer_list = [int(x) + int(random.random() <= math.modf(x)[0]) for x in my_list]

为了解释它，将所有数字向下舍入并以等于小数部分的概率加一，即十分之一0.1将变为1，其余的将变为0

这适用于将大量小数人转换为 1 人或 0 人的统计数据

于 2019-02-01T10:03:01.027 回答