从地图生成组合字符串

Question

我有一张这样的地图：

// 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
}

所有可能排列的不同之处在于我们通过索引指定哪些排列是可能的，我认为这才是真正的难题。

Answer 1

首先，我们需要将 map[int]map[rune]bool 转换为 []map[rune]bool，因为 map 迭代不能保证按键

排序

之后，这是一个递归的方法

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)
    }
}

我们可以用 dfs("", 0, arr) 调用它，其中 arr 被给定 map 转换为 slice 并且答案将在 res 变量中

从地图生成组合字符串

Generating combinatorial string from map

recursion

go

depth-first-search