给出一个自然正整数（n）和一个期望的和（k），找到一个长度为n且和为k的随机数组

Question

我想要给定N：Int和K：Int的函数返回数组长度N，从1 ... N的元素和总和K。因此，例如：对于n == 3和k == 7解决方案：[3，1，3]，[3,3,1]，[3,2,2] ...我天真的解决方案是：

func arrayWith(n: Int, k : Int) -> [Int] {
    let elements = (1...n).map { $0 } // We only allow 1,2,3.... till n
    var output = [Int]()
    repeat {
        output.removeAll()
        for _ in 0..<n {
            let validNumbers = elements.filter { $0 + output.reduce(0,+) <= k }
            if let random = validNumbers.randomElement() {
                output.append(random)
            } else {
                break
            }
        }

    } while output.count != n || output.reduce(0,+) != k
    return output
}

此解决方案有效，但是时间复杂度太高。arrayWith（n：7，k：49）（仅可能性[7,7,7,7,7,7,7,7]，需要几秒钟。）

请注意，N，因此不必处理无效案件。

Answer 1

这里是一个非常简单，快速的解决方案，它产生具有给定总和和限制的随机数组：

func arrayWith(n: Int, k: Int) -> [Int] {
    var output: [Int] = []
    var sum = k
    for i in 1...n {
        let lo = max(sum - (n - i) * n, 1)
        let hi = min(sum - (n - i), n)
        let x = Int.random(in: lo...hi)
        sum -= x
        output.append(x)
    }
    return output
}

想法是在1 ... n范围内随机选择每个元素，但也要进行限制，以使其余元素仍可实现给定的总和。

请注意，这是一种非常简单的方法，很可能不会以相同的概率产生所有可能的解决方案。改组输出数组可能会改善这一点。

有关更复杂的解决方案，请查看Random numbers that add to 100: Matlab和Non biased return a list of n random positive numbers (>=0) so that their sum == total_sum，其中使用其他语言和/或以与语言无关的理论方式来解决问题。