python - 分区中唯一子字符串的最大数量




string algorithm (5)

您可以使用带有set的递归函数作为第二个参数来跟踪当前路径中的唯一字符串。 对于每次递归,遍历所有索引加1,在该索引处将字符串拆分为可能的候选字符串,如果候选字符串尚未在集合中,则使用剩余字符串并将候选对象添加到集合中进行递归调用要从剩余字符串中获取最大数目的唯一子字符串,请向其添加1并从迭代中返回最大值的最大值。 如果给定字符串为空或所有候选字符串已在集合中,则返回0:

def max_unique_substrings(s, seen=()):
    maximum = 0
    for i in range(1, len(s) + 1):
        candidate = s[:i]
        if candidate not in seen:
            maximum = max(maximum, 1 + max_unique_substrings(s[i:], {candidate, *seen}))
    return maximum

演示: https://repl.it/@blhsing/PriceyScalySphere : https://repl.it/@blhsing/PriceyScalySphere

在Python 3.8中,也可以使用生成器表达式调用 max 函数来编写上述逻辑,该生成器表达式可以过滤已通过赋值表达式“看到”的候选对象:

def max_unique_substrings(s, seen=()):
    return max((1 + max_unique_substrings(s[i:], {candidate, *seen}) for i in range(1, len(s) + 1) if (candidate := s[:i]) not in seen), default=0)

稍微修改了标题以使其更易于理解。

这是详细的版本。 假设我们有一个字符串 s ,我们想将其拆分为一些 子字符串 。 每个子字符串彼此不同。 一次 切割可以拥有的唯一子字符串的最大数量是多少。 换句话说,您可以通过串联这些子字符串来恢复。

这里有些例子:

Example 1
s = 'aababaa'
output = 4
Explain: we can split it into aa|b|aba|a or aab|a|b|aa, 
         and 4 is the max number of substrings we can get from one split.

Example 2
s = 'aba'
output = 2
Explain: a|ba

Example 3
s = 'aaaaaaa'
output = 3
Explain: a|aa|aaaa

注意 s 仅包含小写字符。 不知道 s 是多长,这使我无法猜测最佳时间复杂度。 :(

这是一个NP难题吗? 如果没有,如何有效解决?

我从一个朋友那里听到了这个问题。 我无法解决。 我正在尝试使用Trie +贪婪解决此问题。 但是在第一个例子中它失败了。

这是我想出的特里解决方案:

def triesolution(s):
    trie = {}
    p = trie
    output = 0
    for char in s:
        if char not in p:
            output += 1
            p[char] = {}
            p = trie
        else:
            p = p[char]
    return output

例如1,由于试图将其拆分为 a|ab|abaa ,因此上述代码将返回3。

补充: 谢谢大家的想法,看来这个问题非常接近NP问题。 现在,我正在尝试从这个方向进行思考。 假设我们有一个函数 Guess(n) 。 如果我们可以从一个拆分中找到 n 唯一的子字符串,则此函数将返回 True 否则返回 False 。 这里的一个观察是,如果 Guess(n) == True ,那么对于所有 i <= nGuess(i) == True 。 因为我们可以将两个相邻的子字符串合并在一起。 这种观察可能导致二元解。 但是,仍然需要我们能够非常有效地计算 Guess 函数。 可悲的是,我仍然找不到一种计算 Guess(n) 的多项式方法。


我已经试过考虑这个问题,或者考虑是否要在给定的索引上进行分区。 因此,此函数是递归的,并在每个索引处创建2个分支。不要在索引 i处进行 分区2.在索引i处进行分区。

根据分区,我填写一个集合,然后返回集合的大小

def max(a,b):
    if a>b: return a
    return b



def keep(last, current, inp, map):
    # print last
    # print current
    # print map

    if len(inp) == 2 :
        if inp[0]==inp[1]: return 1
        return 2

    if current >= len(inp):
        return len(map)
    // This is when we are at the start of the string. 
    // In this case we can only do one thing not partition and thus take the entire string as a possible string.

    if current == last :
        map11 = map.copy()
        map11.add(inp[current:])
        return keep(last, current + 1, inp, map11)

    map1 = map.copy();
    if current != (len(inp)-1):
        map1.add(inp[last:current])

    map2 = map.copy()

    return max(keep(last,current+1,inp, map2), keep(current, current+1, inp, map1))

print keep(0,0,"121", set([]))
print keep(0,0,"aaaaaaa", set([]))
print keep(0,0,"aba", set([]))
print keep(0,0,"aababaa", set([]))
print keep(0,0,"21", set([]))
print keep(0,0,"22", set([]))

https://onlinegdb.com/HJynWw-iH


这是一个基于图论的答案。

造型
可以将此问题建模为大小为 O(n²) 的图上的最大独立集问题,如下所示:
w = c_1, ..., c_n 为输入字符串。
G = (V,E) 是无向图,其构建如下:
V = { (a, b) such that a,b in [1, n], a <= b } 。 我们可以看到 V 的大小为 n(n-1)/2 ,其中每个顶点代表 w 的子串。
然后,对于每两个顶点 (a1, b1)(a2, b2) ,我们构建边 ((a1, b1), (a2, b2)) iff
(i) [a1, b1] 相交 [a2, b2]
(ii) c_a1...c_b1 = c_a2...c_b2
换句话说,如果(i)它们表示的子字符串在 w 重叠,或者(ii)两个子字符串相等,则在两个顶点之间建立边。

然后我们可以看到为什么 最大的独立 G 集合 为我们的问题提供了答案。

复杂
在一般情况下,最大独立集(MIS)问题是NP难的,时间复杂度为 O(1.1996^n) 且在多项式空间中 [Xiao,NamaGoshi(2017)]
起初,我认为生成的图将是一个弦图(没有诱导的长度> 3的循环),因为它可以很好地解决此类问题,因此可以在线性时间内解决MIS问题。
但是我很快意识到事实并非如此,找到包含5个或更多长度的诱导循环的示例非常容易。
实际上,结果图不显示我们通常需要的任何“好”属性,并且可以将MIS问题的复杂性降低为多项式。
这只是问题复杂性的上限,因为多项式时间减少仅在一个方向上进行(我们可以将这个问题简化为MIS问题,而不能将其简化为MIS问题,至少不是平凡的)。 所以最终我们在最坏的情况下以 O(1.1996^(n(n-1)/2)) 解决了这个问题。
所以,a,我无法证明它在P中,或者它是NP完整的或NP硬的。 可以肯定的是,问题出在NP,但是我想这对任何人来说都不奇怪。

实作
将这个问题简化为MIS问题的好处是MIS是一个经典问题,可以找到几种实现方案,并且MIS问题也很容易写为ILP。
这是MIS问题的ILP公式:

Objective function 
maximize sum(X[i], i in 1..n)
Constraints:
for all i in 1..n, X[i] in {0, 1}
for all edge (i, j), X[i] + X[j] <= 1

我认为,这应该是解决此问题的最有效方法(将此模型用作MIS问题),因为ILP求解器非常有效,特别是在涉及大型实例时。

这是我使用Python3和 GLPK 求解器完成的实现。 要对其进行测试,您需要与Cplex文件格式兼容的LP解算器。

from itertools import combinations

def edges_from_string(w):
    # build vertices
    vertices = set((a, b) for b in range(len(w)) for a in range(b+1))
    # build edges
    edges = {(a, b): set() for (a, b) in vertices}
    for (a1, b1), (a2, b2) in combinations(edges, 2):
        # case: substrings overlap
        if a1 <= a2 <= b1:
            edges[(a1, b1)].add((a2, b2))
        if a2 <= a1 <= b2:
            edges[(a2, b2)].add((a1, b1))
        # case: equal substrings
        if w[a1:b1+1] == w[a2:b2+1]:
            if a1 < a2:
                edges[(a1, b1)].add((a2, b2))
            else:
                edges[(a2, b2)].add((a1, b1))
    return edges

def write_LP_from_edges(edges, filename):
    with open(filename, 'w') as LP_file:
        LP_file.write('Maximize Z: ')
        LP_file.write("\n".join([
            "+X%s_%s" % (a, b)
            for (a, b) in edges
        ]) + '\n')
        LP_file.write('\nsubject to \n')
        for (a1, b1) in edges:
            for (a2, b2) in edges[(a1, b1)]:
                LP_file.write(
                    "+X%s_%s + X%s_%s <= 1\n" %
                    (a1, b1, a2, b2)
                )
        LP_file.write('\nbinary\n')
        LP_file.write("\n".join([
            "X%s_%s" % (a, b)
            for (a, b) in edges.keys()
        ]))
        LP_file.write('\nend\n')
write_LP_from_edges(edges_from_string('aababaa'), 'LP_file_1')
write_LP_from_edges(edges_from_string('kzshidfiouzh'), 'LP_file_2')

然后可以使用 glpsol 命令解决它们:
glpsol --lp LP_file_1
aababaa 很快就解决了(在我的笔记本电脑上为0.02秒),但是正如预期的那样,随着字符串大小的增加,事情变得(非常)艰难。
该程序仅给出数值(而不是最佳分区),尽管如此,仍可以使用类似的实现(使用诸如 pyomo 的LP解算器/ python接口)找到最佳分区和相应的子字符串。

时间与记忆
aababaa :0.02秒,0.4 MB,值:4
kzshidfiouzh :1.4秒,3.8 MB,值:10
aababababbababab :60.2秒,31.5 MB,价值:8
kzshidfiouzhsdjfyu :207.5秒,55.7 MB,值:14
请注意,LP解算器还提供了解决方案的当前上下限,因此对于最后一个示例,我可以在一分钟后获得实际的解决方案作为下限。


这是一个解决方案,但是它很快就爆炸了,而且远不是有效的解决方案。 它首先将字符串分解为唯一的子字符串列表,而不关心顺序,然后尝试使用itertools.permutation将这些子字符串重新组合回原始字符串,测试EACH置换以查看其是否与原始字符串匹配。

import itertools as it

def splitter(seq):                                                             
    temp = [seq]
    for x in range(1, len(seq)):
        print(seq[:x], seq[x:])
        temp.append(seq[:x])
        temp.append(seq[x:])
    return temp

if __name__ == "__main__":
    test = input("Enter a string: ")
    temp = splitter(test)
    copy = temp[::]
    condition = True
    for x in temp:
        if len(x) > 1:
            copy.extend(splitter(x))
    copy = sorted(list(set(copy)))
    print(copy)
    count = []
    for x in range(len(test)):
        item = it.permutations(copy, x)
        try:
            while True:
                temp = next(item)
                if "".join(list(temp)) == test:
                    if len(temp) == len(set(temp)):
                        count.append((len(temp), temp))
        except StopIteration:
            print('next permutation begin iteration')
            continue
    print(f"All unique splits: {count}")
    print(f"Longest unique split : {max(count)[0]}")

对于第一个测试,我们得到以下信息:

All unique splits: [(1, ('aababaa',)), (2, ('a', 'ababaa')), (2, ('aa', 'babaa')), (2, 
('aab', 'abaa')), (2, ('aaba', 'baa')), (2, ('aabab', 'aa')), (2, ('aababa', 'a')), (3, 
('a', 'ab', 'abaa')), (3, ('a', 'aba', 'baa')), (3, ('a', 'abab', 'aa')), (3, ('aa', 'b',
 'abaa')), (3, ('aa', 'ba', 'baa')), (3, ('aa', 'baba', 'a')), (3, ('aab', 'a', 'baa')),
 (3, ('aab', 'ab', 'aa')), (3, ('aab', 'aba', 'a')), (3, ('aaba', 'b', 'aa')), (3,
 ('aaba', 'ba', 'a')), (4, ('a', 'aba', 'b', 'aa')), (4, ('aa', 'b', 'a', 'baa')), (4,
 ('aa', 'b', 'aba', 'a')), (4, ('aab', 'a', 'b', 'aa'))]
Longest unique split : 4

也许可以通过某种方式对其进行优化,但是在这台计算机上花费了相当多的时间。


(非常感谢吉拉德·巴尔坎(Gilad Barkan)使我意识到了这一讨论。)

让我从纯理论的角度分享我对这个问题的想法(请注意,我也使用“因数”而不是“子词”)。

我认为这里考虑的一个或多个问题的正式定义如下:

给定单词w,找到单词u_1,u_2,...,u_k使得

  • u_i!= u_j对于每个i,j的1 <= i <j <= k
  • u_1 u_2 ... u_k = w

最大化变体(我们想要很多u_i):最大化k

最小化变体(我们想要短的u_i):最小化max {| u_i | :1 <= i <= k}

这些问题通过另外给定边界B而成为决策问题,根据我们在说“多因素”变量还是“短因素”变量,边界B是k的下界(我们至少希望B因子)或max {| u_i |的上限 :1 <= i <= k}(我们希望长度的因子至多为B)。 为了谈论NP硬度,我们需要谈论决策问题。

让我们将术语SF用于“短因子”变量,将MF用于“许多因子”变量。 特别是,这是非常关键的一点,问题的定义方式是使我们在 某个 字母上得到一个不受任何限制的单词。 问题的版本是我们先验地知道,我们只能获得输入单词,例如字母{a,b,c,d}是另一个问题! NP硬度不会自动从“无限制”变到“固定字母”变体(后者可能会更简单)。

SF和MF都是NP完全问题。 这已分别在[1,1b]和[2]中显示(正如Gilad已经指出的那样)。 如果我在讨论开始时正确地理解了(也许也是)非正式问题的定义,那么讨论的问题就是MF问题。 最初并没有提到单词仅限于某些固定的字母,后来又说我们可以假定仅使用小写字母。 如果这意味着我们只考虑固定字母{a,b,c,...,z}上的单词,那么就NP硬度而言,这实际上将发生很大变化。

仔细研究发现,SF和MF在复杂性方面存在一些差异:

  1. 论文[1,1b]表明,如果我们将字母固定为二进制字母,则SF仍为NP完整的(更准确地说:将单词w覆盖字母a和b以及边界B,我们可以将其分解为不同的长度因子)吗?最多B?)。
  2. 论文[1,1b]表明,如果我们将边界B固定为2,则SF仍然是NP完全的(更精确地说:得到一个单词w,我们能否将其分解为最多2个不同的长度因子?)。
  3. 论文[3]表明,如果字母和边界B都是固定的,则SF可以在多项式时间内求解。
  4. 论文[2]表明MF是NP完全的,但前提是字母 不受 先验的限制或固定! 特别是,如果我们仅考虑某个固定字母上的输入单词(在实际情况下通常如此),那么它 是否 回答了NP完全问题 并不能 回答问题。
  5. 论文[3]表明,如果输入边界B再次由某个常数作为上界,则MF可以在多项式时间内求解,即问题输入是一个单词和{1,2,...,K}的边界B ,其中K是某个固定常数。

关于这些结果的一些注释:Wrt(1)和(2),直观上很清楚,如果字母是二进制的,那么,为了使问题SF变得困难,边界B也无法固定。 相反,固定B = 2意味着字母大小必须变得相当大才能产生困难的实例。 结果,(3)显得微不足道(实际上,[3]说得更多:然后,我们不仅可以在运行时求解多项式,而且可以将| w | ^ 2倍一个仅取决于字母大小的因数)求解并绑定到B)。 (5)也不难:如果我们的单词比B长,那么我们可以通过简单地切成不同长度的因子来获得期望的分解。 如果不是,那么我们可以蛮力所有可能性,这仅在B中呈指数关系,在这种情况下,B被假定为常数。

因此,我们得到的图片如下:SF似乎更困难,因为即使对于固定的字母或固定的边界B,我们也有硬度。另​​一方面,如果边界固定(在在这方面,它比SF容易),而对应的问题是字母大小未定。 因此,即使事实证明固定字母的MF也是NP完整的,MF的复杂度也比SF略小。 但是,如果可以证明MF可以在固定时间内解决固定字母的问题,那么MF比SF容易得多……因为一种很难解决的情况有些人为(无界字母!) 。

我确实花了点力气试图解决带有有界字母的MF的情况,但此后我无法解决并停止研究。 我不相信其他研究人员已经尽力解决了这个问题(因此,这不是这些非常艰巨的公开问题之一,许多人已经尝试并失败了;我认为这是可行的)。 我的猜测是,对于固定字母来说这也是NP难的,但是减少的过程可能是如此复杂,以至于您会得到类似“对于35或更大的字母来说MF很难”之类的东西,这也不是太好了。

关于其他文献,我知道论文[4],该论文考虑了将单词w分解为都是回文的不同因子u_1,u_2,...,u_k的问题,这些因子也是NP完全的。

我快速浏览了Gilad指出的论文[5]。 不过,似乎要考虑其他设置。 在本文中,作者对给定单词中可以包含多少个不同的子序列或子单词的组合问题感兴趣,但是这些单词可以重叠。 例如,aaabaab包含20个不同的子词a,b,aa,ab,ba,bb,aaa,aab,aba,baa,baa,aaab,aaba,abaa,baab,aaaba,aabaa,abaab,aabaab,aaaaa,aaaaabab(也许误算了,但您知道了)。 它们中的一些仅发生一次,例如baa,其中一些仅发生一次,例如aa。 无论如何,问题不在于我们如何以某种方式拆分单词以获取许多不同的因素,因为这意味着每个单独的符号都恰好构成一个因素。

关于解决此类问题的实际解决方案(请记住,我是一名理论家,因此请耐心等待):

  • 据我所知,如果我们只考虑固定字母上的输入单词,那么就没有理论上的下界(例如NP硬度)会排除它在多项式时间内求解MF的可能性。 但是,有一个警告:如果您使用的是多重时间算法,则该算法应该以固定字母表中的符号数量成指数形式运行(或者在某些函数中以指数形式运行)! 否则,对于无界字母来说,它也是多项式时间算法。 因此,作为一名理论家,我将寻找仅在符号数量以及以某种方式有助于设计MF算法的情况下才能按时间指数计算的算法任务。 另一方面,在固定字母的情况下,很可能不存在这种算法,MF也是NP-hard。

  • 如果您对实际解决方案感兴趣,则近似解决方案可能会有所帮助。 因此,在最坏的情况下,保证分解仅为最佳值的一半就不会太糟糕。

  • 我想,没有给出可证明的近似比率但在实际环境中能很好工作的启发式方法也很有趣。

  • 将问题实例转换为SAT或ILP实例应该不太困难,然后您可以运行SAT或ILP-Solver甚至获得最佳解决方案。

  • 我的个人看法是,即使不知道MF的固定字母是否为NP困难的,也有足够的理论见解表明该问题足够困难,因此有理由寻找启发式解决方案等。在实际环境中运作良好。

参考书目:

[1] Anne Condon,JánManuch,Chris Thachuk:字符串分区的复杂性。 J.离散算法32:24-43(2015)

[1b] Anne Condon,Jan Manuch,Chris Thachuk:碰撞感知字符串分配问题的复杂性及其与基因合成的寡核苷酸设计的关系。 茧2008:265-275

[2] Henning Fernau,Florin Manea,Robert Mercas,Markus L. Schmid:带变量的模式匹配:快速算法和新的硬度结果。 STACS 2015:302-315

[3] Markus L. Schmid:计算无相等和重复的字符串分解。 理论。 计算 科学 618:42-51(2016)

[4] Hideo Bannai,Travis Gagie,Innsaga Shunsuke,JuhaKärkkäinen,Dominik Kempa,Marcin Piatkowski和Shiho Sugimoto:多样的回文因式分解都是NP完全的。 诠释 J.发现。 计算 科学 29(2):143-164(2018)

[5]亚伯拉罕·弗拉克斯曼(Abraham Flaxman),阿拉姆·韦特罗斯(Aram Wettroth Harrow),格雷戈里B. 电器。 J.梳 11(1)(2004)





algorithm