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になるようにランダムに選択された例では、合計が超えることができないため、次の2つの数値はN=5ゼロである必要があり、したがってランダム性に偏りがあります)

考えられるもう 1 つの「強引な」方法は、可能なすべての順列のコレクションを生成すること[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);
    }
}

mrequiredを定義しn、randomPosition結果を取得します。このアルゴリズムの複雑さは、事前計算ではO (M*N)、乱数配列の取得では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 に答える