Как найти случайную комбинацию из заданных чисел, которые складываются в другой номер в Swift? - PullRequest
Новая
       48

Как найти случайную комбинацию из заданных чисел, которые складываются в другой номер в Swift?

0 голосов
/ 17 февраля 2019

Учитывая случайный набор положительных целых чисел A, найдите одну случайную комбинацию чисел, которая в сумме составляет N.

Пример.

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

Набор A также может быть любой длины и может содержать только положительные целые числа.

N может быть любым положительным целым числом.

Мне нужна только одна комбинация чисел, а не все.Я также хотел бы выбрать случайным образом, чтобы, если бы мне давали один и тот же набор, я бы не получал каждый раз один и тот же ответ и искал наиболее эффективный способ сделать это программно в Swift.

1 Ответ

0 голосов
/ 17 февраля 2019

Сначала вам нужно создать метод, чтобы найти все возможные подмножества вашей исходной коллекции, как я написал здесь Сумма подмножеств 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]]

Вы также можете использовать нерекурсивный подход, как вы можете видеть в другом посте, который я сделал здесь Найти все комбинации строкового массива в 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]]
...