How can I filter an array from a array of arrays where all the items in one array matches some of the items in another array?

Question

TL/DR

How can I filter an array of arrays in go against an array of strings?

Is there a some or any equivalent of JS/Py in go where I can filter an array of arrays if some or all the items in an array is present in another array?

So for example, consider this as the source array:

arrays := [][]string{
        {"some", "value"},
        {"some", "value", "another"},
        {"value", "another", "test"},
        {"value", "test"},
        {"some", "test"},
    }

And I want to filter arrays by []string{"some", "value"} if all the items here are found in the array.

The expected output is

[[some value] [some value another]]

Altervatively, if I change my filter to []string{"some", "test"}, the expected value is [[some test]]

I can get the logic down quite right in my test code

package main

import "fmt"

func inArray(s string, arr []string) bool {
    for _, a := range arr {
        if s == a {
            return true
        }
    }
    return false
}

func main() {
    arrays := [][]string{
        {"some", "value"},
        {"some", "value", "another"},
        {"value", "another", "test"},
        {"value", "test"},
        {"some", "test"},
    }
    filterBy := []string{"some", "value"}
    hold := make([][]string, 0)
    // Ignore this because it doesnt work as expected
    for _, arr := range arrays {
        for _, f := range filterBy {
            if ok := inArray(f, arr); ok {
                hold = append(hold, arr)
            }
        }
    }
    fmt.Println(hold)
}

Do any of these help you answer the question? https://stackoverflow.com/questions/61641558/golang-append-issue-inside-a-for-loop, https://stackoverflow.com/questions/20185511/range-references-instead-values, https://stackoverflow.com/questions/61618103/why-change-slice-length-in-range-value-not-affected, https://stackoverflow.com/questions/15945030/change-values-while-iterating, https://stackoverflow.com/questions/48826460/using-pointers-in-a-for-loop — JimB, May 14 '20 at 17:16
Hmm... Not entirely. I can see most of these posts are referencing pointers in for loops, or how range works, but doesnt really help me get to where I am trying to get to. — securisec, May 14 '20 at 17:20
You're doing the exact same thing as all those questions by reusing `arr` in each iteration. The overall logic problem are a different matter — JimB, May 14 '20 at 17:25
My apologies. Very new to go, and I dont fully understand your cryptic comments. I guess I can try to re write this where it will return an array of booleans per filter item, and then try to get a boolean value from that array of booleans to replicate a `some` function. — securisec, May 14 '20 at 17:32

score 1 · Accepted Answer · answered May 14 '20 at 17:37

The logic in the inArray function is correct for checking whether a single needle s string is in a haystack arr []string. If you want to extend that to check if all of the needles ss []string are present in a haystack arr []string, then you at least need to loop over the needles as well. Here is an example:

func allInArray(ss []string, arr []string) bool {
    for _, s := range ss {
        if !inArray(s, arr) {
            return false
        }
    }
    return true
}

Here is a working example in the playgound.

For course, this is pretty inefficient because it loops over the haystack arr as many times as there are needles in ss. To make this more efficient, you could pre-process the haystack, turning it into a map[string]struct{}, then check the needles against the keys of the map like so:

func allInArray(ss []string, arr []string) bool {
    present := make(map[string]struct{})
    for _, a := range arr {
        present[a] = struct{}{}
    }
    for _, s := range ss {
        if _, ok := present[s]; !ok {
            return false
        }
    }
    return true
}

Here is a working example in the playground.

This iterates over arr once to create the lookup map, then iterates over ss once, taking advantage of the constant lookup time of the map to check whether or not an element of ss is present in arr.

Creating map for every array is an inefficient solution rather create map of filter array is more efficient — Eklavya, May 14 '20 at 18:29

Eklavya · Answer 2 · 2020-05-14T18:27:02.560

Check for all filter string of array found in each array then decides to append in slice. I added some comments also.

 hold := make([][]string, 0)
 for _, arr := range arrays {
    isValid := true // Initialy set true
    for _, f := range filterBy {
        if ok := inArray(f, arr); !ok {
            isValid = false // if any filter string does match then make false and break
            break
        }
    }
    // If all filter string found the isValid is true, then append in slice
    if(isValid){ 
       hold = append(hold, arr)
    }
}

Full Code in go playground here

But efficient solution is

filterByMap := make(map[string]bool)
// Create a map for filter slice
for _, a := range filterBy {
    filterByMap[a] = true
}
for _, arr := range arrays {
    cnt := 0 // Initial the counter
    for _, a := range arr {
      if filterByMap[a] {
          cnt++  // Increment the counter if filter string found
      }
    }
    // Check if all filter string found ? Append if yes
    if(cnt >= len(filterBy)){ 
         hold = append(hold, arr)
    }
}

Full code here

You're absolutely right--your solution is more efficient, but assumes that each needle appears only once in the haystack. See https://play.golang.org/p/8RsN-mhzYpp for some counterexamples. — PaSTE, May 14 '20 at 20:43
@PaSTE I don't know OP need that aspect also or not, but you are right — Eklavya, May 15 '20 at 03:43

Le Dong Thuc · Answer 3 · 2022-01-03T12:33:00.100

You can use https://github.com/ledongthuc/goterators that support Some() and Every() that I created to reuse aggregate & transforms functions. But with your case, I think you will need to combine with Filter() and Exist() this same lib.

package main

import (
    "fmt"

    "github.com/ledongthuc/goterators"
)

func main() {
    arrays := [][]string{
        {"some", "value"},
        {"some", "value", "another"},
        {"value", "another", "test"},
        {"value", "test"},
        {"some", "test"},
    }

    expected := []string{"some", "value"}
    filteredItems := goterators.Filter(arrays, func(itemList []string) bool {
        for _, expectedItem := range expected {
            if !goterators.Exist(itemList, expectedItem) {
                return false
            }
        }
        return true
    })

    fmt.Println(filteredItems)
}

This lib requires the Go 1.18 to use that support generic + dynamic type you want to use with.

How can I filter an array from a array of arrays where all the items in one array matches some of the items in another array?

TL/DR

3 Answers3