Generating combinatorial string from map

Question

I have a map as such:

// map[int]          position in string
// map[rune]bool     characters possible at said position
func generateString(in map[int]map[rune]bool) []string { 
    // example: {0: {'A':true, 'C': true}, 1: {'E': true}, 2: {'I': true, 'X': true}}
    result := []string{"AEI", "AEX", "CEI", "CEX"} // should generate these
    return result
}

The difference with all possible permutations is that we are specifying which permutations are possible by index and I think that's the real head-breaker here.

Answer 1

First, we need to convert map[int]map[rune]bool to []map[rune]bool since map iteration isn't guaranteed to be sorted by key's

After that, this is a recursive approach

var res []string

func dfs(curString string, index int, in []map[rune]bool) {
    if index == len(in) {
        res = append(res, curString)
        return
    }

    for ch, is := range in[index] {
        if !is { // I assume booleans can be false
            return
        }
        dfs(curString+string(ch), index+1, in)
    }
}

and we can call it with dfs("", 0, arr) where arr is given map converted to slice and answer will be in res variable