将一个随机值分成四个数，使它们的和等于原始值

Question

将一个随机值分成四个数，使它们的和等于原始值

algorithmswiftmath

3

我有一个值为24，同时我有四个文本框。如何动态生成四个值，使它们加起来为24？

所有的值必须是整数，不能为负数，并且结果不能是6、6、6、6；它们必须不同，例如：8、2、10、4（但5、6、6、7是可以的）。

- da1lbi3

1

这些值都是整数吗？这些值可以为负数吗？ - Alex Pan

@vacawama 是的，那是一个有效的解决方案。 - da1lbi3

0允许吗？24,0,0,0是一个有效的解决方案吗？ - vacawama

7

如果你必须在纸上解决问题，例如使用一对骰子来生成随机数，就忘记Objective-C、Swift等编程语言吧。你会如何解决这个问题？ - Hot Licks

3

@HotLicks 喜欢这个吗：XKCD 随机数？ - zaph

显示剩余5条评论

7个回答

2

针对您提出的问题，可以生成所有可能解的数组，然后随机选择一个解。实际上，有1,770种可能的解决方案。

var solutions = [[Int]]()

for i in 1...21 {
    for j in 1...21 {
        for k in 1...21 {
            let l = 24 - (i + j + k)
            if l > 0 && !(i == 6 && j == 6 && k == 6) {
                solutions.append([i, j, k, l])
            }
        }
    }
}

// Now generate 20 solutions
for _ in 1...20 {
    let rval = Int(arc4random_uniform(UInt32(solutions.count)))
    println(solutions[rval])
}

这样做可以避免任何偏见，但需要付出初始设置时间和存储成本。

可通过以下方式进行改进:

只存储前三个数字，第四个数字始终为24减去前三个数字之和，以减少存储空间。
将每个解决方案作为单个整数存储，例如：(i * 10000 + j * 100 + k)，以减少存储空间。
通过意识到每个循环不需要达到21，加快解决方案的生成速度。

以下是将每个解决方案作为单个整数存储，并优化循环的解决方案：

var solutions = [Int]()

for i in 1...21 {
    for j in 1...22-i {
        for k in 1...23-i-j {
            if !(i == 6 && j == 6 && k == 6) {
                solutions.append(i * 10000 + j * 100 + k)
            }
        }
    }
}

// Now generate 20 solutions
for _ in 1...20 {
    let rval = Int(arc4random_uniform(UInt32(solutions.count)))
    let solution = solutions[rval]

    // unpack the values
    let i = solution / 10000
    let j = (solution % 10000) / 100
    let k = solution % 100
    let l = 24 - (i + j + k)

    // print the solution
    println("\([i, j, k, l])")
}

- vacawama

循环可以设置为21-先前的值吗？这会再次导致偏差问题。或者你还能将循环设置为什么？ - milo526

1

@milo526，使循环更有效率不会引入偏差，因为它们正在生成所有可能的解决方案。只要您没有错过任何一个，就没有问题。 - vacawama

1

func getRandomValues(amountOfValues:Int, totalAmount:Int) -> [Int]?{
    if amountOfValues < 1{
        return nil
    }

    if totalAmount < 1{
        return nil
    }

    if totalAmount < amountOfValues{
        return nil
    }

    var values:[Int] = []
    var valueLeft = totalAmount

    for i in 0..<amountOfValues{

        if i == amountOfValues - 1{
            values.append(valueLeft)
            break
        }
       var value = Int(arc4random_uniform(UInt32(valueLeft - (amountOfValues - i))) + 1)
        valueLeft -= value
        values.append(value)
    }

    var shuffledArray:[Int] = []

    for i in 0..<values.count {
        var rnd = Int(arc4random_uniform(UInt32(values.count)))
        shuffledArray.append(values[rnd])
        values.removeAtIndex(rnd)
    }

    return shuffledArray
}

getRandomValues(4, 24)

这不是最终答案，但应该是一个（好的）起点。

它需要两个参数。随机值的数量（在您的情况下为4）和总量（在您的情况下为24）。

它从总金额到0之间取一个随机值，将其存储在数组中，并将其从存储剩余金额的变量中减去并存储新值。

然后它从剩余的金额到0之间再次取一个新的随机值，将其存储在数组中，并将其从剩余的金额中再次减去并存储新值。

当需要最后一个数字时，它查看剩余的金额并将其添加到数组中。

编辑：

将随机值加上+1可消除在数组中有0的问题。

编辑2：

打乱数组可以消除第一个值为高值的概率增加的问题。

- milo526

2

由于范围不断缩小，连续值的成功偏差会变小。 - zaph

1

@zaph 如果你的第一个项目很小，第二个项目可以很大。此外，打乱数组也可以解决这个问题。 - milo526

一共有4个数字，它们的总和为24：第一个数字可以是1到21之间的任意数，第二个数字可以是1到(21-第一个数字)之间的任意数。后面每个数字的取值范围都会变小。例如，如果第一个随机数为10，则下一个随机数不能大于21-10或11。 - zaph

2

当您请求更大的值时，例如16和1000时，偏差变得更加明显：[600, 137, 151, 94, 5, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2]。尽管如此，我认为这个答案正确地解决了OP的需求，考虑到已知的限制... - Eric Aya

1

洗牌数组并不能消除对较小数字的偏向，详见上述评论。洗牌只是掩盖了这种偏向。任何一个数字对另一个数字的依赖都会产生偏向。 - zaph

显示剩余10条评论

1

以下是一种不幸的非确定性但完全随机的解决方案：

对于四个数字中的总和24：
在1到21之间选择四个随机数字
重复此过程，直到数字的总和等于24且它们不全为6。

平均而言，这将循环约100次才能找到解决方案。

- zaph

0

作为一个递归函数，该算法非常好：

func getRandomValues(amount: Int, total: Int) -> [Int] {
    if amount == 1 { return [total] }
    if amount == total { return Array(count: amount, repeatedValue: 1) }
    let number = Int(arc4random()) % (total - amount + 1) + 1
    return [number] + getRandomValues(amount - 1, total - number)
}

并带有安全检查：

func getRandomValues(amount: Int, total: Int) -> [Int]? {
    if !(1...total ~= amount) { return nil }
    if amount == 1 { return [total] }
    if amount == total { return Array(count: amount, repeatedValue: 1) }
    let number = Int(arc4random()) % (total - amount + 1) + 1
    return [number] + getRandomValues(amount - 1, total - number)!
}

正如@MartinR所指出的那样，上面的代码极其有偏差。因此，为了获得输出值的均匀分布，您应该使用以下代码：

func getRandomValues(amount: Int, total: Int) -> [Int] {
    var numberSet = Set<Int>()

    // add splitting points to numberSet
    for _ in 1...amount - 1 {
        var number = Int(arc4random()) % (total - 1) + 1
        while numberSet.contains(number) {
            number = Int(arc4random()) % (total - 1) + 1
        }
        numberSet.insert(number)
    }

    // sort numberSet and return the differences between the splitting points
    let sortedArray = (Array(numberSet) + [0, total]).sort()
    return sortedArray.enumerate().flatMap{
        indexElement in
        if indexElement.index == amount { return nil }
        return sortedArray[indexElement.index + 1] - indexElement.element
    }
}

- Qbyte

这是极其有偏见的。例如，getRandomValues(3, 7) 产生 [5, 1, 1] 的频率比 [1, 1, 5] 高得多。 - Martin R

@MartinR 你说得对，但是这不符合所需的条件吗？因为他没有提到结果数字的顺序？ - Qbyte

我不确定我是否完全理解你的意思，但是[5, 1, 1]也比（例如）[1, 3, 3]或[1, 2, 4]更经常返回。您可以使用我的答案末尾的测试代码进行验证。 - Martin R

@MartinR 您是正确的，它确实存在偏差，但是OP只想要随机数，使它们加起来等于24，而不对它们的分布进行说明。我将添加另一个具有均匀分布的示例。 - Qbyte

0

这里有一个解决方案，应该比其他方法具有更少的偏差。它通过生成所需数量的随机浮点数，将它们相乘或相除直到它们加起来等于目标总数，然后将它们四舍五入为整数来实现。由于四舍五入过程会改变总数，因此我们需要通过添加或减去随机项来纠正它们的总和，以使它们达到正确的数量。

func getRandomDoubles(#count: Int, #total: Double) -> [Double] {
    var nonNormalized = [Double]()
    nonNormalized.reserveCapacity(count)
    for i in 0..<count {
        nonNormalized.append(Double(arc4random()) / 0xFFFFFFFF)
    }
    let nonNormalizedSum = reduce(nonNormalized, 0) { $0 + $1 }
    let normalized = nonNormalized.map { $0 * total / nonNormalizedSum }
    return normalized
}

func getRandomInts(#count: Int, #total: Int) -> [Int] {
    let doubles = getRandomDoubles(count: count, total: Double(total))
    var ints = [Int]()
    ints.reserveCapacity(count)
    for double in doubles {
        if double < 1 || double % 1 >= 0.5 {
            // round up
            ints.append(Int(ceil(double)))
        } else {
            // round down
            ints.append(Int(floor(double)))
        }
    }
    let roundingErrors = total - (reduce(ints, 0) { $0 + $1 })
    let directionToAdjust: Int = roundingErrors > 0 ? 1 : -1
    var corrections = abs(roundingErrors)
    while corrections > 0 {
        let index = Int(arc4random_uniform(UInt32(count)))
        if directionToAdjust == -1 && ints[index] <= 1 { continue }
        ints[index] += directionToAdjust
        corrections--
    }
    return ints
}

*编辑: Martin R 正确指出，这并不像人们期望的那样统一，实际上高度偏向于 1-24 范围中间的数字。我不建议使用这个解决方案，但我仍然保留它，以便其他人知道不要犯同样的错误。

- exists-forall

我进行了一些测试，使用 getRandomInts(count: 3, total: 5) 进行了 100,000 次调用，结果似乎分布不均匀。虽然我不是这方面的专家，但根据https://dev59.com/iWsz5IYBdhLWcg3wNE1q#8068956所述，选择一个随机数向量，然后将其缩放到所需的总和不是一个好的算法。 - Martin R

我运行了4和24的10K次迭代，并获得了以下平均值：6.03、5.98、6.01、5.98，还不错。但是随机性很难确定，这只是在一个维度上进行测量，可能是重要的维度，也可能不是。我知道任何偏见来自哪里，我喜欢这一点，没有对最初有偏差的结果进行修正。 - zaph

请注意，所引用的答案使用了rand()。如果那是"C"库函数（看起来是这样），那么就存在一个主要问题，因为rand()不会产生随机数。正在做的事情与本问题无关。它是将1000万个数字缩小到总和为1.0。我们正在取24个范围内的4个数字。 - zaph

@zaph：该答案中的rand()来自MATLAB，它创建了1000万对范围在0.0到1.0之间的随机数。然后每个对都被减少到总和=1.0。 - Martin R

请看我对@MartinR的回复。缩小比例没有简单的比例因子，它对于不同范围的随机数是不同的。这与将整数随机数转换为浮点数无关。 - zaph

0

一个适用于可能正在寻找此类案例的JavaScript实现：

const numbersSumTo = (length, value) => {
    const fourRandomNumbers = Array.from({ length: length }, () => Math.floor(Math.random() * 6) + 1);
    const res = fourRandomNumbers.map(num => (num / fourRandomNumbers.reduce((a, b) => a + b, 0)) * value).map(num => Math.trunc(num));
    res[0] += Math.abs(res.reduce((a, b) => a + b, 0) - value);
    return res;
}


// Gets an array with 4 items which sum to 100
const res = numbersSumTo(4, 100);
const resSum = res.reduce((a, b) => a + b, 0);

console.log({
  res,
  resSum
});

此外，关于这个问题还可以找到很多不同的方法：https://math.stackexchange.com/questions/1276206/method-of-generating-random-numbers-that-sum-to-100-is-this-truly-random

- Finbar

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Martin R · Accepted Answer

这是一个Swift实现的算法，参考了https://dev59.com/iWsz5IYBdhLWcg3wNE1q#8064754，由于需要所有数字都为正数，稍作修改。

生成N个正随机整数使它们的和为M的方法是：

建立一个数组，包含数字0，后面跟着N-1个不同的1到M-1之间的随机数，最后是数字M。
计算相邻数组元素的差。

在第一步中，我们需要从集合{ 1, ..., M-1 }中随机选择一个大小为N-1的子集。这可以通过遍历此集合并以概率n/m选择每个元素来实现，其中m是我们可以选择的剩余元素数量，n是要选择的剩余元素数量。

不需要将所选的随机数存储在数组中，而是立即计算与先前选择的数字的差，并将其存储。

以下是该函数的代码：

func randomNumbers(#count : Int, withSum sum : Int) -> [Int] {
    
    precondition(sum >= count, "`sum` must not be less than `count`")
    
    var diffs : [Int] = []
    var last = 0        // last number chosen

    var m = UInt32(sum - 1)     // remaining # of elements to choose from
    var n = UInt32(count - 1)   // remaining # of elements to choose
    for i in 1 ..< sum  {
        // Choose this number `i` with probability n/m:
        if arc4random_uniform(m) < n {
            diffs.append(i - last)
            last = i
            n--
        }
        m--
    }
    diffs.append(sum - last)
    
    return diffs
}

println(randomNumbers(count: 4, withSum: 24))

如果不允许所有元素相等的解决方案（例如6 + 6 + 6 + 6 = 24），则可以重复使用该方法，直到找到有效的解决方案：

func differentRandomNumbers(#count : Int, withSum sum : Int) -> [Int] {

    precondition(count >= 2, "`count` must be at least 2")

    var v : [Int]
    do {
        v = randomNumbers(count: count, withSum: sum)
    } while (!contains(v, { $0 != v[0]} ))
    return v
}

这是一个简单的测试。它计算了100万个随机表示，其中7被表示为3个正整数的和，并统计结果的分布。

let set = NSCountedSet()
for i in 1 ... 1_000_000 {
    let v = randomNumbers(count: 3, withSum: 7)
    set.addObject(v)
}
for (_, v) in enumerate(set) {
    let count = set.countForObject(v)
    println("\(v as! [Int]) \(count)")
}

结果:

[1, 4, 2] 66786
[1, 5, 1] 67082
[3, 1, 3] 66273
[2, 2, 3] 66808
[2, 3, 2] 66966
[5, 1, 1] 66545
[2, 1, 4] 66381
[1, 3, 3] 67153
[3, 3, 1] 67034
[4, 1, 2] 66423
[3, 2, 2] 66674
[2, 4, 1] 66418
[4, 2, 1] 66292
[1, 1, 5] 66414
[1, 2, 4] 66751

Swift 3更新:

func randomNumbers(count : Int, withSum sum : Int) -> [Int] {
    
    precondition(sum >= count, "`sum` must not be less than `count`")
    
    var diffs : [Int] = []
    var last = 0        // last number chosen
    
    var m = UInt32(sum - 1)     // remaining # of elements to choose from
    var n = UInt32(count - 1)   // remaining # of elements to choose
    for i in 1 ..< sum  {
        // Choose this number `i` with probability n/m:
        if arc4random_uniform(m) < n {
            diffs.append(i - last)
            last = i
            n -= 1
        }
        m -= 1
    }
    diffs.append(sum - last)
    
    return diffs
}

print(randomNumbers(count: 4, withSum: 24))

针对 Swift 4.2（及更高版本），使用统一的随机 API 进行更新：

func randomNumbers(count : Int, withSum sum : Int) -> [Int] {

    precondition(sum >= count, "`sum` must not be less than `count`")

    var diffs : [Int] = []
    var last = 0        // last number chosen

    var m = sum - 1     // remaining # of elements to choose from
    var n = count - 1   // remaining # of elements to choose
    for i in 1 ..< sum  {
        // Choose this number `i` with probability n/m:
        if Int.random(in: 0..<m) < n {
            diffs.append(i - last)
            last = i
            n -= 1
        }
        m -= 1
    }
    diffs.append(sum - last)

    return diffs
}