python - 分區中唯一子字符串的最大數量




string algorithm (5)

稍微修改了標題以使其更易於理解。

這是詳細的版本。 假設我們有一個字符串 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) 的多項式方法。


您可以使用帶有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)

我已經試過考慮這個問題,或者考慮是否要在給定的索引上進行分區。 因此,此函數是遞歸的,並在每個索引處創建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,aaaa,aaba,abaa,baab,aaaba,aabaa,abaab,aabaab,aaabaa,aaabaab(也許我誤算了,但您知道了)。 它們中的一些僅發生一次,例如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·索金(Gregory B. Sorkin):具有最大不同子序列和子字符串的字符串。 電器。 J.梳 11(1)(2004)





algorithm