如何找到一组最短的子序列,其中一组字符串的冲突最小

Question

我有一个字符串列表

• Foobar的
• Foobaron
• 脚丫子
• 酒吧椅子
• barfoo
• 自由自在

我想找到一组最短的子序列,这些子序列对于集合中的每个字符串都是唯一的; 每个子序列中的字符不需要相邻,只是它们出现在原始字符串中的顺序.对于上面的例子,那将是(沿着其他可能性)

• Fb(正如它所获得的Foobar一样独特;与Foobaron的碰撞不可避免)
• Fn(Foobaron独有,没有其他...F...n...)
• Ft(脚)
• bs(barstool)
• bf(barfoo)
• e(自由)

是否有一种有效的方法来挖掘这些序列并最小化碰撞字符串的数量(当无法避免碰撞时,例如当字符串是其他字符串的子串时)来自给定的字符串数组？更确切地说,选择长度N,最多N个字符的子序列集合是什么,每个字符识别具有最少数量的冲突的原始字符串.

Answer 1

我不会真正称其为“高效”，但你可以做得比完全愚蠢更好：

words = ['Foobar', 'Foobaron', 'Foot', 'barstool', 'barfoo', 'footloose']
N = 2
n = len(words)
L = max([len(word) for word in words])

def generate_substrings(word, max_length=None):
    if max_length is None:
        max_length = len(word)
    set_substrings = set()
    set_substrings.add('')
    for charac in word:
        new_substr_list = []
        for substr in set_substrings:
            new_substr = substr + charac
            if len(new_substr) <= max_length:
                new_substr_list.append(new_substr)
        set_substrings.update(new_substr_list)
    return set_substrings

def get_best_substring_for_each(string_list=words, max_length=N):
    all_substrings = {}
    best = {}
    for word in string_list:
        for substring in generate_substrings(word, max_length=max_length):
            if substring not in all_substrings:
                all_substrings[substring] = 0
            all_substrings[substring] = all_substrings[substring] + 1
    for word in string_list:
        best_score = len(string_list) + 1
        best[word] = ''
        for substring in generate_substrings(word=word, max_length=max_length):
            if all_substrings[substring] < best_score:
                best[word] = substring
                best_score = all_substrings[substring]
    return best

print(get_best_substring_for_each(words, N))

该程序打印解决方案：

{'barfoo': 'af', 'Foobar': 'Fr', 'Foobaron': 'n', 'footloose': 'os', 'barstool': 'al', 'Foot': 'Ft'}

这仍然可以通过常数因子轻松改进，例如通过存储结果generate_substrings而不是计算两次。

复杂度为O(n*C(N, L+N))，其中 n 是单词数，L 是单词的最大长度，并且C(n, k)是 n 中 k 个元素的组合数量。

我不认为（虽然不确定）在最坏的情况下你可以做得更好，因为在最坏的情况下似乎很难不枚举所有可能的子字符串（最后一个要评估的可能是唯一一个没有冗余的子字符串） ...）。也许平均而言你可以做得更好......