Maksymalna liczba unikalnych podciągów z partycji

Zmodyfikowałem tytuł, aby był bardziej zrozumiały.

Oto szczegółowa wersja pytania:

Mamy ciąg s i chcemy go podzielić na podciągi . Każdy podciąg różni się od siebie. Jaka jest maksymalna liczba unikalnych podciągów, które możemy mieć z jednego cięcia. Innymi słowy, jaka jest maksymalna liczba unikalnych podciągów, które łączą się tworząc s.

Oto kilka przykładów:

Example 1
s = 'aababaa'
output = 4
Explain: we can split `s` 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

Uwaga : szawiera tylko małe litery. Nie powiedziano mi, jak długo si dlatego nie mogę odgadnąć optymalnej złożoności czasu. :(

Czy to trudny NP? Jeśli nie, jak mogę go rozwiązać skutecznie?

Słyszałem ten problem od jednego z moich przyjaciół i nie mogłem na nie odpowiedzieć. Próbuję użyć chciwości Trie +, aby rozwiązać ten problem. Metoda zawodzi w pierwszym przykładzie.

Oto rozwiązanie Trie, które wymyśliłem:

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

Na przykład 1, powyższy kod powróci 3, ponieważ stara się rozstali ssię a|ab|abaa.

Dodaj: Dzięki pomysłowi wszystkich wygląda na to, że ten problem jest bardzo zbliżony do problemu NP. W tej chwili staram się myśleć w tym kierunku. Załóżmy, że mamy funkcję Guess(n). Ta funkcja zwróci się, Truejeśli będziemy mogli znaleźć nunikalne podciągi z jednego podziału lub w Falseinny sposób. Jedną z obserwacji jest to, że jeśli Guess(n) == True, to Guess(i) == Truedla wszystkich i <= n. Ponieważ możemy scalić dwa sąsiednie podciągi razem. Ta obserwacja może prowadzić do rozwiązania binarnego. Nadal jednak wymaga to Guessbardzo wydajnego obliczenia tej funkcji. Niestety nadal nie mogłem znaleźć wielomianowego sposobu obliczania Guess(n).

Jest to znane jako problem podziału struny rozpoznający kolizję, a wykazano, że jest on NP-zupełny dzięki redukcji z 3-SAT w pracy Anne Condon, Ján Maňuch i Chris Thachuk - Złożoność problemu podziału struny świadomego kolizji i jej związek z projektem oligo do syntezy genów ( International Computing and Combinatorics Conference , 265-275, 2008).

(Wielkie podziękowania dla Gilada Barkana (גלעד ברקן) za poinformowanie mnie o tej dyskusji.)

Pozwólcie, że podzielę się przemyśleniami na temat tego problemu z czysto teoretycznego punktu widzenia (zauważ, że używam również „czynnik” zamiast „podsłówka”).

Uważam, że rozważana tutaj wystarczająco formalna definicja problemu (lub problemów) jest następująca:

Biorąc pod uwagę słowo w, znajdź słowa u_1, u_2, ..., u_k takie, że

• u_i! = u_j dla każdego i, j z 1 <= i <j <= k i
• u_1 u_2 ... u_k = w

Wariant maksymalizacji (chcemy wielu u_i): maksymalizuj k

Wariant minimalizacji (chcemy krótkiego u_i): minimalizuj max {| u_i | : 1 <= i <= k}

Problemy te stają się problemami decyzyjnymi poprzez dodatkowe ograniczenie B, które zgodnie z tym, czy mówimy o wariancie „wielu czynników”, czy wariancie „czynników krótkich”, jest dolną granicą k (chcemy co najmniej B Czynniki) lub górna granica maks. {| u_i | : 1 <= i <= k} (chcemy odpowiednio współczynników długości co najwyżej B). Aby mówić o twardości NP, musimy mówić o problemach decyzyjnych.

Użyjmy wyrażeń SF dla wariantu „krótkich czynników” i MF dla wariantu „wielu czynników”. W szczególności, i to jest naprawdę kluczowa kwestia, problemy są zdefiniowane w taki sposób, że uzyskujemy słowo nad jakimś alfabetem, które nie jest w żaden sposób ograniczone. Wersja problemowa, w której wiemy z góry, że otrzymujemy tylko słowa wejściowe, powiedzmy, że alfabet {a, b, c, d} to inny problem! Twardość NP nie przenosi się automatycznie z „nieograniczonego” na wariant „ustalonego alfabetu” (ten drugi może być prostszy).

Zarówno SF, jak i MF są problemami NP-zupełnymi. Pokazano to odpowiednio w [1, 1b] i [2] (jak już wskazał Gilad). Jeśli dobrze rozumiem (być może też) nieformalną definicję problemu tutaj na początku tej dyskusji, to problemem tej dyskusji jest właśnie problem MF. Początkowo nie wspomniano, że wyrazy są ograniczone do jakiegoś stałego alfabetu, później mówi się, że możemy założyć, że używane są tylko małe litery. Jeśli to oznacza, że ​​bierzemy pod uwagę tylko słowa nad ustalonym alfabetem {a, b, c, ..., z}, to zmieniłoby się bardzo dużo pod względem twardości NP.

Bliższe spojrzenie ujawnia pewne różnice w złożoności SF i MF:

1. artykuł [1, 1b] pokazuje, że SF pozostaje NP-kompletne, jeśli poprawimy alfabet na binarny (a dokładniej: otrzymując słowo w nad literami aib oraz związaną B, czy możemy je rozłożyć na różne czynniki długości przy najwięcej B?).
2. artykuł [1, 1b] pokazuje, że SF pozostaje NP-kompletne, jeśli naprawimy związany B = 2 (a ściślej: otrzymując słowo w, czy możemy go podzielić na różne czynniki długości co najwyżej 2?).
3. artykuł [3] pokazuje, że jeśli zarówno alfabet, jak i związany B są stałe, to SF można rozwiązać w czasie wielomianowym.
4. artykuł [2] pokazuje, że MF jest kompletny NP, ale tylko wtedy, gdy alfabet nie jest ograniczony ani ustalony a priori! W szczególności nie odpowiada na pytanie, czy problem jest NP-zupełny, jeśli weźmiemy pod uwagę tylko słowa wpisane w stosunku do jakiegoś ustalonego alfabetu (jak to zwykle ma miejsce w praktycznych ustawieniach).
5. artykuł [3] pokazuje, że MF można rozwiązać w czasie wielomianowym, jeśli granice wejściowe B są ponownie górne ograniczone pewną stałą, tzn. wejściowym problemem jest słowo i granica B z {1, 2, ..., K} , gdzie K jest pewną stałą stałą.

Kilka komentarzy na temat tych wyników: Wrt (1) i (2), intuicyjnie jest jasne, że jeśli alfabet jest binarny, to w celu utrudnienia SF problem związany z B również nie może zostać naprawiony. I odwrotnie, ustalenie B = 2 oznacza, że ​​rozmiar alfabetu musi być dość duży, aby stworzyć trudne przypadki. W konsekwencji (3) jest dość trywialny (w rzeczywistości [3] mówi nieco więcej: możemy go rozwiązać w czasie wykonywania nie tylko wielomianu, ale także | w | ^ 2 razy czynnik, który zależy tylko od wielkości alfabetu i związany B). (5) również nie jest trudne: jeśli nasze słowo jest długie w porównaniu do B, możemy uzyskać pożądaną faktoryzację, po prostu dzieląc na czynniki o różnych długościach. Jeśli nie, to możemy zastosować brutalną siłę wszystkich możliwości, która jest wykładnicza tylko w B, który w tym przypadku przyjmuje się za stały.

Obraz, który mamy, jest następujący: SF wydaje się trudniejszy, ponieważ mamy twardość nawet dla ustalonych alfabetów lub dla ustalonego wiązania B. Z drugiej strony problem MF staje się rozwiązywalny w czasie wielokrotnym, jeśli granica jest ustalona (w pod tym względem jest łatwiej niż SF), podczas gdy odpowiadające pytanie o rozmiar alfabetu jest otwarte. Zatem MF jest nieco mniej skomplikowane niż SF, nawet jeśli okaże się, że MF dla stałych alfabetów jest również NP-zupełny. Jeśli jednak można wykazać, że MF można rozwiązać dla stałych alfabetów w czasie wielozadaniowym, wówczas MF jest znacznie łatwiejsze niż SF ... ponieważ jeden przypadek, dla którego jest trudny, jest nieco sztuczny (nieograniczony alfabet!) .

Włożyłem trochę wysiłku w rozwiązanie problemu MF z ograniczonym alfabetem, ale nie byłem w stanie go rozwiązać i od tego czasu przestałem nad nim pracować. Nie wierzę, że inni badacze bardzo starali się go rozwiązać (więc nie jest to jeden z tych bardzo trudnych, otwartych problemów, wiele osób już próbowało i poniosło porażkę; uważam, że jest to jakoś wykonalne). Domyślam się, że jest to również trudne dla NP dla stałych alfabetów, ale może redukcja jest tak skomplikowana, że ​​można uzyskać coś takiego jak „MF jest trudny dla alfabetów o rozmiarze 35 lub większym” lub coś, co nie byłoby super miłe .

Jeśli chodzi o dalszą literaturę, znam pracę [4], która rozważa problem podziału słowa w na odrębne czynniki u_1, u_2, ..., u_k, które wszystkie są palindromami, co również jest NP-zupełne.

Rzuciłem okiem na papier [5], na co zwrócił uwagę Gilad. Wydaje się jednak, że rozważa inne ustawienie. W tym artykule autorzy są zainteresowani kombinatoryjnym pytaniem, ile różnych podsekwencji lub pod słów może zawierać jedno słowo, ale mogą się one nakładać. Na przykład aaabaab zawiera 20 różnych podtytułów a, b, aa, ab, ba, bb, aaa, aab, aba, baa, aaab, aaba, abaa, baab, aaaba, aabaa, abaab, aabaab, aaabaa, aaabaab (może ja przeliczyłem, ale masz pomysł). Niektóre z nich mają tylko jedno wystąpienie, jak baa, inne kilka, jak aa. W każdym razie nie chodzi o to, w jaki sposób możemy jakoś podzielić słowo, aby uzyskać wiele różnych czynników, ponieważ oznacza to, że każdy pojedynczy symbol przyczynia się do dokładnie jednego czynnika.

Jeśli chodzi o praktyczne rozwiązania tego rodzaju problemów (pamiętaj, że jestem teoretykiem, więc weź to z odrobiną soli):

• Według mojej wiedzy, nie ma teoretycznych dolnych granic (takich jak twardość NP), które wykluczałyby rozwiązanie MF w czasie wielomianowym, jeśli weźmiemy pod uwagę tylko słowa wpisane na ustalonym alfabecie. Jest jednak jedno zastrzeżenie: jeśli otrzymasz algorytm wielogodzinny, powinien on działać wykładniczo w liczbie symboli ze stałego alfabetu (lub wykładniczo w niektórych funkcjach tego)! W przeciwnym razie byłby to również algorytm wielomianowy w przypadku nieograniczonych alfabetów. Będąc teoretykiem, szukałbym zadań algorytmicznych, które można by obliczyć w czasie wykładniczym, tylko jeśli liczba symboli i które w jakiś sposób pomagają w opracowaniu algorytmu dla MF. Z drugiej strony jest prawdopodobne, że taki algorytm nie istnieje, a MF jest również NP-twardy w przypadku stałego alfabetu.

• Jeśli interesują Cię praktyczne rozwiązania, pomocne może być przybliżenie rozwiązania. Tak więc uzyskanie faktoryzacji, które są gwarantowane tylko w połowie tak duże, jak optymalne w najgorszym przypadku, nie byłoby takie złe.

• Interesujące wydaje się również heurystyka, która nie daje możliwego do udowodnienia współczynnika przybliżenia, ale działa dobrze w praktycznym otoczeniu.

• Przekształcanie instancji problemowych w instancje SAT lub ILP nie powinno być zbyt trudne, a następnie możesz uruchomić SAT lub ILP-Solver, aby uzyskać nawet optymalne rozwiązania.

• Moim osobistym zdaniem jest to, że chociaż nie wiadomo, czy przypadek MF z ustalonym alfabetem jest trudny do NP, istnieje wystarczająco dużo teoretycznych spostrzeżeń, które sugerują, że problem jest na tyle trudny, że uzasadnione jest poszukiwanie rozwiązań heurystycznych itp., Które działają dobrze w praktycznych warunkach.

Bibliografia:

[1] Anne Condon, Ján Manuch, Chris Thachuk: Złożoność partycjonowania łańcucha. J. Discrete Al Algorytmy 32: 24-43 (2015)

[1b] Anne Condon, Ján Manuch, Chris Thachuk: Złożoność świadomego kolizji problemu rozdziału struny i jego związek z projektem Oligo do syntezy genów. COCOON 2008: 265–275

[2] Henning Fernau, Florin Manea, Robert Mercas, Markus L. Schmid: Dopasowywanie wzorców ze zmiennymi: szybkie algorytmy i nowe wyniki twardości. STACS 2015: 302–315

[3] Markus L. Schmid: Obliczanie wolnych od równości i powtarzalnych faktoryzacji ciągów. Teoria Comput. Sci. 618: 42–51 (2016)

[4] Hideo Bannai, Travis Gagie, Shunsuke Inenaga, Juha Kärkkäinen, Dominik Kempa, Marcin Piatkowski, Shiho Sugimoto: Zróżnicowane faktowanie palindromiczne jest zakończone NP. Int. J. Znaleziono. Comput. Sci. 29 (2): 143–164 (2018)

[5] Abraham Flaxman, Aram Wettroth Harrow, Gregory B. Sorkin: Struny z maksymalnie wieloma odrębnymi podsekwencjami i podciągami. Electr. J. Comb. 11 (1) (2004)

Oto rozwiązanie, ale wybuchnie naprawdę szybko i nie jest blisko wydajnego rozwiązania. Najpierw rozkłada ciąg na listę unikatowych podciągów bez obawy o kolejność, a następnie próbuje użyć itertools.permutation, aby ponownie złożyć te podciągi z powrotem w oryginalny ciąg, testując KAŻDĄ permutację, aby sprawdzić, czy pasuje do oryginalnego ciągu.

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]}")

Do pierwszego testu otrzymujemy to:

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

Być może można to jakoś zoptymalizować, ale na tym komputerze zajmuje to kilka sekund.

Podjąłem ten problem i zastanowiłem się nad nim w kategoriach lub czy utworzyć partycję pod danym indeksem. Ta funkcja jest rekurencyjna i tworzy 2 gałęzie przy każdym indeksie 1. Nie dziel na indeks i. 2. Podziel na indeks i.

Na podstawie partycji wypełniam zestaw, a następnie zwracam rozmiar zestawu

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

Możesz użyć funkcji rekurencyjnej z zestawem jako drugim parametrem, aby śledzić unikalne ciągi w bieżącej ścieżce do tej pory. Dla każdej rekurencji, iteruj przez wszystkie indeksy plus 1, przy których można podzielić ciąg dla możliwego ciągu kandydującego, a jeśli ciąg kandydujący nie znajduje się jeszcze w zestawie, wykonaj wywołanie rekurencyjne z pozostałym ciągiem i kandydatem dodanym do zestawu aby uzyskać maksymalną liczbę unikalnych podciągów z pozostałego ciągu, dodaj 1 do niego i zwróć maksimum maksimów z iteracji. Zwraca 0, jeśli podany ciąg jest pusty lub wszystkie ciągi kandydujące są już w zestawie:

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

Demo: https://repl.it/@blhsing/PriceyScalySphere

W Pythonie 3.8 powyższą logikę można również zapisać za pomocą wywołania maxfunkcji z wyrażeniem generatora, które filtruje kandydatów, którzy zostali „widziani” za pomocą wyrażenia przypisania:

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)

Oto odpowiedź oparta na teorii grafów.

Modelowanie
Ten problem można modelować jako maksymalny niezależny problem z zestawem na wykresie wielkości O(n²)w następujący sposób:
Niech w = c_1, ..., c_nbędzie łańcuchem wejściowym.
Pozwolić G = (V,E)być nieukierunkowane wykres, zbudowany w następujący sposób:
V = { (a, b) such that a,b in [1, n], a <= b }. Widzimy, że rozmiar Vto n(n-1)/2, gdzie każdy wierzchołek reprezentuje podłańcuch w.
Następnie dla każdej pary wierzchołków (a1, b1)i (a2, b2)budujemy krawędzi ((a1, b1), (a2, b2))IFF
(I) [a1, b1]przecina [a2, b2]lub
(ii) c_a1...c_b1 = c_a2...c_b2.
Mówiąc inaczej, budujemy krawędź między dwoma wierzchołkami, jeśli (i) reprezentowane przez nie podciągi nachodzą na siebie wlub (ii) dwa podciągi są równe.

Możemy wtedy zobaczyć, dlaczego maksymalna niezależny zestaw z Gzapewnia odpowiedź na nasz problem.

Złożoność
W ogólnym przypadku problem maksymalnego zestawu niezależnego (MIS) jest trudny do NP, ze złożonością czasową O(1.1996^n)w przestrzeni wielomianowej [Xiao, NamaGoshi (2017)] .
Na początku myślałem, że otrzymany wykres będzie grafem akordowym (bez indukowanego cyklu długości> 3), co byłoby bardzo miłe, ponieważ problem MIS można rozwiązać w czasie liniowym na tej klasie grafów.
Ale szybko zdałem sobie sprawę, że tak nie jest, dość łatwo jest znaleźć przykłady, w których indukowane są cykle o długości 5 i więcej.
W rzeczywistości powstały wykres nie wykazuje żadnej „ładnej” właściwości, której zwykle szukamy i która pozwala zredukować złożoność problemu MIS do wielomianu.
Jest to tylko górna granica złożoności problemu, ponieważ wielomianowe skrócenie czasu idzie tylko w jednym kierunku (możemy zredukować ten problem do problemu MIS, ale nie na odwrót, przynajmniej nie trywialnie). Ostatecznie rozwiązujemy ten problem w O(1.1996^(n(n-1)/2))najgorszym przypadku.
Tak więc, niestety, nie mogłem udowodnić, że jest w P lub że jest NP-kompletny lub NP-twardy. Pewne jest to, że problem dotyczy NP, ale chyba nikogo to nie zaskoczy.

Implementacja
Zaletą zmniejszenia tego problemu do problemu MIS jest to, że MIS jest klasycznym problemem, dla którego można znaleźć kilka implementacji, a problem MIS można łatwo napisać jako ILP.
Oto sformułowanie ILP problemu MIS:

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

Moim zdaniem powinien to być najskuteczniejszy sposób rozwiązania tego problemu (wykorzystanie tego modelowania jako problemu MIS), ponieważ solver ILP jest niezwykle wydajny, szczególnie w przypadku dużych instancji.

Jest to implementacja, którą zrobiłem używając Python3 i solvera GLPK . Aby to przetestować, potrzebujesz solwera LP zgodnego z formatem pliku Cplex.

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')

Następnie możesz je rozwiązać za pomocą glpsolpolecenia:
glpsol --lp LP_file_1
Rozwiązanie aababaajest rozwiązywane szybko (0,02 s na moim laptopie), ale zgodnie z oczekiwaniami, sprawy stają się (znacznie) trudniejsze wraz ze wzrostem rozmiaru łańcucha ....
Ten program podaje tylko wartość liczbową (a nie optymalna partycja), jednak optymalną partycję i odpowiadające jej podciągi można znaleźć w podobnej implementacji, używając interfejsu solver LP / python, takiego jak pyomo

Czas i pamięć
aababaa : 0,02 sekundy, 0,4 MB, wartość: 4
kzshidfiouzh: 1,4 sekundy, 3,8 MB, wartość: 10
aababababbababab: 60,2 sekundy, 31,5 MB, wartość: 8
kzshidfiouzhsdjfyu: 207,5 sekundy, 55,7 MB, wartość: 14
Należy pamiętać, że solver LP oferuje również bieżące dolne i górne granice rozwiązania, więc w ostatnim przykładzie mogę uzyskać rzeczywiste rozwiązanie jako dolną granicę po minucie.

Moja inna odpowiedź była ściśle powiązana, ale nie odpowiadała dokładnie temu problemowi, pozostawiając niejednoznaczne, czy znalezienie największego wolnego od równości faktoryzacji ciągów może mieć inną klasę złożoności niż to, czy istnieje jakikolwiek wolny od równości faktoryzacja ze związaną długością czynnika (ta ostatnia skierowane przez cytowany artykuł).

W artykule Dopasowywanie wzorców ze zmiennymi: szybkie algorytmy i nowe wyniki twardości (Henning Fernau, Florin Manea, Robert Mercaş i Markus L. Schmid, w Proc. 32. sympozjum na temat teoretycznych aspektów informatyki, STACS 2015, tom 30 Leibniz International Proceedings in Informatics (LIPIcs) , strony 302–315, 2015), autorzy pokazują, że NP jest kompletne w podejmowaniu decyzji, dla danej liczby ki słowa w, czy wmożna je rozdzielić na kodrębne czynniki.

Jeśli weźmiemy pod uwagę templatetypedef za komentarz , co oznacza, że może być wielomianem rozwiązanie czas nieograniczony, największej równości wolne Faktoryzacji to z pewnością możemy użyć takiego algorytmu, aby odpowiedzieć, czy możemy podzielić ciąg znaków w króżnych czynników (podciągi), po prostu obserwując, czy kjest mniej niż maksimum, które już znamy.

Schmid (2016) pisze jednak, że „nadal jest otwartym problemem, czy MaxEFF-s pozostaje NP-kompletny, jeśli alfabet jest poprawiony”. (Obliczanie wolnych od równości i powtarzalnych faktoryzacji łańcuchów, Theoretical Computer Science Tom 618 , 7 marca 2016, strony 42-51)

Maksymalny rozmiar faktoryzacji wolnej od równości (MaxEFF-s) jest jednak nadal parametryzowany i definiowany jako:

Instancja: Słowo wi numer m, 1 ≤ m ≤ |w|.

Pytanie: Czy istnieje faktoryzacja bez równości p wz s(p) ≥ m? ( s(p)jest wielkością faktoryzacji).