ios - 如何从给定的数字中找到一个随机组合，这些数字加起来与 Swift 中的另一个数字相加？

Question

给定一组随机的正整数 A，找到一个整数的随机组合，加起来为 N。

例。

A = [4, 2, 10, 8, 13, 1, ...]  
N = 18  
The possibilities are [10, 8], [4, 13, 1], etc.

集合A 也可以是任意长度并且只能容纳正整数。

N 可以是任何正整数。

我只需要一种数字组合，而不是所有组合。我也想随机选择，这样如果我得到相同的集合，我就不会每次都得到相同的答案，我正在寻找可以在 Swift 中以编程方式执行此操作的最有效方法。

Answer 1

您首先需要创建一种方法来查找原始集合的所有可能子集，正如我在此处发布的 Subset sum Swift .然后你只需要检查是否有任何子集和等于 n:

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

---

let a = [4, 2, 10, 8, 13, 1]
let n = 18
let matches = a.subSets.lazy.filter { $0.reduce(0,+) == n }
print("Matches:", Array(matches.map{Array($0)}))  // Matches: [[10, 8], [4, 13, 1]]

您还可以使用非递归方法，正如您在我在这里发表的另一篇文章中看到的那样 Find all combination of string array in swift .请注意，我采用的第二种方法不将空集视为子集:

extension RangeReplaceableCollection {
    var subSetsNotRecursive : [SubSequence] {
        guard !isEmpty else { return [] }
        let count = self.count
        let n = 1 << count - 1
        var subSequences: [SubSequence] = .init(repeating: SubSequence(), count: n-1)
        (0 ..< n).map {
            var counter = 0
            for element in self {
                if $0 & 1 << counter > 0 {
                    subSequences[$0-1].append(element)
                }
                counter += 1
            }
        }
        return subSequences + [self[...]]
    }
}

---

let matches2 = a.subSetsNotRecursive.lazy.filter { $0.reduce(0,+) == n }
print("Matches2:", Array(matches2.map{Array($0)}))  // Matches2: [[10, 8], [4, 13, 1]]

或进一步扩展。如果您只对总和等于某个值的那些集合感兴趣，则可以在每次完成创建集合时检查附加元素的总和是否等于您想要的值:

extension RangeReplaceableCollection where Element: BinaryInteger {
    func subSetsThatSummedAre(equalTo value: Element) -> [SubSequence] {
        guard !isEmpty else { return [] }
        let count = self.count
        let n = 1 << count - 1
        var subSets: [SubSequence] = []
        (0 ..< n).map {
            var counter = 0
            var sum: Element = 0
            var subSequence = SubSequence()
            for element in self {
                if $0 & 1 << counter > 0 {
                    subSequence.append(element)
                    sum += element
                }
                counter += 1
            }
            if sum == value {
                subSets.append(subSequence)
            }
        }
        if reduce(0, +) == value {
            subSets.append(self[...])
        }
        return subSets
    }
}

---

let matches4 = a.subSetsThatSummedAre(equalTo: n)
print("Matches4:", Array(matches4.map{Array($0)}))  // Matches4: [[10, 8], [4, 13, 1]]