arrays - Go でのスライスによるサブセット チェック

Question

スライスが別のサブセットであるかどうかを確認する効率的な方法を探しています。それらを単純に繰り返して確認することもできますが、もっと良い方法が必要だと感じています。

例えば

{1, 2, 3} は {1, 2, 3, 4} のサブセットです {
1, 2, 2} は {1, 2, 3, 4} のサブセットではありません

これを効率的に行うための最良の方法は何ですか?

ありがとう！

Answer 1

サブセットの問題を解決する最も一般的な方法は、マップを使用することだと思います。

package main

import "fmt"

// subset returns true if the first array is completely
// contained in the second array. There must be at least
// the same number of duplicate values in second as there
// are in first.
func subset(first, second []int) bool {
    set := make(map[int]int)
    for _, value := range second {
        set[value] += 1
    }

    for _, value := range first {
        if count, found := set[value]; !found {
            return false
        } else if count < 1 {
            return false
        } else {
            set[value] = count - 1
        }
    }

    return true
}

func main() {
    fmt.Println(subset([]int{1, 2, 3}, []int{1, 2, 3, 4}))
    fmt.Println(subset([]int{1, 2, 2}, []int{1, 2, 3, 4}))
}

重複値をチェックする機能は比較的まれです。上記のコードは、要求どおりに問題を解決します ( http://play.golang.org/p/4_7Oh-fgDQを参照)。重複した値を持つことを計画している場合は、上記のコードのようにカウントを保持する必要があります。値が重複しない場合は、マップ値に整数の代わりにブール値を使用することで、問題をよりコンパクトに解決できます。

Answer 2

スライスがソートされている場合、これで問題ありません。

package main

import "fmt"

// Subset return whether a is a sublist of b. Both a and b must be (weakly) ascending.
func Subset(a, b []int) bool {
    for len(a) > 0 {
        switch {
        case len(b) == 0:
            return false
        case a[0] == b[0]:
            a = a[1:]
            b = b[1:]
        case a[0] < b[0]:
            return false
        case a[0] > b[0]:
            b = b[1:]
        }
    }
    return true
}

func main() {
    cases := []struct {
        a, b []int
        want bool
    }{
        {[]int{1, 2, 3}, []int{1, 2, 3, 4}, true},
        {[]int{1, 2, 2}, []int{1, 2, 3, 4}, false},
    }
    for _, c := range cases {
        if Subset(c.a, c.b) != c.want {
            fmt.Printf("Subset(%v, %v) = %v, want %v\n", c.a, c.b, Subset(c.a, c.b), c.want)
        }
    }
}