2017-08-30 15:11

# 如何使用不同的数据结构递归遍历地图

I'm trying to figure out the best way to recursively go through a `[string]int` map in Go. I'm building a game in which multiple countries are involved, and grouped together by teams of two in the end.

The goal is to match the first two countries with the lowest 'score' into its own group of two, and add it back to the collection giving the new map a total value of the scores of those countries.

Then recursively doing that to all the groups, ending up with one group and one total value in the end.

``````score := map[string]int{
"US": 2,
"Germany": 3,
"Korea": 4,
}
``````

group1 = `{[US:2] [Germany:3]}` with a total of 5

group1 would now be put back into the initial collection with a 'score' of 5 since it takes the two lowest scores. We would now have:

``````score := map[string]int{
"Korea": 4,
group1: `US:2 Germany:3` with a total of 5
}
``````

If this was now the lowest score in the collection, the next iteration would be:

group2 = `{[Korea:4] [group1:5]}`

`````` score := map[string]int{
group2: `Korea:4 group1:5` with a total of 9
}
``````

And so on until you're left with one.. I think the basic structure should be something like this. However, I'm unsure of the proper way to do this since the data structure is now encompassing a `[string]int` map, as well as this new map.

I realize this is not such a generic question, but could an interface be used for this? I'm very new to Go, so advice would be helpful.

Here is an example to further illustrate what I mean: https://play.golang.org/p/cnkTc0HBY4

• 点赞
• 写回答
• 关注问题
• 收藏
• 复制链接分享
• 邀请回答

#### 3条回答

• duanlu9816 4年前

Your problem can "easy" be solved using a heap data structure.

``````package main

import (
"container/heap"
"fmt"
)

// Something that has a score
type Scoreable interface {
fmt.Stringer
Score() int
}

// A country has a name and a score
type Country struct {
name  string
score int
}

// Country implements Scoreable
func (c Country) Score() int {
return c.score
}

// ... and fmt.Stringer
func (c Country) String() string {
return fmt.Sprintf("%s [%d]", c.name, c.score)
}

// A team consists of two Scoreable's and has itself a score
type Team struct {
team1, team2 Scoreable
score        int
}

// Team implements Scoreable
func (t Team) Score() int {
return t.score
}

// ... and fmt.Stringer
func (t Team) String() string {
return fmt.Sprintf("(%s + %s)", t.team1.String(), t.team2.String())
}

// The heap will be implemented using a slice of Scoreables
type TeamHeap []Scoreable

// TeamHeap implements heap.Interface
func (th TeamHeap) Len() int {
return len(th)
}

func (th TeamHeap) Less(i, j int) bool {
return th[i].Score() < th[j].Score()
}

func (th TeamHeap) Swap(i, j int) {
th[i], th[j] = th[j], th[i]
}

func (th *TeamHeap) Push(t interface{}) {
*th = append(*th, t.(Scoreable))
}

func (th *TeamHeap) Pop() interface{} {
old := *th
n := len(old)
t := old[n-1]
*th = old[0 : n-1]
return t
}

// The main function
func main() {

// Create a heap and initialize it
teams := &TeamHeap{}
heap.Init(teams)

// Push the countries (NB: heap.Push(), not teams.Push())
heap.Push(teams, Country{"US", 2})
heap.Push(teams, Country{"Germany", 3})
heap.Push(teams, Country{"Korea", 4})

// Take the two teams with lowest score and make a new team of them
// Repeat this until there's only one team left
for teams.Len() > 1 {
t1 := heap.Pop(teams).(Scoreable)
t2 := heap.Pop(teams).(Scoreable)
heap.Push(teams, Team{t1, t2, t1.Score() + t2.Score()})
}

// Print the teams that we now have in the heap
for teams.Len() > 0 {
t := heap.Pop(teams).(Team)
fmt.Println(t)
}
}
``````

You can find runnable code on the Go Playground.

点赞 评论 复制链接分享
• dtcu5885 4年前

You can try `map[string]interface{}` with `Type assertion`。 Here is the demo

``````package main

import "fmt"

const total = "total"

func GetValue(i interface{}) int {
value, ok := i.(int)
if ok {
return value
}
return i.(map[string]interface{})[total].(int)
}

func main() {
score := map[string]interface{}{
"US":      2,
"Germany": 3,
"Korea":   4,
}
groupCount := 0

for len(score) > 2 {
var (
firstMin  = math.MaxInt32
secondMin = math.MaxInt32
firstKey  = ""
secondKey = ""
)
for k, v := range score {
iv := GetValue(v)
if iv < firstMin {
secondMin = firstMin
secondKey = firstKey
firstMin = iv
firstKey = k
continue
}
if iv < secondMin {
secondMin = iv
secondKey = k
continue
}

}
groupCount++

score[fmt.Sprintf("Group%d", groupCount)] = map[string]interface{}{
firstKey:  score[firstKey],
secondKey: score[secondKey],
total:     GetValue(score[firstKey])+ GetValue(score[secondKey]),
}
delete(score, firstKey)
delete(score, secondKey)
}
fmt.Println(score)
}
``````

点赞 评论 复制链接分享
• duan41497 4年前
``````package main

import (
"container/heap"
"fmt"
)

//Recursive data structure may looks something like
type Group struct {
Score   int
Left    *Group
Right   *Group
Country string
}

//You can use slice to hold them organized in tree
type GrHeap []Group

//To implement your logic you can use stdlib/container/heap Heap interface
//you must implement Heap interface for your slice
func (h GrHeap) Len() int           { return len(h) }
func (h GrHeap) Less(i, j int) bool { return h[i].Score < h[j].Score }
func (h GrHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

func (h *GrHeap) Push(x interface{}) {
// Push and Pop use pointer receivers because they modify the slice's length,
// not just its contents.
*h = append(*h, x.(Group))
}

func (h *GrHeap) Pop() interface{} {
old := *h
n := len(old)
x := old[n-1]
*h = old[0 : n-1]
return x
}

func main() {
//you most likely already have a map
//anyway it will be handy to keep it for convenient access to individual country
score := map[string]int{
"US":      2,
"Germany": 3,
"Korea":   4,
}
//here we allocate heap
gr := make(GrHeap, 0)
//populate it from map
for k, v := range score {
g := Group{v, nil, nil, k}
gr = append(gr, g)
}
//and initialize
heap.Init(&gr)
//and here we use heap magic to implement your logic
for len(gr) > 2 {
l := heap.Pop(&gr).(Group)
r := heap.Pop(&gr).(Group)
ng := Group{l.Score + r.Score, &l, &r, ""}
heap.Push(&gr, ng)
}
fmt.Println(gr)
fmt.Println(gr[1].Left)
fmt.Println(gr[1].Right.Left)
//and you can see it works https://play.golang.org/p/gugJxJb7rr
}
``````
点赞 评论 复制链接分享