check for equality on slices without order

Viewed 31757

I am trying to find a solution to check for equality in 2 slices. Unfortanely, the answers I have found require values in the slice to be in the same order. For example, http://play.golang.org/p/yV0q1_u3xR evaluates equality to false.
I want a solution that lets []string{"a","b","c"} == []string{"b","a","c"} evaluate to true.
MORE EXAMPLES
[]string{"a","a","c"} == []string{"c","a","c"} >>> false
[]string{"z","z","x"} == []string{"x","z","z"} >>> true

8 Answers

You can use cmp.Diff together with cmpopts.SortSlices:

less := func(a, b string) bool { return a < b }
equalIgnoreOrder := cmp.Diff(x, y, cmpopts.SortSlices(less)) == ""

Here is a full example that runs on the Go Playground:

package main

import (
    "fmt"

    "github.com/google/go-cmp/cmp"
    "github.com/google/go-cmp/cmp/cmpopts"
)

func main() {
    x := []string{"a", "b", "c"}
    y := []string{"a", "c", "b"}
    
    less := func(a, b string) bool { return a < b }
    equalIgnoreOrder := cmp.Diff(x, y, cmpopts.SortSlices(less)) == ""
    fmt.Println(equalIgnoreOrder) // prints "true"

}

Like adrianlzt wrote in his answer, an implementation of assert.ElementsMatch from testify can be used to achieve that. But how about reusing actual testify module instead of copying that code when all you need is a bool result of the comparison? The implementation in testify is intended for tests code and usually takes testing.T argument.

It turns out that ElementsMatch can be quite easily used outside of testing code. All it takes is a dummy implementation of an interface with ErrorF method:

type dummyt struct{}

func (t dummyt) Errorf(string, ...interface{}) {}

func elementsMatch(listA, listB interface{}) bool {
    return assert.ElementsMatch(dummyt{}, listA, listB)
}

Or test it on The Go Playground, which I've adapted from the adrianlzt's example.

Since I haven't got enough reputation to comment, I have to post yet another answer with a bit better code readability:

func AssertSameStringSlice(x, y []string) bool {
    if len(x) != len(y) {
        return false
    }

    itemAppearsTimes := make(map[string]int, len(x))
    for _, i := range x {
        itemAppearsTimes[i]++
    }

    for _, i := range y {
        if _, ok := itemAppearsTimes[i]; !ok {
            return false
        }

        itemAppearsTimes[i]--

        if itemAppearsTimes[i] == 0 {
            delete(itemAppearsTimes, i)
        }
    }

    if len(itemAppearsTimes) == 0 {
        return true
    }

    return false
}

The logic is the same as in this answer

I know its been answered but still I would like to add my answer. By following code here stretchr/testify we can have something like

  func Elementsmatch(listA, listB []string) (string, bool) {
    aLen := len(listA)
    bLen := len(listB)

    if aLen != bLen {
        return fmt.Sprintf("Len of the lists don't match , len listA %v, len listB %v", aLen, bLen), false
    }

    visited := make([]bool, bLen)

    for i := 0; i < aLen; i++ {
        found := false
        element := listA[i]
        for j := 0; j < bLen; j++ {
            if visited[j] {
                continue
            }
            if element == listB[j] {
                visited[j] = true
                found = true
                break
            }
        }
        if !found {
            return fmt.Sprintf("element %s appears more times in %s than in %s", element, listA, listB), false
        }
    }
    return "", true
}

Now lets talk about performance of this solution compared to map based ones. Well it really depends on the size of the lists which you are comparing, If size of list is large (I would say greater than 20) then map approach is better else this would be sufficent.

Well on Go PlayGround it shows 0s always, but run this on local system and you can see the difference in time taken as size of list increases

So the solution I propose is, adding map based comparision from above solution

func Elementsmatch(listA, listB []string) (string, bool) {
    aLen := len(listA)
    bLen := len(listB)

    if aLen != bLen {
        return fmt.Sprintf("Len of the lists don't match , len listA %v, len listB %v", aLen, bLen), false
    }

    if aLen > 20 {
        return elementsMatchByMap(listA, listB)
    }else{
        return elementsMatchByLoop(listA, listB)
    }

}

func elementsMatchByLoop(listA, listB []string) (string, bool) {
    aLen := len(listA)
    bLen := len(listB)

    visited := make([]bool, bLen)

    for i := 0; i < aLen; i++ {
        found := false
        element := listA[i]
        for j := 0; j < bLen; j++ {
            if visited[j] {
                continue
            }
            if element == listB[j] {
                visited[j] = true
                found = true
                break
            }
        }
        if !found {
            return fmt.Sprintf("element %s appears more times in %s than in %s", element, listA, listB), false
        }
    }
    return "", true
}

func elementsMatchByMap(x, y []string) (string, bool) {
    // create a map of string -> int
    diff := make(map[string]int, len(x))
    for _, _x := range x {
        // 0 value for int is 0, so just increment a counter for the string
        diff[_x]++
    }
    for _, _y := range y {
        // If the string _y is not in diff bail out early
        if _, ok := diff[_y]; !ok {
            return fmt.Sprintf(" %v is not present in list b", _y), false
        }
        diff[_y] -= 1
        if diff[_y] == 0 {
            delete(diff, _y)
        }
    }
    if len(diff) == 0 {
        return "", true
    }
    return "", false
}
Related