1

这只是我昨晚在床上时想到的一个问题:)。

你如何将一个数字，我们称它为 N，分成 M 个随机部分，以便每个部分具有相同的概率成为从 0 到 N 的数字。

例如：N=5，M=3

该算法应返回如下数组之一：

[0,2,3]   //0 + 2 +3 =5
[1,1,3]  
[0,0,5]  
[3,2,0]  
[2,2,1]  
...etc

编程语言并不重要。

4

4 回答 4

2

我刚刚订阅分享我关于这个特定问题的结果。我已经找到了一个令我满意的解决方案，即使显然这不是 100% 的随机数拆分。但它符合我的需求，而且资源非常少。

我为您提供了该方法的代码（它是一种递归方法），并带有对特定部分的注释（我认为其他部分非常简单）。代码是用 AS3 编写的，但语言很容易阅读：

/**
 * This function splits a unique number into many numbers whose total equals to the one given as a parameter.
 * The function only works for size equals to a power of 2, but I think it can be easily done for any size,
 * by making as many "power of 2" calls as necessary to get a good final result.
 * @param   total The expected value of the sum of the resulting numbers
 * @param   minValue The minimum value each number can take
 * @param   maxValue The maximum value each number can take
 * @param   size The number of numbers we want to split the total into
 * @param   stepNum The step number of the recursive calls. Used to enhance the results of the algorithm.
 * @return
 */
    private function splitTotalInTwo(total:int, minValue:int, maxValue:int, size:int, stepNum:int):Vector.<int>
    {
        var result:Vector.<int> = new Vector.<int>();

        // we determine the min and max values allowed for the random generated number so that it doesn't 
        // make the second group impossible to process with success
        var minRand:int = Math.max(size * minValue, total - (size * maxValue));
        var maxRand:int = Math.min(size * maxValue, total - (size * minValue));

        // the balanceFactor is used to make the split tighter in the early stages of the recursive algorithm, 
        // therefore ensuring a best number distribution in the end. 
        // You can comment the next three lines to see the number distribution of th inital algorithm.
        // You can alsocchange the balancefactor to get which results you like most. 
        // This var good also be passed as parameter to fine tune the algorithm a little bit more.
        var balanceFactor:Number = 0.4;
        var delta:int = Math.floor((maxRand - minRand) * (0.4 / stepNum));
        minRand += delta;
        maxRand -= delta;

        var random:int = Math.floor(Math.random() * (maxRand - minRand)) + minRand;
        if (size > 1)
        {
            result = result.concat(splitTotalInTwo(random, minValue, maxValue, size / 2, stepNum+1), splitTotalInTwo(total - random, minValue, maxValue, size / 2, stepNum+1));
        }
        else 
        {
            result.push(random);
            result.push(total - random);
        }

        return result;
    }

希望这可以帮助...

于 2013-02-21T12:28:11.223 回答
1

假设我们有一种方法可以在 之间生成均匀随机分布的数字[0,N]。M一个明显的方法是在每次生成后更新 N的范围内连续生成随机数[0,N]，因为所有生成的数字的总和必须等于N。您必须在数学上证明这将导致成对的均匀随机分布的集合[x1,x2,....,xM]。我会说这不是微不足道的。（例如您的示例，其中第一个数字被随机选择为 5，以下两个数字必须为零，因为总和不能超过N=5，因此随机性是有偏差的）

您可能会考虑的另一种“蛮力”方法是生成所有可能排列的集合，[x1,x2,....,xM]其中总和为x1+x2+...+xM = N. 如果集合包含Y可能的排列，您可以使用我们之前定义的随机生成器来获取范围内的随机数[1,Y]并从您的集合中选择该元素

请注意，这只是我的想法，如果你想确保真正随机的均匀分布，你必须在数学上检查这些建议。

编辑：我也刚刚意识到，他们可能以您描述问题的方式，数字拆分的顺序无关紧要（即与 相同[0,2,3]）。这减少了分组集合中总唯一排列的数量[2,3,0][0,3,2]Y

于 2013-01-29T13:11:27.703 回答
0

你可以试试我的方法。最初我计算了可能结果的数量，然后选择随机（在 C# 上实现）：

class Program
{
    private static int[,] dp;

    private static void Populate(int m, int n)
    {
        dp[0, 0] = 1;
        for (int i = 1; i <= m; i++)
        {
            dp[i, 0] = 1;
            for (int j = 1; j <= n; j++)
            {
                dp[i, j] = dp[i - 1, j] + dp[i, j - 1];
            }
        }
    }

    private static int[] GetResultAt(int index, int m, int n)
    {
        int[] result = new int[m];

        while (m > 0)
        {
            for (int i = 0; i <= n; i++)
            {
                if (index <= dp[m - 1, i] && dp[m - 1, i] > 0)
                {
                    m--;
                    result[m] = n - i;
                    n = i;
                    break;
                }
                index = index - dp[m - 1, i];
            }
        }

        return result;
    }

    static void Main(string[] args)
    {
        int n = 5;
        int m = 3;
        dp = new int[m + 1, n + 1];
        Populate(m, n);

        int randomPosition = 7;// Random value from 1 and dp[m,n] range.
        int[] result = GetResultAt(randomPosition, m, n);

        Console.WriteLine(result);
    }
}

定义 required m，n并randomPosition得到结果。这个算法的复杂度是O(M*N)用于 precalc 和O(M+N)用于获取随机数组。

于 2013-01-29T13:33:47.040 回答
0 
public static Integer[] sliceUnequally(int value, int numberOfSlices) {
    if (numberOfSlices > value) {
        throw new IllegalArgumentException(
                String.format("!!! Cannot carve %d into %d slices", value, numberOfSlices));
    }

    final Integer[] slices = new Integer[numberOfSlices];

    int allocated = numberOfSlices;
    for (int i = 0; i < numberOfSlices; i++) {
        if (i == (numberOfSlices - 1)) {
            slices[i] = 1 + (value - allocated);
        } else {
            int slice = new Double((value - allocated) * random.nextDouble()).intValue();
            slices[i] = 1 + slice;
            allocated += slice;
        }
    }

    return slices;
}
于 2016-02-05T14:37:34.443 回答