Unexpected behaviour when populating a map using recursion

Question

The goal is to compute all possible slices of length k that can be formed from a set of n strings.

I tried to do it using a simple recursion. Just printing the result works fine. Putting the results in a map yields some unexpected results for odd k's greater than 2.

What causes differences between the map's keys and their corresponding values?

https://play.golang.org/p/_SGrPRFjJ5g

package main

import (
    "fmt"
    "strings"
)

func main() {
    QQM := make(map[string][]string)
    
    states := []string{
        "a",
        "b",
    }

    var perm func(Q []string, k int)

    perm = func(Q []string, k int) {
        if k == 0 {
            QQM[strings.Join(Q, "")] = Q
            fmt.Println(QQM)
            return
        }

        for i := 0; i < len(states); i++ {
            perm(append(Q, states[i]), k-1)
        }
    }

    perm([]string{}, 4)
}

map[aaaa:[a a a a]]
map[aaaa:[a a a b] aaab:[a a a b]]
map[aaaa:[a a a b] aaab:[a a a b] aaba:[a a b a]]
...

score 3 · Accepted Answer · answered May 27 '21 at 19:07

A slice is a view of an underlying array. When you pass slices around, you are not passing the values they contain, but references to those values. So when you put a slice to a map then add elements to that slice, if the slice has the capacity, you would be adding elements to the slice in the map as well.

Copy the slice before putting into the map:

newQ:=make([]string,len(Q))
copy(newQ,Q)
QQM[strings.Join(Q, "")] = newQ

Unexpected behaviour when populating a map using recursion

1 Answers1