Дайте натуральный положительный Int (n) и искомую сумму (k) найдите случайный массив с длиной n и суммой k - PullRequest
Новая
       4

Дайте натуральный положительный Int (n) и искомую сумму (k) найдите случайный массив с длиной n и суммой k

1 голос
/ 06 апреля 2020

Я хочу, чтобы функция с данными 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], занимает секунды.)

Обратите внимание, что N, поэтому его не нужно обрабатывать недействительные случаи.

1 Ответ

1 голос
/ 06 апреля 2020

Вот очень простое и быстрое решение, создающее случайный массив с заданной суммой и ограничениями: 

func arrayWith(n: Int, k: Int) -> [Int] {
    var output: [Int] = []
    var sum = k // Sum of the remaining elements
    for i in 1...n {
        let lo = max(sum - (n - i) * n, 1) // Minimum possible value for the next number
        let hi = min(sum - (n - i), n) // Maximum possible value for the next number
        let x = Int.random(in: lo...hi)
        sum -= x
        output.append(x)
    }
    return output
}

Идея состоит в том, чтобы выбрать каждый элемент случайным образом в диапазоне 1 ... n, но также ограничены таким образом, что данная сумма все еще достижима с остальными элементами.

Обратите внимание, что это довольно простой подход, который не дает всех возможных решений с равной вероятностью. Перестановка выходного массива может улучшить это немного.

Для более сложных решений взгляните на Случайные числа, которые добавляют к 100: Matlab и Несмещенные возвращают список из n случайных положительные числа (> = 0), так что их сумма == общая_сумма , где проблема решается на других языках и теоретически c.

...