Подмножество суммы Swift

Question

Я хочу использовать динамическое программирование, чтобы получить сумму всех подмножеств из данного массива.

subsets([1,2,3]) = 24
Since the subsets are {1}{2}{3}{1,2}{2,3}{1,3}{1,2,3}

Я пытаюсь вычислить подмножества ([1,2]), что = 6 Моя реализация нижеполучает 5

func subsets(_ arr: [Int]) -> Int {
    var mem = Array(repeating: 0, count: arr.count)
    return subsetsRecursive(arr, 0, &mem)
}

// correct result, but too slow so requires memorization
func subsetsRecursive(_ arr: [Int], _ ptr: Int, _ memo : inout [Int]) -> Int {
    if (ptr > arr.count - 1) {return 0}
    if memo[ptr] != 0 {return memo[ptr]}
    // either take the next number, or don't
    let res = (
        subsetsRecursive(arr, ptr + 1, &memo) + arr[ptr]
            +
        subsetsRecursive(arr, ptr + 1, &memo)
    )
    memo[ptr] = res
    return res
}

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

Answer 1

Проблема с вашим подходом заключается в том, что шаг рекурсии не учитывает с сколько подмножеств текущего элемента arr[ptr] может быть объединено.Например, subsets([1,2]) вычисляет сумму подмножеств {1, 2} и {2}, но опускает подмножество {1}.

Возможное исправление для подхода динамического программирования - помнить не толькосумма, но также число всех подмножеств, начинающихся с определенной позиции:

func subsets(_ arr: [Int]) -> Int {
    var mem = Array(repeating: (sum: 0, count: 0), count: arr.count)
    return subsetsRecursive(arr, 0, &mem).sum
}

func subsetsRecursive(_ arr: [Int], _ ptr: Int, _ memo : inout [(sum: Int, count: Int)]) -> (sum: Int, count: Int) {
    if (ptr > arr.count - 1) { return (sum: 0, count: 1) }
    if memo[ptr].sum != 0 { return memo[ptr] }
    let res = subsetsRecursive(arr, ptr + 1, &memo)
    memo[ptr] = (2 * res.sum + arr[ptr] * res.count, 2 * res.count)
    return memo[ptr]
}

Примеры:

print(subsets([1, 2])) // 6
print(subsets([1, 2, 3])) // 24

Это можно упростить в дальнейшем, но, надеюсь,отвечает на ваш ближайший вопрос.

---

Итерационным решением будет

func subsetsum(_ arr: [Int]) -> Int {
    var sum = 0
    var count = 1
    for elem in arr {
        sum = 2 * sum + count * elem
        count = 2 * count
    }
    return sum
}

, которое можно записать кратко как

func subsetsum(_ arr: [Int]) -> Int {
    return arr.reduce((sum: 0, count: 1)) {
        (2 * $0.sum + $0.count * $1, 2 * $0.count )
    }.sum
}

---

В качестве альтернативы обратите внимание, что каждый из n элементов массиваможет быть в 2 ^n-1 из 2 ⁿ подмножеств:

func subsetsum(_ arr: [Int]) -> Int {
    return arr.reduce(0, +) * (1 << (arr.count - 1))
}

Answer 2

Вы можете сначала получить все элементы подмножества, присоединить их и использовать команду Reduce для суммирования элементов:

extension RangeReplaceableCollection  {
    public var subSets: [SubSequence] {
        return isEmpty ? [SubSequence()] : dropFirst().subSets.lazy.flatMap { [$0, prefix(1) + $0] }
    }
}

---

let subSets = [1,2,3].subSets // [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]

---

let sum = subSets.joined().reduce(0,+)   // 24

или

let sum = subSets.reduce(0) { $1.reduce($0,+) }

Обратите внимание, что, расширяя RangePlaceableCollection и возвращая SubSequence, вы сможете использовать его также с типами StringProtocol, такими как String s и Substring s:

let characters = Array("123")
let charactersSubSets = characters.subSets // [[], ["1"], ["2"], ["1", "2"], ["3"], ["1", "3"], ["2", "3"], ["1", "2", "3"]]
let stringSubSets = "123".subSets // ["", "1", "2", "12", "3", "13", "23", "123"]
let substringSubSets = "1234".dropLast().subSets // ["", "1", "2", "12", "3", "13", "23", "123"]