Use a Function to Find Common Elements in Two Sequences in Swift

Use a function to find common elements in two sequences in Swift

I was able to get it to work by making the return value an Array of T.GeneratorType.Element.

func anyCommonElements <T, U where T: SequenceType, U: SequenceType, T.Generator.Element: Equatable, T.Generator.Element == U.Generator.Element> (lhs: T, rhs: U) -> Array<T.Generator.Element> {
    var toReturn = Array<T.Generator.Element>()
    for lhsItem in lhs {
        for rhsItem in rhs {
            if lhsItem == rhsItem {
                toReturn.append(lhsItem)
            }
        }
    }
    return toReturn
}
anyCommonElements([1, 2, 3], [3])

How to get list of common elements of 2 array in Swift?

You can also use filter and contains in conjunction:

let fruitsArray = ["apple", "mango", "blueberry", "orange"]
let vegArray = ["tomato", "potato", "mango", "blueberry"]

// only Swift 1
let output = fruitsArray.filter{ contains(vegArray, $0) }

// in Swift 2 and above
let output = fruitsArray.filter{ vegArray.contains($0) }
// or
let output = fruitsArray.filter(vegArray.contains)

---

Set vs Array for a single computation of common elements

We consider the following code snippet:

let array1: Array = ...
let array2: Array = ...

// `Array`
let commonElements = array1.filter(array2.contains)

// vs `Set`
let commonElements = Array(Set(array1).intersection(Set(array2)))
// or (performance wise equivalent)
let commonElements: Array = Set(array1).filter(Set(array2).contains)

I have made some (artificial) benchmarks with Int and short/long Strings (10 to 100 Characters) (all randomly generated). I always use array1.count == array2.count

I get the following results:

If you have more than critical #(number of) elements converting to a Set is preferable

data         |  critical #elements
-------------|--------------------
         Int |        ~50
short String |       ~100
 long String |       ~200

Explanation of the results

Using the Array approach uses "Brute force"-search which has time complexity O(N^2) where N = array1.count = array2.count which is in contrast to the Set approach O(N). However the conversion from Array to Set and back is very expensive for large data which explains the increase of critical #elements for bigger data types.

---

Conclusion

For small Arrays with about 100 elements the Array approach is fine but for larger ones you should use the Set approach.

If you want to use this "common elements"-operation multiple times it is advisable to use Sets only if possible (the type of the elements has to be Hashable).

Final Remarks

A conversion from Array to Set is kind of expensive while the conversion from Set to Array is in contrast very inexpensive.

Using filter with .filter(array1.contains) is performance wise faster than .filter{ array1.contains($0) } since:

• the last one creates a new closure (only once) whereas the first one passes only a function pointer
• for the last one the call of the closure creates an additional stack frame which costs space and time (multiple times: O(N))

How to get list of elements of two sequences using Set.intersection

Yes, you can even just init a Set from the input anyway. Doesn't matter if it is Set or Array since your input is Sequence and Set can be init from Sequence. where T.Element: Hashable, T.Element == U.Element already guarantee the element types are the same and can be made as Set

func getCommonElements<T: Sequence, U: Sequence>(_ lhs: T, _ rhs: U) -> [T.Element] 
    where T.Element: Hashable, T.Element == U.Element
{
   return Array(Set<T.Element>(lhs).intersection(Set<U.Element>(rhs)))
}

print(getCommonElements(["FirstName", "MiddleName", "LastName"], ["FirstName", "LastName"]))
let elementsSet1 = Set<Double>([1.2, 2.4, 3.6])
let elementsSet2 = Set<Double>([1.2, 3.6])
print(getCommonElements(elementsSet1, elementsSet2))

output:

["FirstName", "LastName"]
[1.2, 3.6]

In Swift I would like to join two sequences in to a sequence of tuples

There is already a function for that called Zip2:

var first = [0,1,2,3]
var second = ["zero", "one", "two", "three"]

Array(Zip2(first,second))
// (0, "zero"), (1, "one"), (2, "two"), (3, "three")

This function however does not pad with nil and it also uses the shortest of the two passed in sequences. Notice though that it does not require that the types match between the two sequences and that it takes any sequence, not just arrays.

Here is my own custom implementation of Zip2WithNilPadding:

struct Zip2WithNilPadding<T: SequenceType,U: SequenceType>: SequenceType {
    typealias Generator = GeneratorOf<(T.Generator.Element?, U.Generator.Element?)>

    let first: T
    let second: U

    init(_ first: T, _ second: U) {
        self.first = first
        self.second = second
    }

    func generate() -> Generator {
        var generator1: T.Generator? = first.generate()
        var generator2: U.Generator? = second.generate()

        return GeneratorOf<(T.Generator.Element?, U.Generator.Element?)>() {
            let element1 = generator1?.next()
            let element2 = generator2?.next()
            if element1 == nil && element2 == nil {
                return nil
            }
            else if element1 == nil{
                generator1 = nil
            }
            else if element2 == nil {
                generator2 = nil
            }
            return (element1, element2)
        }
    }
}

var first = [0,1,2]
var second = ["zero", "one", "two", "three", "four"]
Array(Zip2WithNilPadding(first, second))

If you have questions about the specific implementation let me know and I will try to clarify. This implementation should also help you in creating a Zip that takes an array of sequences. Unfortunately in that case they would all have to be a sequence of the same type because you can't have a variable amount of generics.

Swift - Determine if Array1 contains at least one object from Array2

You can do this by simply passing in your array2's contains function into your array1's contains function (or vice versa), as your elements are Equatable.

let array1 = [2, 3, 4, 5]
let array2 = [20, 15, 2, 7]

// this is just shorthand for array1.contains(where: { array2.contains($0) })
if array1.contains(where: array2.contains) {
    print("Array 1 and array 2 share at least one common element")
} else {
    print("Array 1 doesn't contains any elements from array 2")
}

This works by looping through array 1's elements. For each element, it will then loop through array 2 to check if it exists in that array. If it finds that element, it will break and return true – else false.

This works because there are actually two flavours of contains. One takes a closure in order to check each element against a custom predicate, and the other just compares an element directly. In this example, array1 is using the closure version, and array2 is using the element version. And that is the reason you can pass a contains function into another contains function.

---

Although, as correctly pointed out by @AMomchilov, the above algorithm is O(n²). A good set intersection algorithm is O(n), as element lookup is O(1). Therefore if your code is performance critical, you should definitely use sets to do this (if your elements are Hashable), as shown by @simpleBob.

Although if you want to take advantage of the early exit that contains gives you, you'll want to do something like this:

extension Sequence where Iterator.Element : Hashable {

    func intersects<S : Sequence>(with sequence: S) -> Bool
        where S.Iterator.Element == Iterator.Element
    {
        let sequenceSet = Set(sequence)
        return self.contains(where: sequenceSet.contains)
    }
}

if array1.intersects(with: array2) {
    print("Array 1 and array 2 share at least one common element")
} else {
    print("Array 1 doesn't contains any elements from array 2")
}

This works much the same as the using the array's contains method – with the significant difference of the fact that the arraySet.contains method is now O(1). Therefore the entire method will now run at O(n) (where n is the greater length of the two sequences), with the possibility of exiting early.

The elegant solution for function that gives everytime called different element of array(ordered and starting from new when all returned)?

Update: The Swift Algorithms package incorporates exactly this algorithm, under the name Cycle<T>. See https://github.com/apple/swift-algorithms/blob/main/Guides/Cycle.md

This process of "popping" is actually iteration... of a custom sequence.
The appropriate way of representing this in Swift is as a type (struct/class) that implements the IteratorProtocol. I called mine CycleIterator . Iterators are rarely used directly. Rather, they're usually provided by a type that conforms to Sequence. I called mine CycleSequence

The Sequence protocol simply requires the conforming type to provide a function, makeIterator(), which returns an iterator (CycleIterator in my case). Simply by doing this, you instantly gain all of functionality of sequences. Iterability, map/filter/reduce, prefix, suffix, etc.

The IteratorProtocol simply requires that this type provide a function, next(), which yields returns a Element?. The return value is optional, as nil is used to represent the end of a sequence.

Here is how I would implement these:

public struct CycleSequence<C: Collection>: Sequence {
    public let cycledElements: C
    
    public init(cycling cycledElements: C) {
        self.cycledElements = cycledElements
    }
    
    public func makeIterator() -> CycleIterator<C> {
        return CycleIterator(cycling: cycledElements)
    }
}

public struct CycleIterator<C: Collection>: IteratorProtocol {
    public let cycledElements: C
    public private(set) var cycledElementIterator: C.Iterator
    
    public init(cycling cycledElements: C) {
        self.cycledElements = cycledElements
        self.cycledElementIterator = cycledElements.makeIterator()
    }
    
    public mutating func next() -> C.Iterator.Element? {
        if let next = cycledElementIterator.next() {
            return next
        } else {
            self.cycledElementIterator = cycledElements.makeIterator() // Cycle back again
            return cycledElementIterator.next()
        }
    }
}

let s1 = CycleSequence(cycling: [1, 2, 3]) // Works with arrays of numbers, as you would expect.
// Taking one element at a time, manually
var i1 = s1.makeIterator()
print(i1.next() as Any) // => Optional(1)
print(i1.next() as Any) // => Optional(2)
print(i1.next() as Any) // => Optional(3)
print(i1.next() as Any) // => Optional(1)
print(i1.next() as Any) // => Optional(2)
print(i1.next() as Any) // => Optional(3)
print(i1.next() as Any) // => Optional(1)

let s2 = CycleSequence(cycling: 2...5) // Works with any Collection. Ranges work!
// Taking the first 10 elements
print(Array(s2.prefix(10))) // => [2, 3, 4, 5, 2, 3, 4, 5, 2, 3]

let s3 = CycleSequence(cycling: "abc") // Strings are Collections, so those work, too!
s3.prefix(10).map{ "you can even map over me! \($0)" }.forEach{ print($0) }


print(Array(CycleSequence(cycling: [true, false]).prefix(7))) // => [true, false, true, false, true, false, true]
print(Array(CycleSequence(cycling: 1...3).prefix(7))) // => [1, 2, 3, 1, 2, 3, 1]
print(Array(CycleSequence(cycling: "ABC").prefix(7))) // => ["A", "B", "C", "A", "B", "C", "A"]
print(Array(CycleSequence(cycling: EmptyCollection<Int>()).prefix(7))) // => []
print(Array(zip(1...10, CycleSequence(cycling: "ABC")))) // => [(1, "A"), (2, "B"), (3, "C"), (4, "A"), (5, "B"), (6, "C"), (7, "A"), (8, "B"), (9, "C"), (10, "A")]

Here's a shorter, alternate implementation that shows how sequence(state:next:) can be used to achieve a similar thing.

func makeCycleSequence<C: Collection>(for c: C) -> AnySequence<C.Iterator.Element> {
    return AnySequence(
        sequence(state: (elements: c, elementIterator: c.makeIterator()), next: { state in
            if let nextElement = state.elementIterator.next() {
                return nextElement
            }
            else {
                state.elementIterator = state.elements.makeIterator()
                return state.elementIterator.next()
            }
        })
    )
}
    
let repeater = makeCycleSequence(for: [1, 2, 3])
print(Array(repeater.prefix(10)))

How to compare two array and get different elements by swift

Try symmetricDifference:

// ["d"]
Set(["a", "b", "c"]).symmetricDifference(["a", "b", "c", "d"])

Returns a new set with the elements that are either in this set or in the given sequence, but not in both.

How do I check in Swift if two arrays contain the same elements regardless of the order in which those elements appear in?

Swift 3, 4

extension Array where Element: Comparable {
    func containsSameElements(as other: [Element]) -> Bool {
        return self.count == other.count && self.sorted() == other.sorted()
    }
}

// usage
let a: [Int] = [1, 2, 3, 3, 3]
let b: [Int] = [1, 3, 3, 3, 2]
let c: [Int] = [1, 2, 2, 3, 3, 3]

print(a.containsSameElements(as: b)) // true
print(a.containsSameElements(as: c)) // false

---

Spilt Array into pairs

How about this:

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

let pairs = Array(zip(a, a.dropFirst())).map {[$0.0, $0.1] }

print(pairs)

That outputs

[[1, 2], [2, 3], [3, 4], [4, 5], [5, 6], [6, 7], [7, 8], [8, 9]]

Edit:

If you want arbitrary chunk-size, you could write the extension like this:

extension Array {
    func chunks(_ chunkSize: Int, includePartialChunk: Bool = true) -> [[Element]] {
        var indexes = Array<Int>(stride(from: 0, to: count, by: chunkSize - 1))
        if includePartialChunk,
           let last = indexes.last,
           last < count - 1 {
            indexes.append(count-1)
        }
        return zip(indexes, indexes.dropFirst()).map {Array(self[$0.0...$0.1])}
    }
}

Use the parameter includePartialChunk to tell the function if you want to include a "partial chunk" at the end when the array size is not an even multiple of the chunk-size. If true (The default) it returns a last chunk that is smaller than chunkSize but goes to the end of the array. If false, it only returns full-sized chunks, but will skip array elements at the end that don't fit into a full-sized chunk.

(I'll have to study Leo's UnfoldSequence version and see if I can adapt my code to that.)

Finding common elements in two arrays of different size

Sort the arrays. Then iterate through them with two pointers, always advancing the one pointing to the smaller value. When they point to equal values, you have a common value. This will be O(n log n+m log m) where n and m are the sizes of the two lists. It's just like a merge in merge sort, but where you only produce output when the values being pointed to are equal.

def common_elements(a, b):
  a.sort()
  b.sort()
  i, j = 0, 0
  common = []
  while i < len(a) and j < len(b):
    if a[i] == b[j]:
      common.append(a[i])
      i += 1
      j += 1
    elif a[i] < b[j]:
      i += 1
    else:
      j += 1
  return common

print 'Common values:', ', '.join(map(str, common_elements([1, 2, 4, 8], [1, 4, 9])))

outputs

Common values: 1, 4

If the elements aren't comparable, throw the elements from one list into a hashmap and check the elements in the second list against the hashmap.

---

Related Topics