algorithm - 如何使用go识别给定号码的匹配模式？

Question

我正在尝试确定给定电话号码范围的模式匹配，以用于Cisco Communications Manager平台。

本质上，“X”与电话号码中的数字0-9匹配，并且您可以使用[x-y]表示法指定数字范围。

给定电话号码范围01502221000-02072221149(包含150个号码)，这将创建并输出两种模式:020722210XX和020722211 [0-4] X

显然，我希望它可以在提供的任何范围内工作。在给定数字范围的情况下，我似乎无法理解如何生成这些模式。

任何想法将不胜感激。
非常感谢。

Answer 1

我相信我找到了一个不错的算法可以为您解决这个问题。如果其中的任何解释不够详细，我会提前表示歉意，但是其中很多都是直觉，可能难以解释。
我从更简单的案例开始，想出一种方法来从比较中获得最少的模式。对于我的示例，我将比较211234和245245。
经过一番思考，我得出结论，您需要采用较小数字到9的数字范围，并处理较小数字中最低数字的特殊情况。为了更详细地说明，在数字211234中，理想的是将最后一个数字表示为X，但是我们只能在数字可能是[0-9]的情况下做到这一点，在此示例中，唯一不能使用[0-9]的情况是当我们的十位数是3时，因为我们有4的下限。然后，当我们朝着最高有效数字前进时，此逻辑将沿数字的其余部分向上传播。因此，对于下一种情况下的十位数，我们根据上一个4的示例有一个下限，因为当我们专门允许3时，我们正在处理这种情况。因此，对于我们的十个范围，我们以4-9结尾，因为下一位数字不会限制我们的范围。
实际上，直到最高有效位数受要比较的数字之间的范围所限制，我们才受到限制。手工解决了一些问题后，在数字与数字之间明显分开的情况下，我注意到X的金字塔的一种模式:

compare: 211234
to:      245245


21123[4-9]
2112[4-9]X
211[3-9]XX
21[2-9]XXX
2[2-3]XXXX
24[0-4]XXX
245[0-1]XX
2452[0-3]X
24514[0-5]

这是我如何处理它的第一个提示。从最小有效移动开始，利用对称性，但处理我们遇到“金字塔顶端”的情况。尽管这个示例很简单，但是有很多极端情况会引起问题。为了简洁起见，我将不对每个细节进行详细介绍，但我将对每个细节进行简短说明:
如果两个比较的数字之间有一个数字，例如4和6之间，该怎么办？
在这种情况下，只需使用一位数字代替一个范围。
如果两个比较的数字之间没有数字，例如4和5之间，您该怎么办？
在这种情况下，请丢弃要处理数字之间数字的行，因为所有情况都将得到明确处理。
如果范围中的最小数字为8，该怎么办？
在这种情况下，当我们在数字上加1以得到范围的下限时，我们得到9，这意味着我们可以简单地替换为9而不是[9-9]范围
如果范围中的最小数字为9，该怎么办？
在这种情况下，我们根本不用理会这个数字，因为当处理下一个数字时，应该使用X覆盖它
我确定我遗漏了我在代码中处理过的一些极端情况，而我根本没想到将它们放在此列表中。如果您只想发表评论，我愿意澄清代码的任何部分。
下面是我在Go中的刺探。可能会更干燥，但这是我摆弄一点之后想到的。我也是Go的新手，因此请在评论中告知我任何精神上的犯规之处，我会予以纠正。
我不保证这将处理所有情况，但可以处理我抛出的所有情况。由您决定将其转换为一个包含2个字符串的脚本;)
编辑:我刚刚通过问题中的示例(出于某种原因我从未运行过)意识到这并不总是将所提供的范围压缩到最小数量的输出中，但是它应该始终提供涵盖每种情况的模式。尽管存在这个缺点，但我认为这是朝着正确方向迈出的良好一步，您可以以此为基础。如果我有时间来整理一下以前的范围是1-9而特殊情况是0的情况，我将更新答案。最好的方法可能是在第一代人“手动”压缩这些情况之后。

package main

import (
    "strconv"
    "fmt"
)


func getStringFromMinAndMax(min int, max int) (string, bool){
    minstr := strconv.Itoa(min)
    maxstr := strconv.Itoa(max)
    if max == min {
        return minstr, false
    }
    if max < min{
        return minstr, false
    }
    return "["+minstr+"-"+maxstr+"]", true
}
func main(){
    str1 := "211234"
    str2 := "245245"

    diffLength := 0
    for i := 0; i < len(str1); i++{
        diffLength = i+1
        number1, _ := strconv.Atoi(str1[:len(str1)-i-1])
        number2, _ := strconv.Atoi(str2[:len(str2)-i-1])
        if number1 == number2 {
            break
        }

    }

    elems := (diffLength * 2)-1
    output := make([]*[]string, elems+1)
    for i := 0; i < elems; i++ {
        newSlice := make([]string, diffLength)
        output[i] = &newSlice
    }

    for digit := 0; digit < diffLength; digit++ {
        for j := 0; j < diffLength; j++ {
            if j == digit {
                if output[j] != nil {
                    min, _ := strconv.Atoi(string(str1[len(str1)-(digit+1)]))
                    max := 9
                    if digit == diffLength-1 {
                        max, _ = strconv.Atoi(string(str2[len(str1)-(digit+1)]))
                        max = max - 1
                    }
                    if digit != 0{
                        min = min+1
                    }

                    if min < 10 {
                        maxchar := strconv.Itoa(max)[0]
                        minchar := strconv.Itoa(min)[0]
                        newVal, safe := getStringFromMinAndMax(min, max)
                        if digit == diffLength-1 && !safe && (str1[len(str1)-(digit+1)] == maxchar || str2[len(str2)-(digit+1)] == minchar) {
                            output[j] = nil
                        } else {
                            (*output[j])[diffLength-digit-1] = newVal
                        }
                    } else {
                        output[j] = nil
                    }
                }
                if j != diffLength-1 && output[elems-1-j] != nil {
                    min := 0
                    max, _ := strconv.Atoi(string(str2[len(str1)-(digit+1)]))
                    if digit != 0{
                        max = max-1
                    }
                    if max >= 0{
                        newVal, _ := getStringFromMinAndMax(min, max)
                        (*output[elems-1-j])[diffLength-digit-1] = newVal
                    } else {
                        output[elems-1-j] = nil
                    }
                }
            } else {
                if j > digit {
                    if output[j] != nil {
                        (*output[j])[diffLength-digit-1] = "X"
                    }
                    if j != diffLength-1 && output[elems-1-j] != nil {
                        (*output[elems-1-j])[diffLength-digit-1] = "X"
                    }
                } else {
                    if output[j] != nil {
                        (*output[j])[diffLength-digit-1] = string(str1[len(str1)-digit-1])
                    }
                    if j != diffLength-1 && output[elems-1-j] != nil {
                        (*output[elems-1-j])[diffLength-digit-1] = string(str2[len(str2)-digit-1])
                    }
                }
            }
        }
    }


    for _, list := range output {
        if list != nil{
            if len(str1) != diffLength{
                fmt.Printf(str1[:len(str1)-diffLength])
            }
            for _, element := range *list {
                fmt.Printf(element)
            }
            fmt.Printf("\n")
        }
    }
}

脚注:

diffLength是字符串末尾的字符数，它们不一样，我想不到一个比脚本中的字符更好的方法来获取这个数字...

我将输出设置为nil的意思是，“将明确处理此内容，因此将其丢弃”

j是我要为其设置输出的变量...但这也反映到底部，因此我想不出一个简洁的名称来命名它，因此将其保留为j。

digit跟踪我们正在修改的

右边的数字