生成随机数,每个都是最小尺寸

Question

不确定之前是否曾询问过这个问题,尽管此处也提出了类似的问题.基本上,我正在尝试生成的最小大小的随机整数仍然总和到某个值(不变量是和/(你想要的randoms数)大于最小值.这是一个悲伤的尝试我编码了:

import java.util.Arrays;
import java.util.Random;

public class ScratchWork {

    private static Random rand = new Random();


    public static void main(String[] args) {
            int[] randoms = genRandoms(1000, 10, 30);
            for (int i = 0; i<randoms.length; i++) sop("Random Number "+ (i+1) + ": " + randoms[i]);
            sop("Sum: " + sum(randoms));
    }

    public static int sum(int[] array) { int sum = 0; for (int i : array) sum+=i; return sum; }

    public static int[] genRandoms(int n, int numberOfRandoms, int min) {
        if (min > n/numberOfRandoms) throw new UnsupportedOperationException();
        int[] intRandArray = {0};
        while (sum(intRandArray) != n) {
            ////////////////////////
            // See https://stackoverflow.com/questions/2640053/getting-n-random-numbers-that-the-sum-is-m
            Double[] randArray = new Double[numberOfRandoms];
            double workerSum = 0;
            for (int i = 0; i<numberOfRandoms; i++) {
                randArray[i] = ((double)rand.nextInt(n-1)+1);
                workerSum += randArray[i];
            }

            for (int i = 0; i<randArray.length; i++) {
                randArray[i] = n*(randArray[i]/(workerSum));
            }
            /////////////////////////

            while (existsSmallerNumThanMin(randArray, min)) 
                randArray = continueToFix(randArray, min);

            //Convert doubles to ints
            intRandArray = new int [randArray.length];
            for (int i = 0; i < intRandArray.length; i++) 
                intRandArray[i] = (int)Math.round(randArray[i]);
        }
        return intRandArray;
    }

    public static boolean existsSmallerNumThanMin(Double[] randArray, int min) {
        for (double i : randArray) if (i < (double)min) return true;
        return false;
    }

    public static Double[] continueToFix(Double[]randArray, int min) {
        Double[] tempArray = Arrays.copyOf(randArray, randArray.length);
        Arrays.sort(tempArray);
        int smallest = Arrays.asList(randArray).indexOf(tempArray[0]);
        int largest = Arrays.asList(randArray).indexOf(tempArray[tempArray.length-1]);

        double randomDelta = rand.nextInt(min);

        randArray[smallest]+=randomDelta;
        randArray[largest]-=randomDelta;
        return randArray;
    }

    public static void sop(Object s) { System.out.println(s); }

}

这既不是一种优雅的,也不是一种高性能的方式...它也似乎不能很好地(如果有的话)传入,比方说,(100,10,10),这只允许这个数字数组中有10个.随机数的分布也很糟糕.

有一个优雅的方法吗？

此外,我的最终目标是在Objective-C中实现这一点,尽管我仍然只是学习该语言的绳索,所以任何使用该语言执行此操作的提示都将非常感激.

Answer 1

我做了一些测试,我的Java实现被打破了.我认为我的算法很糟糕.

如何在[0,1]中获得N个随机数并根据它们的总和(不同于所需的总和)对结果进行归一化.然后将这些值乘以所需的数字和.

这假设最小大小为0.概括这一点以保持每个结果的最小值很简单.只是饲料中sum - min * n的sum.添加min到所有结果.

为了避免潜在的浮点问题,您可以使用逻辑上在[0,M](M任意大)M而不是[0,1]上的一系列整数值来执行类似操作.这个想法是相同的,因为你"标准化"你的随机结果.因此,假设你得到N的随机总和(希望N必须是...的倍数,sum+1请参阅REMARK).Divy N按sum+1部分计算.第一部分是0,第二部分是1,......,最后是sum.每个随机值通过查看它所属的N的哪个部分来查找其值.

备注:如果您对任意少量偏差感到满意,请使每个模具的滚动幅度大于sum(可能需要BigInteger).设N为总和.然后N = k*sum + rem在哪里rem < sum.如果N很大,那么rem / k -> 0,这是好的.如果M很大,则N在概率上很大.

算法伪代码:

F(S, N):
    let R[] = list of 0's of size N
    if S = 0: return R[]
    for 0 <= i < N
        R[i] = random integer in [0, M] -- inclusive and (M >= S). M should be an order larger than S. A good pick might be M = 1000*S*N. Not sure though. M should probably be based on both S and N though or simply an outragously large number.
    let Z = sum R[]
    for 0 <= i < N
        R[i] = (Z mod R[i]) mod (S+1)
    return R[]

Java实现:

import java.math.BigInteger;
import java.util.Arrays;
import java.util.Map;
import java.util.Random;
import java.util.TreeMap;


public class Rand {
    private final Random rand;

    public Rand () {
        this(new Random());
    }

    public Rand (Random rand) {
        this.rand = rand;
    }

    public int[] randNums (int total, int minVal, int numRands) {
        if (minVal * numRands > total) {
            throw new IllegalArgumentException();
        }
        int[] results = randNums(total - minVal * numRands, numRands);
        for (int i = 0; i < numRands; ++i) {
            results[i] += minVal;
        }
        return results;
    }

    private int[] randNums (int total, int n) {
        final int[] results = new int[n];
        if (total == 0) {
            Arrays.fill(results, 0);
            return results;
        }
        final BigInteger[] rs = new BigInteger[n];
        final BigInteger totalPlus1 = BigInteger.valueOf(total + 1L);
        while (true) {
            for (int i = 0; i < n; ++i) {
                rs[i] = new BigInteger(256, rand);
            }
            BigInteger sum = BigInteger.ZERO;
            for (BigInteger r : rs) {
                sum = sum.add(r);
            }
            if (sum.compareTo(BigInteger.ZERO) == 0) {
                continue;
            }
            for (int i = 0; i < n; ++i) {
                results[i] = sum.mod(rs[i]).mod(totalPlus1).intValue();
            }
            return results;
        }
    }

    public static void main (String[] args) {
        Rand rand = new Rand();
        Map<Integer, Integer> distribution = new TreeMap<Integer, Integer>();
        final int total = 107;
        final int minVal = 3;
        final int n = 23;
        for (int i = total - (n-1) * minVal; i >= minVal; --i) {
            distribution.put(i, 0);
        }
        for (int i = 0; i < 100000; ++i) {
            int[] rs = rand.randNums(total, minVal, n);
            for (int r : rs) {
                int count = distribution.get(r);
                distribution.put(r, count + 1);
            }
        }
        System.out.print(distribution);
    }

}

Answer 2

基于以下评论中的修订要求。

public static int[] genRandoms(int total, int numberOfRandoms, int minimumValue) {
    int[] ret = new int[numberOfRandoms];
    Random rnd = new Random();
    int totalLeft = total;
    for (int i = 0; i < numberOfRandoms; i++) {
        final int rollsLeft = numberOfRandoms - i;
        int thisMax = totalLeft - (rollsLeft - 1) * minimumValue;
        int thisMin = Math.max(minimumValue, totalLeft / rollsLeft);
        int range = thisMax - thisMin;
        if (range < 0)
            throw new IllegalArgumentException("Cannot have " + minimumValue + " * " + numberOfRandoms + " < " + total);
        int rndValue = range;
        for (int j = 0; j * j < rollsLeft; j++)
            rndValue = rnd.nextInt(rndValue + 1);
        totalLeft -= ret[i] = rndValue + thisMin;
    }
    Collections.shuffle(Arrays.asList(ret), rnd);
    return ret;
}

public static void main(String... args) throws IOException {
    for (int i = 100; i <= 1000; i += 150)
        System.out.println("genRandoms(" + i + ", 30, 10) = " + Arrays.toString(genRandoms(1000, 30, 10)));
}

印刷

genRandoms(100, 30, 10) = [34, 13, 22, 20, 26, 12, 30, 45, 22, 35, 108, 20, 31, 53, 11, 35, 20, 11, 18, 32, 14, 30, 20, 19, 31, 31, 151, 45, 25, 36]
genRandoms(250, 30, 10) = [30, 27, 25, 34, 28, 33, 34, 82, 45, 30, 24, 26, 26, 45, 19, 18, 95, 28, 22, 30, 30, 25, 38, 11, 18, 27, 77, 26, 26, 21]
genRandoms(400, 30, 10) = [48, 25, 19, 22, 36, 65, 24, 29, 49, 24, 11, 30, 33, 41, 37, 33, 29, 36, 28, 24, 32, 12, 28, 29, 29, 34, 35, 28, 27, 103]
genRandoms(550, 30, 10) = [25, 44, 72, 36, 55, 41, 11, 33, 20, 21, 33, 19, 29, 30, 13, 39, 54, 26, 33, 30, 40, 32, 21, 31, 61, 13, 16, 51, 37, 34]
genRandoms(700, 30, 10) = [22, 13, 24, 26, 23, 61, 44, 79, 69, 25, 29, 83, 29, 35, 25, 13, 33, 32, 13, 12, 30, 26, 28, 26, 14, 21, 26, 13, 84, 42]
genRandoms(850, 30, 10) = [11, 119, 69, 14, 39, 62, 51, 52, 34, 16, 12, 17, 28, 25, 17, 31, 32, 30, 34, 12, 12, 38, 11, 32, 25, 16, 31, 82, 18, 30]
genRandoms(1000, 30, 10) = [25, 46, 59, 48, 36, 32, 29, 12, 27, 34, 33, 14, 12, 30, 29, 31, 25, 16, 34, 44, 25, 50, 60, 32, 42, 32, 13, 41, 51, 38]

恕我直言，对结果进行洗牌可以提高分布的随机性。