algorithm - 随机部分拆分数字

Question

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

如何将一个数字(我们称之为 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

编程语言并不重要。

Answer 1

我刚刚订阅分享关于这个特定问题的结果。我找到了一个令我满意的解决方案，即使显然不是 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;
    }

希望这有助于...