0

三元语言的所有单词仅包含 3 个字母：a、b 和 c，并且都具有严格指定的长度 N。在一行中不包含两个相同字母子序列的单词被认为是正确的。例如，abcacb 是正确的词，而 ababc 不是正确的词，因为 ab 子序列到那里。

我试图通过完整枚举所有可能的组合和一个寻找重复序列的函数来解决这个问题。然而，事实证明这是一个错误的决定。需要使用分支定界方法以某种方式解决问题。我完全不知道如何通过这种方法解决这个问题。如果有人向我提供示例或解释，我会非常高兴。我已经花了六天时间来解决这个问题，而且很累。

我的错误解决方案：

import Foundation

func findRepetition(_ p: String) -> [String:Int] {
    var repDict: [String:Int] = [:]
    var p = p
    while p.count != 0 {
        for i in 0...p.count-1 {
            repDict[String(Array(p)[0..<i]), default: 0] += 1
        }
        p = String(p.dropFirst())
    }
    return repDict
}

var correctWords = [String]()
var wrongWords = [String]()
func getRepeats(_ p: String) -> Bool {
    let p = p
    var a = findRepetition(p)
    for i in a {
        var substring = String(Array(repeating: i.key, count: 2).joined())
        if p.contains(substring) {
            wrongWords.append(p)
            return false
        }
    }
    correctWords.append(p)
    return true
}

var counter = 0
func allLexicographicRecur (_ string: [String.Element], _ data: [String], _ last: Int, _ index: Int){
    var length = string.count-1
    var data = data
    for i in 0...length {
        data[index] = String(string[i])
        if index == last {
            if getRepeats(data.joined()) {
                counter += 1
            }
        }else{
            allLexicographicRecur(string, data, last, index+1)
        }

    }
}


func threeLanguage(_ l: Int) {
    var alphabet = "abc"
    var data = Array(repeating: "", count: l)
    allLexicographicRecur(alphabet.sorted(), data, l-1, 0)
    print("The specified word length: \(l), the number of correct words: \(counter)\n")
    print("Correct words:\n\(correctWords)\n")
    print("Wrong words:\n\(wrongWords)")
}


threeLanguage(3)

示例：abca 是正确的词。abab 是错误的 (ab)。aaaa 也是错误的 (a)。abcabc 也不正确 (abc)。

4

1 回答 1

1

如果我正确理解了您的问题，您需要将输入字符串分成 N 长度的部分，并按照您的规则检查部分。像这样

    let constant: Int = 3

    extension String {

    private func components(withLength length: Int) -> [String] {
        return stride(from: 0, to: count, by: length).map {
            let start = index(startIndex, offsetBy: $0)
            let end = index(start, offsetBy: length, limitedBy: endIndex) ?? endIndex
            return String(self[start ..< end])
        }
    }

    var numberOfValidWords: Int {
        var numberOfIncorrectWords = 0
        let length = count - constant
        let array = components(withLength: constant)
        for component in array {
            let computedLength = replacingOccurrences(of: component, with: "").count
            if computedLength != length {
                print("as is lengths are not equal, this part is met in string several times")
                numberOfIncorrectWords += 1
                continue
            }
        }
        return array.count - numberOfIncorrectWords
    }
}

希望它会有所帮助

于 2019-08-05T12:56:06.973 回答