将一个数字分割成多个范围

Question

我正在尝试将一个数字分割成较小的数字，使其符合预定义的范围，但我似乎无法得到正确的算法。 我正在使用C＃。 示例 将20分为三个数字，其中数字必须符合以下范围：1-3、3-10和0-15。 最终数字可能看起来像这样：1,5,14或2,3,15。

另一个例子是将100分成四个数字，这些数字必须符合以下范围：0-10、0-10、0-40和0-40。 结果自然会是10,10,40,40。 在相同的范围内拆分90可能会导致5,8,38,39等。

你能给我指点方向吗？

（不，这不是作业，这是个人项目）

- Kraken

---

我会研究一下找零计算器应用程序的代码；即使目标不完全相同，你也可能会找到一些想法！ - Alexandre Beaudet

这些范围是否总是连续的？ - Pseudonym

是的，它始终是允许的最小值和最大值。 - Kraken

如何获取每个范围的最小值，对它们进行排序，然后从要拆分的数字的运行总数中减去每个最小值，如果有剩余的总数，则将其添加到最小值中，直到运行总数为0？ - Pseudonym

代码返回满足条件的随机数合适吗？或者如果它对于相同的给定数字和范围始终返回相同的值，那也可以吗？ - Andrew

它应该始终返回随机数。 - Kraken

Answer 1

你可以使用递归来实现。

算法的思路如下：

- 在每次执行中，你需要遍历区间内所有可能的数字。 - 通过递归调用生成下一个区间的数字。 - 如果在任何时候求和超过所需值，则回溯。 - 一旦生成了所有数字，如果总和等于所需数字，则拥有一种可能的组合。

这个方案可以改进，但它是可行的解决方案。

以下代码将在控制台中打印所有有效序列：

SplitNumber(100, new Interval[]
{
    new Interval { Min = 0, Max = 11 },
    new Interval { Min = 0, Max = 11 },
    new Interval { Min = 0, Max = 40 },
    new Interval { Min = 0, Max = 40 },
});

public static void SplitNumber(int n, Interval[] intervals)
{
    SplitNumber(n, 0, intervals, "");
}

public static void SplitNumber(int n, int k, Interval[] intervals, string s)
{
    if (n < 0) return;

    if (k >= intervals.Length) { if (n == 0) Console.WriteLine(s); }
    else
        for (int i = intervals[k].Min; i <= intervals[k].Max; i++)
            SplitNumber(n - i, k + 1, intervals, string.Format("{0} {1}", s, i));
}

Interval 类大致如下：

public class Interval
{
    public int Min { get; set; }
    public int Max { get; set; }
}

- Arturo Menchaca

---

我喜欢这种方法，因为可以得到基本上任何可能的变化。但是这个解决方案有点繁重，因为它必须经过所有区间。非常感谢，这是一个好主意！ - Kraken

Answer 2

以下是一种相当有效的方法，假设桶具有某种排序方式。

首先选择每个范围的最小值并将它们加起来。

如果总和等于您的数字，则停止。

如果总和大于您的数字，则发出错误。

如果总和小于您的数字，则继续。

接下来，从每个范围中减去最小值，以便它们都在0 . . n上标准化，并从您的数字中减去总和。这不是必需的，但有助于解释其余算法。

接下来，对最大范围值进行累积和。找到适合新总和的桶（太大以前的桶但适合）。如果没有找到，则发出错误。

然后分配箱子，使前面的桶达到最大值，并将找到的桶设置为适当的值。

这给您提供了一个符合条件的值集。

如果您想要更多处于范围“中间”的值，请从范围的中间值开始。然后跨所有桶添加或减去值的块，直到达到最大值。这需要更多迭代，但也非常有效。

- Gordon Linoff

Answer 3

试试这个：

List<KeyValuePair<int, int>> ranges = new List<KeyValuePair<int, int>>();
ranges.Add(new KeyValuePair<int, int>(1, 3));
ranges.Add(new KeyValuePair<int, int>(1, 3));
ranges.Add(new KeyValuePair<int, int>(1, 100));

int totalSum = ranges.Sum(i => i.Value - i.Key);

double ws = 0.0;
int rIndex = 0;
var rangeAndWeight = ranges.Select(i => new { index = rIndex++, range = i, maxw = (ws += (double)(i.Value - i.Key) / totalSum) }).ToList();

int[] nums = ranges.Select(i => i.Key).ToArray();

int number = 50;

Random r = new Random();
while (nums.Sum() != number)
{
    double rDouble = r.NextDouble();

    var index = rangeAndWeight.SkipWhile(i => i.maxw < rDouble).First().index;

    if (nums[index] < ranges[index].Value)
        nums[index] += 1;
}

nums数组包含您所需的较小数字

- VDN

---

这是我没有想到的，谢谢你的建议。然而，似乎这个解决方案会遇到一个问题，即较小的范围将比较大的范围更快地填满，这可能不会导致真正的随机分布。我是对的吗？例如，假设范围是1-3、1-3和1-100。要分配的数字是50。它几乎总是会得出3、3和44。 - Kraken

我已经编辑了答案。可能不是最优的，但看起来能正常工作。 - VDN

另一个修正。因为第一和第二个范围是相同的，所以第二个从未被选中。现在已经修复了。 - VDN

是的，之前的版本没有正常工作。我现在正在测试这个版本。由于使用这种算法很难得到极端值（例如，在1-40、1-40、1-20中分配50基本上总是会产生大约20、20、10的值），所以它仍然不完全随机，但它对于解决问题来说还是相当不错的尝试。到目前为止，非常感谢！ - Kraken

让我们在聊天中继续这个讨论。 - Kraken

Answer 4

你可以编写一个程序，尝试在允许的范围内对可能的数字进行求和，并希望结果是正确的。如果结果错误，则需要回溯。但这种方法效率相对较低...

- philimnorden

---

这似乎应该是一条注释，而不是一个答案。 - Pseudonym

@Pseudonym 这是一种有效的随机变量生成技术，被称为“接受/拒绝”方法。它不需要很长时间来描述，但这并不影响它的合法性。 - pjs

如果区间值的组合过大而有效组合过小，那么可能需要花费一些时间。此外，这也不是你应该编写代码的方式。 :P - Andrew