Swift: efficiently get the union of two Arrays (not Sets)-CodePudding

I have a situation where I need the union specifically of two Arrays, not Sets — i.e., the result is ordered and can contain duplicates.

So if I have

let input1 = ["A", "B", "F", "E"]

and

let input2 = ["F", "E", "A", "G"]

the result should be:

let result = ["A", "B", "F", "E", "A", "G"]

I say "union" because the output contains both arrays in their original state, as overlapping subarrays, each of which is identical to the original. The goal is to concatenate the two arrays without duplicating the shared suffix/prefix, if one exists. The canonical way to do something similar is with Sets, but that would of course remove the second "A".

CodePudding user response：

Here is a brute force solution where I start by finding the last position in the first array of the first element of the second array and then directly compare the end of the first array with the start of the second array using the found index to create sub arrays.

let first = ["A", "B", "F", "E"]
let second = ["F", "E", "A", "G"]

let result: [String]
if let firstIndex = first.lastIndex(of: second[0]) {
    let secondIndex = second.index(second.endIndex, offsetBy: -first[firstIndex..<first.endIndex].count)

    if first[firstIndex..<first.endIndex] == second[second.startIndex..<secondIndex] {
        result = first   second[secondIndex..<second.endIndex]
    } else {
        result = first   second
    }
} else {
    result = first   second
}

Note that I haven't tested for any edge cases here, just the sample given in the question with some simple variants.

CodePudding user response：

Just for fun you can use starts with predicate while iterating your first sequence from the end as follow:

let first: [String] = ["A", "B", "F", "E"]
let second: [String] = ["F", "E", "A", "G"]

var pos = first.endIndex
while pos > first.startIndex,
      second.starts(with: first[pos...], by: { $0 != $1}),
      !second.isEmpty {
    first.formIndex(before: &pos)
}

let result = first[..<pos]   second // ["A", "B", "F", "E", "A", "G"]

This will result in a SubSequence, in this case an array slice. If you need an array just explicitly set the resulting type:

let result: [String] = first[..<pos]   second

Based on OP comments if you need to match the subsequence by pairs just offset every two elements:

let first = "ABFF"
let second = "FFAG"

var pos = first.endIndex
while pos > first.startIndex,
      second.starts(with: first[pos...], by: { $0 != $1 }),
      !second.isEmpty {
    first.formIndex(&pos, offsetBy: -2)
}

let result: String = first[..<pos]   second  // "ABFFAG"

If you need the string elements separated by spaces:

var first = "A B C D E F G D E"
var second = "D E F C B A"

first.removeAll(where: \.isWhitespace)
second.removeAll(where: \.isWhitespace)

var pos = first.endIndex
while pos > first.startIndex,
      second.starts(with: first[pos...], by: { $0 != $1 }),
      !second.isEmpty {
    first.formIndex(&pos, offsetBy: -2)
}

let result = (first[..<pos]   second)
                 .map(String.init)
                 .joined(separator: " ")
result  // "A B C D E F G D E F C B A"

CodePudding user response：

This seems to work for what I need. The one thing I don't like is the check on (tail.count > second.count), which feels like a hack...

var first: [String] = ["at", "by", "chicken", "dog", "eat", "for", "good", "dog", "eat"]
var second: [String] = ["dog", "eat", "feed", "cats", "bonk", "atrophe"]

var head: [String] = []
var tail: [String] = []
for i in stride(from: first.count-1, through: 0, by: -1) {
    tail = Array(first[i ..< first.count])
    if (tail.count > second.count) || !(Array(second[0 ..< tail.count]) == tail) {
        tail = []
    } else {
        head = Array(first[0 ..< i])
    }
}
let result = head   second
print(result) // ["at", "by", "chicken", "dog", "eat", "for", "good", "dog", "eat", "feed", "cats", "bonk", "atrophe"]

Thanks for the responses; they definitely helped me get there. Yes, even downvotes helped by providing adrenaline.