Rust 根据填充系数以相对大小在给定空间中布局项目

我需要在给定的空间中布置一维物品.这些物品都有一个给定的起始尺寸.它们可以伸展以填满可用空间，但永远不会缩小.每个项目都有一个关联的填充系数，用于确定相对于其他项目的理想大小.填充系数为0的项目始终保持其原始大小.

如果起始大小和可用空间使得无法以达到理想相对大小的方式分配空间，那么我希望将额外的空间分配给这些项，以便新的相对大小最接近最佳值.我没有设定一个特定的"最近"度量，但是为一个相对空间已经大于其相对填充因子的元素分配更多空间并不是我想要的.

我在Rust中编写了一个实现，它根据相对填充系数分配额外的可用空间，但只有在有足够的可用空间来实现最佳大小比率的情况下才能正确工作.如果不是这样，它就失败了，因为它总是 for each 填充因子为正的项目分配一些额外的空间.

以下是我的代码和一些测试用例，它们有望演示我要实现的目标.

fn allocate_space(
    current_sizes: &[f32],
    fill_factors: &[u16],
    available_space: f32,
) -> Vec<f32> {
    // Assumptions
    {
        assert_eq!(current_sizes.len(), fill_factors.len());
        assert!(current_sizes.iter().sum::<f32>() <= available_space);
    }

    // Implementation
    let mut sizes = Vec::from(current_sizes);
    let fill_factor_sum = fill_factors.iter().sum::<u16>();

    // I'll probably need this
    let _fixed_size = current_sizes
        .iter()
        .zip(fill_factors)
        .filter_map(|(space, fill_factor)| {
            (*fill_factor == 0u16).then_some(space)
        })
        .sum::<f32>();

    if fill_factor_sum > 0 {
        let extra_space = available_space - sizes.iter().sum::<f32>();
        for (space, fill_factor) in sizes.iter_mut().zip(fill_factors) {
            *space += f32::from(*fill_factor) / f32::from(fill_factor_sum)
                * extra_space;
        }
    }

    // Constraints on the result
    {
        for ((current_size, new_size), fill_factor) in
            current_sizes.iter().zip(&sizes).zip(fill_factors)
        {
            // The allocated space is not allowed to shrink
            assert!(new_size >= current_size);
            // Items with a fill factor of zero keep their original size
            if *fill_factor == 0u16 {
                assert_eq!(current_size, new_size);
            }
        }
        // Can't use more space than available
        assert!(sizes.iter().sum::<f32>() <= available_space);
    }

    sizes.into()
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn enough_space_for_relative_fill_factors() {
        assert_eq!(allocate_space(&[1.0, 1.0], &[1, 1], 4.0), vec![2.0, 2.0]);
        assert_eq!(allocate_space(&[1.0, 1.0], &[1, 1], 5.0), vec![2.5, 2.5]);
    }

    #[test]
    fn not_enough_space_for_relative_fill_factors() {
        assert_eq!(allocate_space(&[1.0, 2.0], &[1, 1], 3.5), vec![1.5, 2.0]);
    }

    #[test]
    fn unequal_fill_factors() {
        assert_eq!(allocate_space(&[1.0, 1.0], &[1, 2], 3.0), vec![1.0, 2.0]);
        assert_eq!(allocate_space(&[1.0, 1.0], &[1, 2], 2.5), vec![1.0, 1.5]);
    }

    #[test]
    fn fixed_spaces() {
        assert_eq!(
            allocate_space(&[1.0, 2.0, 2.0], &[0, 1, 1], 7.0),
            vec![1.0, 3.0, 3.0]
        );
        assert_eq!(
            allocate_space(&[1.0, 2.0, 2.0], &[0, 1, 2], 6.0),
            vec![1.0, 2.0, 3.0]
        );
    }

    #[test]
    fn three_variable_sizes() {
        assert_eq!(
            allocate_space(&[1.0, 1.0, 2.0], &[1, 2, 1], 4.0),
            vec![1.0, 1.0, 2.0]
        );
        assert_eq!(
            allocate_space(&[1.0, 1.0, 2.0], &[1, 2, 1], 6.0),
            vec![1.0 + 1.0 / 3.0, 2.0 + 2.0 / 3.0, 2.0]
        );
        assert_eq!(
            allocate_space(&[1.0, 1.0, 2.0], &[1, 2, 1], 7.0),
            vec![1.0 + 2.0 / 3.0, 3.0 + 1.0 / 3.0, 2.0]
        );
        assert_eq!(
            allocate_space(&[1.0, 1.0, 2.0], &[1, 2, 1], 8.0),
            vec![2.0, 4.0, 2.0]
        );
    }
}

我的直觉是，这个问题有一个相对简单的解决方案，但我不太清楚.

我提供了Rust代码作为示例，因为我在Rust程序中使用它，但我很乐意得到任何语言、伪代码、数学或文本方面的帮助.

EDIT 下面是我对@btilly的答案的实现，使用float-cmp crate来判断f32是否近似相等.

use std::cmp::Ordering;

#[derive(Debug, Clone, Copy, PartialEq)]
struct Item {
    size: f32,
    fill_factor: u16,
}

impl Item {
    fn size_over_fill(&self) -> f32 {
        self.size / self.fill_factor as f32
    }
}

fn item(size: f32, fill_factor: u16) -> Item {
    Item { size, fill_factor }
}

fn allocate_space(items: Vec<Item>, available_space: f32) -> Vec<f32> {
    assert!(
        items.iter().map(|i| i.size).sum::<f32>() <= available_space,
        "Sum of current sizes is smaller than total available space"
    );

    // Implementation
    let mut fill_factor_sum = items.iter().map(|i| i.fill_factor).sum::<u16>();
    let fixed_space = items
        .iter()
        .filter_map(|i| (i.fill_factor == 0).then_some(i.size))
        .sum::<f32>();
    let mut size_sum = available_space;

    let sorted_items = sort_items(items.clone());

    let mut new_sizes = sorted_items
        .iter()
        .map(|(i, item)| {
            let fill_size =
                item.fill_factor as f32 / fill_factor_sum as f32 * size_sum;
            let new_size = if item.size < fill_size {
                fill_size
            } else {
                item.size
            };
            size_sum -= new_size;
            fill_factor_sum -= item.fill_factor;
            (i, new_size)
        })
        .collect::<Vec<_>>();

    // Sort the elements back into original order
    new_sizes.sort_by(|(a, _), (b, _)| a.cmp(&b));

    // Constraints on the result
    for ((_, new_size), Item { size, fill_factor }) in
        new_sizes.iter().zip(&items)
    {
        assert!(
            new_size >= size,
            "Allocated space must not be smaller than the starting size"
        );
        if *fill_factor == 0u16 {
            assert_eq!(
                new_size, size,
                "Items with a fill factor of zero must keep their original
                size. Original size: {}, new size: {}",
                size, new_size
            );
        }
    }
    assert!(
        new_sizes.iter().map(|i| i.1).sum::<f32>() == available_space,
        "Should use all available space. Space used: {}, available_space: {}",
        new_sizes.iter().map(|i| i.1).sum::<f32>(),
        available_space
    );

    new_sizes.into_iter().map(|(_, size)| size).collect()
}

fn sort_items(items: Vec<Item>) -> Vec<(usize, Item)> {
    let mut items = items.into_iter().enumerate().collect::<Vec<_>>();
    items.sort_by(|a, b| {
        if a.1.fill_factor == 0 {
            return Ordering::Less;
        } else if b.1.fill_factor == 0 {
            return Ordering::Greater;
        }

        b.1.size_over_fill().total_cmp(&a.1.size_over_fill())
    });
    items
}

#[cfg(test)]
mod tests {
    use float_cmp::assert_approx_eq;

    use super::*;

    #[test]
    fn sort_correctly() {
        let item_a = item(1., 1);
        let item_b = item(1., 0);

        assert_eq!(
            sort_items(vec![item_a, item_b]),
            vec![(1, item_b), (0, item_a)]
        );

        let item_a = item(1., 1);
        let item_b = item(1., 0);
        let item_c = item(2., 1);
        let item_d = item(2., 3);
        assert_eq!(
            sort_items(vec![item_a, item_b, item_c, item_d]),
            vec![(1, item_b), (2, item_c), (0, item_a), (3, item_d)]
        );
    }

    #[test]
    fn enough_space_for_relative_fill_factors() {
        assert_eq!(
            allocate_space(vec![item(1., 1), item(1., 1)], 2.),
            vec![1., 1.]
        );
        assert_eq!(
            allocate_space(vec![item(1., 1), item(1., 1)], 4.),
            vec![2., 2.]
        );
        assert_eq!(
            allocate_space(vec![item(1., 1), item(1., 1)], 5.),
            vec![2.5, 2.5]
        );
    }

    #[test]
    fn not_enough_space_for_relative_fill_factors() {
        assert_eq!(
            allocate_space(vec![item(1., 1), item(2., 1)], 3.5),
            vec![1.5, 2.]
        );
    }

    #[test]
    fn unequal_fill_factors() {
        assert_eq!(
            allocate_space(vec![item(1., 1), item(1., 2)], 2.5),
            vec![1., 1.5]
        );
        assert_eq!(
            allocate_space(vec![item(1., 1), item(1., 2)], 3.),
            vec![1., 2.]
        );
    }

    #[test]
    fn fixed_spaces() {
        assert_eq!(
            allocate_space(vec![item(1., 0), item(2., 1), item(2., 1)], 7.),
            vec![1., 3., 3.]
        );
        assert_eq!(
            allocate_space(vec![item(1., 0), item(2., 1), item(2., 2)], 7.),
            vec![1., 2., 4.]
        );
    }

    #[test]
    fn three_variable_sizes() {
        assert_approx_eq!(
            &[f32],
            &allocate_space(vec![item(1., 1), item(1., 2), item(2., 1)], 4.),
            &[1., 1., 2.]
        );
        assert_approx_eq!(
            &[f32],
            &allocate_space(vec![item(1., 1), item(1., 2), item(2., 1)], 4.5),
            &[1., 1.5, 2.]
        );
        assert_approx_eq!(
            &[f32],
            &allocate_space(vec![item(1., 1), item(1., 2), item(2., 1)], 5.),
            &[1., 2., 2.]
        );
        assert_approx_eq!(
            &[f32],
            &allocate_space(vec![item(1., 1), item(1., 2), item(2., 1)], 6.),
            &[4. / 3., 8. / 3., 2.]
        );
        assert_approx_eq!(
            &[f32],
            &allocate_space(vec![item(1., 1), item(1., 2), item(2., 1)], 7.),
            &[5. / 3., 10. / 3., 2.]
        );
        assert_approx_eq!(
            &[f32],
            &allocate_space(vec![item(1., 1), item(1., 2), item(2., 1)], 8.),
            &[2., 4., 2.]
        );
        assert_approx_eq!(
            &[f32],
            &allocate_space(vec![item(1., 1), item(1., 2), item(2., 0)], 7.),
            &[5. / 3., 10. / 3., 2.]
        );
    }
}