如何遞歸遍歷地圖使用不同的數據結構

Question

我試圖找出遞歸的[string]int地圖圍棋最好的一段路要走。我正在製作一個遊戲，其中涉及多個國家，並最終由兩隊組成隊伍。

的目標是前兩個國家的最低「分數」到自己組的兩個匹配，並將其添加回集合賦予新地圖這些國家的分數的總價值。

然後遞歸這樣做，所有組，其中一組，最後一個總價值結束了。

例如，如果您有：

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

組1 = {[US:2] [Germany:3]}共5

1組的現在會放回到初始集合與5「分數」，因爲它需要兩個最低的分數。現在，我們將有：

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

如果這是現在在集合中的最低分，下一次迭代是：

組2 = {[Korea:4] [group1:5]}

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

依此類推，直到你留下一個..我認爲基本結構應該是這樣的。不過，由於數據結構現在包含[string]int地圖以及此新地圖，因此我不確定正確的方法。

我意識到這是沒有這樣一個普通的問題，但可能的接口被用於此？我對Go很新，所以建議會有幫助。

這裏是爲了進一步說明我的意思的例子： https://play.golang.org/p/cnkTc0HBY4

Answer 1

您的問題可以「輕鬆」地使用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{"Canada", 7}) 
    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) 
    } 
} 

你可以在Go Playground上找到runnable code。 。

Answer 2

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{ 
     "Canada": 7, 
     "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 
} 

Answer 3

你可以嘗試用map[string]interface{}Type assertion 這裏是演示

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{}{ 
     "Canada": 7, 
     "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) 
} 

這裏是鏈接https://play.golang.org/p/qq5qwAsh1m