Блог

Можно ли найти, существует ли последовательность элементов в массиве? Давайте возьмем несколько цифр из числа Pi,

  let piDigits=[3,1,4,1,5,9,2,6,5,3,5,8,9,7,9,3,2,3,8,4,6,2,6,4,3,3,8,3,2,7,9,5,0,2,8,8,4,1,9,7,1,6,9,3,9,9,3,7,5,1,0,5,8,2,0,9,7,4,9,4,4] 
  

Теперь я хочу найти, существуют ли 5 и 9 в качестве элементов последовательности в массиве — в данном случае они существуют один раз в позициях 4 и 5.

В идеале я бы не хотел перебирать массив с помощью цикла, я бы хотел что-то похожее на array.contains(элемент) .

@Bawpotter, фрагмент кода:

  for element in piDigits{  //check every element
  if element == 5 { //if element is equal with the element i want
    var currentPosition = piDigits.index(of: element) //get the position of that element
    if piDigits[currentPosition! 1] == 9 { //if the element at the next position is equal to the other element i want
        print("true")   // it prints true 7 times, instead of 1!
    }
  }
}
  

Вы можете фильтровать свои индексы, где его подпоследовательность elementsEqual имеет значение true:

 extension Collection where Element: Equatable {
    func firstIndex<C: Collection>(of collection: C) -> Index? where C.Element == Element {
        guard !collection.isEmpty else { return nil }
        let size = collection.count
        return indices.dropLast(size-1).first {
            self[$0..<index($0, offsetBy: size)].elementsEqual(collection)
        }
    }
    func indices<C: Collection>(of collection: C) -> [Index] where C.Element == Element {
        guard !collection.isEmpty else { return [] }
        let size = collection.count
        return indices.dropLast(size-1).filter {
            self[$0..<index($0, offsetBy: size)].elementsEqual(collection)
        }
    }
    func range<C: Collection>(of collection: C) -> Range<Index>? where C.Element == Element {
        guard !collection.isEmpty else { return nil }
        let size = collection.count
        var range: Range<Index>!
        guard let _ = indices.dropLast(size-1).first(where: {
            range = $0..<index($0, offsetBy: size)
            return self[range].elementsEqual(collection)
        }) else {
            return nil
        }
        return range
    }
    func ranges<C: Collection>(of collection: C) -> [Range<Index>] where C.Element == Element {
        guard !collection.isEmpty else { return [] }
        let size = collection.count
        return indices.dropLast(size-1).compactMap {
            let range = $0..<index($0, offsetBy: size)
            return self[range].elementsEqual(collection) ? range : nil
        }
    }
}
  

 [1, 2, 3, 1, 2].indices(of: [1,2])   // [0,3]
[1, 2, 3, 1, 2].ranges(of: [1,2])    // [[0..<2], [3..<5]]
  

Если вам нужно только проверить, содержит ли коллекция подпоследовательность:

 extension Collection where Element: Equatable {
    func contains<C: Collection>(_ collection: C) -> Bool where C.Element == Element  {
        guard !collection.isEmpty else { return false }
        let size = collection.count
        for i in indices.dropLast(size-1) where self[i..<index(i, offsetBy: size)].elementsEqual(collection) {
            return true
        }
        return false
    }
}
  

 [1, 2, 3].contains([1, 2])  // true
  

Очень простая реализация с использованием линейного поиска:

 let piDigits: [Int] = [3,1,4,1,5,9,2,6,5,3,5,8,9,7,9,3,2,3,8,4,6,2,6,4,3,3,8,3,2,7,9,5,0,2,8,8,4,1,9,7,1,6,9,3,9,9,3,7,5,1,0,5,8,2,0,9,7,4,9,4,4]

let searchedSequence: [Int] = [5, 9]

var index = 0
var resultIndices: [Int] = []

while index < (piDigits.count - searchedSequence.count) {
    let subarray = piDigits[index ..< (index   searchedSequence.count)]

    if subarray.elementsEqual(searchedSequence) {
        resultIndices.append(index)
    }

    index  = 1
}

print("Result: (resultIndices)")
  

Существуют и другие варианты, например, вы можете продолжать отбрасывать первый символ из piDigits во время итерации и проверять piDigits , начинается ли с searchedSequence .

Если производительность критична, я рекомендую использовать алгоритм поиска строк, например, Aho-Corasick (см. https://en.wikipedia.org/wiki/String_searching_algorithm ), который сначала создает конечный автомат для быстрого сравнения (аналогично регулярным выражениям).

Давайте посмотрим, как можно использовать регулярные выражения:

 let searchedSequences: [[Int]] = [[5, 9], [7], [9, 2]]

let stringDigits = piDigits.map { String($0) }.joined()
let stringSearchedSequences = searchedSequences.map { sequence in sequence.map { String($0) }.joined() }

let regularExpressionPattern = stringSearchedSequences.joined(separator: "|")

let regularExpression = try! NSRegularExpression(pattern: regularExpressionPattern, options: [])

let matches = regularExpression.matches(in: stringDigits, options: [], range: NSRange(location: 0, length: stringDigits.characters.count))
let matchedIndices = matches.map { $0.range.location }

print("Matches: (matchedIndices)")
  

Недостатком подхода является то, что он не будет искать перекрывающиеся диапазоны (например, «592» соответствует двум диапазонам, но сообщается только об одном).

Внутри метода contains выполняется итерация по массиву, и здесь вы должны сделать то же самое. Вот пример:

 extension Array where Element: Equatable {
  func contains(array elements: [Element]) -> Int {
    guard elements.count > 0 else { return 0 }
    guard count > 0 else { return -1 }

    var ti = 0

    for (index, element) in self.enumerated() {
      ti = elements[ti] == element ? ti   1 : 0

      if ti == elements.count {
        return index - elements.count   1
      }
    }

    return -1
  }
}
  

И вот как это использовать:

 let index = [1, 4, 5, 6, 6, 9, 6, 8, 10, 3, 4].contains(array: [6, 8, 10])
// index = 6

let index = [1, 4, 5, 6, 6, 9, 6, 8, 10, 3, 4].contains(array: [6, 8, 1])
// index = -1
  

 let firstSeqNum = 5
let secondSeqNum = 9
for (index, number) in array.enumerated() {
    if  number == firstSeqNum amp;amp; array[index 1] == secondSeqNum {
        print("The sequence (firstSeqNum), (secondSeqNum) was found, starting at an index of (index).")
    }
}
  

Поскольку для этого нет встроенного метода, это будет ваш лучший вариант.