Jak trudne jest tasowanie sznurka?

117

Losowanie dwóch ciągów znaków polega na przeplataniu znaków w nowy ciąg znaków, utrzymując porządek znaków każdego łańcucha. Na przykład, MISSISSIPPIjest losowanie MISIPPi SSISI. Nazwijmy kwadrat ciągów, jeśli jest to tasowanie dwóch identycznych ciągów. Na przykład ABCABDCDjest kwadratowy, ponieważ jest to przetasowanie ABCDi ABCD, ale ciąg ABCDDCBAnie jest kwadratowy.

Czy istnieje szybki algorytm określający, czy łańcuch jest kwadratowy, czy trudny do NP? Oczywiste podejście do programowania dynamicznego wydaje się nie działać.

Nawet następujące przypadki szczególne wydają się trudne: (1) ciągi, w których każdy znak występuje najwyżej cztery sześć razy, oraz (2) ciągi zawierające tylko dwa różne znaki. Jak zauważa Per Austrin poniżej, specjalny przypadek, w którym każda postać występuje najwyżej cztery razy, można zmniejszyć do 2SAT.


Aktualizacja: ten problem ma inną formułę, która może ułatwić sprawdzenie twardości.

Rozważmy wykres G, którego wierzchołki są liczbami całkowitymi od 1 do n; zidentyfikuj każdą krawędź za pomocą rzeczywistego odstępu między jej punktami końcowymi. Mówimy, że dwie krawędzie G są zagnieżdżone, jeśli jeden przedział prawidłowo zawiera drugi. Na przykład krawędzie (1,5) i (2,3) są zagnieżdżone, ale (1,3) i (5,6) nie są, a (1,5) i (2,8) nie. Dopasowanie w G nie jest zagnieżdżone, jeśli nie ma zagnieżdżonej pary krawędzi. Czy istnieje szybki algorytm określający, czy G ma nie zagnieżdżone idealne dopasowanie, czy też jest to trudny NP?

  • Odtasowywanie łańcucha jest równoznaczne ze znalezieniem idealnego dopasowania bez zagnieżdżenia w rozłącznym związku kliki (z krawędziami między równymi znakami). W szczególności rozpakowywanie łańcucha binarnego jest równoznaczne ze znalezieniem idealnego dopasowania nie zagnieżdżonego w rozłącznym połączeniu dwóch klik. Ale nawet nie wiem, czy ten problem jest trudny dla grafów ogólnych, czy łatwy dla jakichkolwiek interesujących klas grafów.

  • Nie jest to łatwe algorytm wielomianowy czas, aby znaleźć idealny innych niż przekraczania skojarzeń.


Aktualizacja (24 czerwca 2013 r.): Problem został rozwiązany! Istnieją teraz dwa niezależne dowody, że identyfikacja ciągów kwadratowych jest NP-kompletna.

Istnieje również prostszy dowód na to, że znalezienie niedopasowanych idealnych dopasowań jest trudne dla NP, ze względu na Shuai Cheng Li i Ming Li w 2009 roku. Patrz „ O dwóch otwartych problemach wzorów 2-interwałowych ”, Theoretical Computer Science 410 (24–25 ): 2410–2423, 2009.

Jeffε
źródło
2
Czy sekwencja nie jest tylko A000984, „liczbą możliwych wartości 2-bitowej liczby binarnej, dla której połowa bitów jest włączona, a połowa nie”?
Travis Brown
5
@ Travis, chyba że się mylę: dla n = 4 10000111 jest 2-bitową liczbą binarną, dla której połowa bitów jest włączona, a połowa wyłączona, ale która nie jest kwadratem, jak zdefiniowano. Zgodnie z tą logiką, ponieważ kwadraty są ścisłym podzbiorem zbioru, który generuje A000984, wartości kwadratów w alfabecie binarnym powinny być niższe przy równych indeksach w sekwencji - nie?
Daniel Apon
1
Obserwacja: Używając formalizmu grafowego, niech 2n będzie liczbą wierzchołków w G. Niech G 'będzie wykresem uzyskanym z wykresu liniowego G przez dodanie krawędzi między wierzchołkami odpowiadającymi zagnieżdżonym krawędziom G. Problem polega na pytaniu, czy G ′ ma niezależny zestaw wielkości n. Istnieją różne klasy wykresów, w których można obliczyć maksymalny niezależny zbiór czasu wielomianowego. Jeśli pójdziemy tą drogą, pytanie brzmi: jakie ładne właściwości ma G ′? (więcej)
Tsuyoshi Ito,
2
@Radu: Nie wydaje mi się, aby część kwadratów na kwadraty (ponad alfabet binarny) była zbieżna do 1/3. Zrobiłem kilka symulacji Monte Carlo, które wskazują na powolną konwergencję do 1/2. Stąd w limicie zasadniczo wszystkie ciągi binarne o parzystych liczbach 0 i 1 są kwadratami. Jest to dla mnie zaskakujące i może być wykorzystywane w algorytmie. W przypadku większych alfabetów ułamek kwadratów wydaje się szybko zbliżać do zera.
Martin Berger,
8
Ponieważ pytanie to jest wspomniane w dzisiejszym poście na blogu, zobaczmy, czy możemy ponownie zainteresować się rozwiązaniem tego problemu. Minęło rok odkąd to pytanie zostało wysunięte i od tego czasu zdobyliśmy wielu nowych użytkowników. Za to pytanie wystawiłem nagrodę w wysokości 100 powtórzeń.
Alex ten Brink

Odpowiedzi:

66

Michael Soltys i ja udało nam się udowodnić, że problem określania, czy ciąg może być zapisany jako tasowanie kwadratowe, jest NP kompletny. Dotyczy to nawet skończonego alfabetu zawierającego tylko różnych symboli, chociaż nasz dowód jest napisany dla alfabetu zawierającego 9 symboli. To pytanie jest nadal otwarte dla mniejszych alfabetów, powiedzmy z tylko 2 symbolami. Nie spojrzeliśmy na problem pod ograniczeniem, że każdy symbol pojawia się tylko 6 razy (lub, bardziej ogólnie, stała liczba razy); więc to pytanie jest nadal otwarte.792)6

Dowód wykorzystuje redukcję z części. Publikacja tutaj jest zbyt długa, ale przedruk „Unshuffling a string is NP -hard” jest dostępny na naszych stronach internetowych:3)NP

http://www.math.ucsd.edu/~sbuss/ResearchWeb/Shuffle/

i

http://www.cas.mcmaster.ca/~soltys/#Papers .

Artykuł został opublikowany w czasopiśmie Journal of Computer System Sciences:

http://www.sciencedirect.com/science/article/pii/S002200001300189X

Sam Buss
źródło
11
Niesamowite!! (I ku mojej ogromnej uldze, poważnie nietrywialne.)
Jeffε
15
Dzięki. StackExchange było naszym źródłem tego pytania. To świetny zasób!
Sam Buss
9
@SamBuss mała prośba: cytując pytanie Jeffa, w tekście wspominasz tylko o rozwiązaniu Per Austrina. Jeśli spojrzysz na odpowiedzi, istnieje również sposób na wygenerowanie formalnego cytowania odpowiedzi (kliknij przycisk udostępniania i kliknij link „cytuj”). W ten sposób możesz również wygenerować odpowiedni cytat dla odpowiedzi Pera. Wspominam o tym tylko po to, aby osoby, które dokonały formalnego wkładu na stronie, mogły uzyskać formalne uznanie. Dzięki ! i gratulacje za rozwiązanie tego problemu
Suresh Venkat
2
@SureshVenkat. Dzięki za wskazówkę: jest to przydatne. Dodałem to do internetowej wersji artykułu.
Sam Buss
Problem rozpoznawania kwadratowy shuffle, teraz okazuje się trudne nawet na binarnego alfabetu: sciencedirect.com/science/article/pii/S0304397519300258
a3nm
58

W specjalnym przypadku, o którym wspominasz, gdy każda postać pojawia się maksymalnie cztery razy, następuje prosta redukcja do 2-SAT (chyba że czegoś mi brakuje ...) w następujący sposób:

Najważniejsze jest to, że dla każdej postaci istnieją (co najwyżej) dwa prawidłowe sposoby dopasowywania wystąpień postaci (trzecią możliwością będzie zagnieżdżenie). Użyj zmiennej boolowskiej, aby wskazać, które z dwóch dopasowań jest wybrane. Teraz przypisanie do tych zmiennych daje prawidłowe przetasowanie ciągu iff dla każdej pary zagnieżdżonych krawędzi, nie wybrano obu. Ten warunek można dokładnie opisać przez rozłączenie zmiennych (ewentualnie zanegowanych) odpowiadających dwóm zaangażowanym znakom.

Per Austrin
źródło
Miły. Ten sam pomysł uogólnia się na ciągi znaków, w których każdy znak występuje najwyżej sześć razy, ale wynikiem jest instancja 5-SAT. :-(
Jeffε
2
Ta odpowiedź jest faworytem do wygrania nagrody.
Jeffε
więc wydaje się to dowodzić, że problemem jest NPC i dlaczego potrzebujemy długich dowodów konferencji i dzienników?
T ....
@Turbo Bardzo spóźnione, ale to nie dowodzi, że problemem jest NPC, ponieważ 2-SAT nie jest NPC; jest w P.
Steven Stadnicki
Czy redukcja do 2-SAT działa, jeśli wielkość alfabetu jest nieograniczona?
Mohammad Al-Turkistany
11

Oto algorytm, który może mieć pewne szanse na poprawność, choć udowodnienie tego wydaje się trudne i nie postawiłbym na to domu ...

Powiedzmy, że jest czyszczone, jeśli dla każdej krawędzi e istnieje (ewentualnie zagnieżdżone) idealne dopasowanie G, które używa e i nie używa żadnej krawędzi zawartej w e lub zawierającej e .solmisolmimi

Łatwo jest sprawdzić, czy jest wyczyszczony, a jeśli nie znajduje naruszających krawędzi. Oczywiście żadna z tych naruszających krawędzi nie może być użyta w niedopasowanym idealnym dopasowaniu G , więc można je bezpiecznie usunąć z rozważań. Powtarzając ten proces, uzyskać (unikalne) przedmuchanej podgrafu z G , który ma nie zagnieżdżonej doskonałe dopasowanie IFF G ma.solsolsolsol

Teraz następuje skok wiary, który może, ale nie musi być poprawny: mamy nadzieję, że na oczyszczonym wykresie, jeśli nadal będą wierzchołki stopnia , możemy dokonać chciwego wyboru i dopasować pierwszy taki wierzchołek do jego pierwszego sąsiada (lub równoważnie usuń krawędzie z wszystkimi pozostałymi sąsiadami).>1

Po chciwym wyborze ponownie oczyszczamy wykres i tak dalej, a proces kończy się, gdy (mam nadzieję), że wykres nie pasuje do zagnieżdżenia.

Na początku myślałem, że z grubsza przypominałoby to chciwość algorytmu i nie działa, ale zaskakująco trudno było mi znaleźć kontrprzykład.

Per Austrin
źródło
Jestem sceptycznie nastawiony do drugiej chciwej fazy, ale oczyszczenie wykresu wydaje się przydatne. Czy w oryginalnym kontekście łańcuchowym, gdzie wykres jest rozłącznym połączeniem klik, czy możesz coś powiedzieć o strukturze oczyszczonego wykresu? Czy nadal jest to rozłączny związek klik? (Innymi słowy, czy można podzielić wystąpienia każdego znaku w ciągu wejściowym, aby znaki w różnych częściach nie mogły być dopasowane?)
Jeffε
2
W przypadku drugiego pytania rozważ ciąg „aaaa”. Oczyszczanie usuwa krawędzie 1-4 i 2-3, dając 4-cyklowy. Dwie odmiany drugiego chciwego kroku, które również byłyby wystarczające i których nie mogłem znaleźć żadnych kontrprzykładów, to: 1) Oczyszczony wykres ma nie zagnieżdżone idealne dopasowanie i ma idealne dopasowanie (wydaje się to nieporównywalne z chciwym krokiem) . 2) Na czystym wykresie z niedopasowanym doskonałym dopasowaniem każda krawędź jest używana w pewnym niedopasującym idealnym dopasowaniu (jest to mocniejsze niż zarówno chciwy krok, jak i pierwszy element, więc powinno być łatwiej obalić).
Per Austrin
11

Rozwiązanie zaproponowane przez Sama Bussa w listopadzie 2012 r. (Pokazujące, że przemieszanie kwadratu w NP-twardym przez redukcję z 3 partycji) jest teraz opublikowanym artykułem w Journal of Computer System Sciences:

http://www.sciencedirect.com/science/article/pii/S002200001300189X

Michael Soltys
źródło
2
To naprawdę powinno być edycją wcześniejszej odpowiedzi Sama Bussa, a nie oddzielną odpowiedzią. Możesz kliknąć „edytuj”, aby zasugerować zmianę odpowiedzi innej osoby, a Twoja zmiana zostanie sprawdzona przez innych użytkowników witryny.
DW
11

Romeo Rizzi i Stéphane Vialette udowadniają, że rozpoznawanie ciągów kwadratowych jest NP-zupełne w artykule z 2013 r. „ Rozpoznawanie słów, które są kwadratami dla produktu losowego ”, dzięki redukcji od najdłuższego problemu podsekwencji binarnej. Twierdzą, że złożoność rozpakowywania ciągów binarnych jest nadal otwarta.

Jeszcze prostszy dowód na to, że znalezienie nienasyconego idealnego dopasowania jest NP-zupełne, podali Shuai Cheng Li i Ming Li w artykule z 2009 r. „ O dwóch otwartych problemach wzorów 2-interwałowych ”. Używają jednak terminologii odziedziczonej po bioinformatyce. Zamiast „idealnego dopasowania nie zagnieżdżonego” nazywają to „ problemem DIS-2-IP- {<,} ”. Równoważność między tymi dwoma problemami opisali Blin, Fertin i Vialette :

Problem 2-IP-DIS- {<,} ma natychmiastowe sformułowanie w kategoriach ograniczonych dopasowań na ogólnych wykresach: Biorąc pod uwagę wykres sol wraz z liniowym uporządkowaniem π wierzchołków sol , 2-IP-DIS- {<,} problemem jest to równoważne z ustaleniem maksymalnego dopasowania liczność M. w sol z własności, że dla dowolnych dwóch różnych krawędzi {u,v} i {u,v} o M. animjan{π(u),π(v)}<mjan{π(u),π(v)} orazmax{π(u),π(v)<max{π(u),π(v)} normjan{π(u),π(v)}<mjan{π(u),π(v)} orazmzax{π(u),π(v)}<mzax{π(u),π(v)} występują.

Aktualizacja (25 lutego 2019 r.): Bulteau i Vialette pokazały, że problem decyzyjny polegający na odtajnieniu łańcucha binarnego jest w ich dokumencie kompletny, rozpoznawanie binarnych kwadratów losowych jest trudne .

Mohammad Al-Turkistany
źródło
Nie widzę połączenia i nie widzę, gdzie autorzy twierdzą, że rozpakowywanie łańcucha jest równoznaczne z ich problemem.
Suresh Venkat
2
Nie mówią, że jest to równoważne z przetasowaniem; jest to bardziej ogólny problem.
Jeffε
@SureshVenkat Zredagowałem swoją odpowiedź, mam nadzieję, że jest jaśniejsza. Zasadniczo w przypisie mówią, że dowolne dwie krawędzie w dopasowaniu ( ) nie są zagnieżdżone. M
Mohammad Al-Turkistany
W rzeczywistej opublikowanej wersji równoważność jest podana na stronie 320. books.google.com/…
Mohammad Al-Turkistany
Edytowane, aby un pochować lede .
Jeffε
9

czy to pomaga?

http://users.soe.ucsc.edu/~manfred/pubs/J1.pdf

Aaron Sterling
źródło
7
Niezłe referencje. Trudno zobaczyć, jak wyniki mogłyby się odnosić do mojego problemu, ale może techniki pomogłyby. Łatwo jest stwierdzić, czy dany ciąg X jest przetasowaniem dwóch kopii innego podanego ciągu Y. Załączony papier dowodzi, że trudno jest zdecydować, czy dany ciąg X jest przetasowaniem dowolnej liczby kopii innego podanego ciągu Y. Chcę wiedzieć, czy dany ciąg X jest przetasowaniem dwóch kopii NIEKTÓRYCH ciągów NIEZNANY Y.
Jeffε
5

NIGDY NIE UMYSŁ, TO ODPOWIEDŹ JEST ŹLE. Nie udaje się na wejściu „AABAAB”: łapczywe dopasowanie dwóch pierwszych A ze sobą uniemożliwia dopasowanie pozostałych symboli. Zostawiam to, a nie usuwam, aby pomóc innym uniknąć tego samego błędu.

Wydaje mi się, że zawsze można bezpiecznie łapać każdą kolejną postać domniemanego kwadratu łapczywie do innej równej postaci, która jest na jak najwcześniejszej pozycji. To znaczy, myślę, że następujący algorytm czasu liniowego powinien działać:

Zapętlaj każdą pozycję i w ciągu wejściowym, i = 0, 1, 2, ... n. Dla każdej pozycji i sprawdź, czy ta pozycja została już dopasowana do jakiejś wcześniejszej pozycji w ciągu. Jeśli nie, dopasuj go do znaku równości, który pojawia się po ostatniej już dopasowanej pozycji i poza tym jest możliwie najwcześniej w ciągu. Jeśli nie znaleziono dopasowania dla jakiegoś znaku, zadeklaruj, że dane wejściowe nie są kwadratem; w przeciwnym razie jest to zestaw znaków w pierwszej parze każdego dopasowania.

Oto w Pythonie:

def sqrt (S):
    mecze = []
    i, j = 0, 0
    podczas gdy i <len (S):
        if j <len (mecze) i mecze [j] [1] == i:
            i + = 1
            j + = 1
            dalej
        jeśli pasuje:
            k = dopasowania [-1] [1] + 1
        jeszcze:
            k = 1
        podczas gdy k <len (S) i S [k]! = S [i]:
            k + = 1
        jeśli k> = len (S):
            podniesienie wyjątku („To nie jest kwadrat”)
        match.append ((i, k))
        i + = 1
    return „” .join (S [a] dla a, b w meczach)

print sqrt („ABCABDCD”)

Tutaj i jest zmienną głównej pętli (pozycja, którą próbujemy dopasować), j jest wskaźnikiem w tablicy dopasowanych par, który przyspiesza sprawdzenie, czy pozycja i jest już dopasowana, a k jest indeksem używanym do wyszukiwania znak, który pasuje do tego w pozycji i. Jest to czas liniowy, ponieważ i, j i k rosną monotonicznie przez łańcuch, a każda iteracja wewnętrznej pętli zwiększa jeden z nich.

David Eppstein
źródło
4
Byłem tam Skończone. :-)
Jeffε
5

Aktualizacja: Nie ma sensu mówić o trudnościach ze znalezieniem idealnego dopasowania, które nie zagnieżdża się i nie krzyżuje, gdy etykiety mają wartość od 1 do n, ponieważ jest tylko jedna taka. (Tak, sam się kopię.) Byłoby jednak sensowne, biorąc pod uwagę większy zakres na etykietach ... więc wciąż widzę nadzieję, ale może to być zupełnie bezcelowe. Z pewnością będę musiał to kontynuować.


Mogę wymyślić, dlaczego może być trudno znaleźć dopasowanie, które nie zagnieżdża się i nie krzyżuje. Pozwól mi nazwać takie dopasowanie rozłącznym dopasowaniem . Nie jestem pewien, w jakim stopniu to pomaga, ale i tak przedstawię uzasadnienie. (Powinienem zauważyć, że mój argument w obecnym brzmieniu nie jest kompletny, a szczegóły, które pomijam, są prawdopodobnie kluczowe. Wyobrażam sobie jednak, że może to być początek.)

Zacznę od nieco innego problemu. Biorąc pod uwagę wykres którego krawędzie są pokolorowane za pomocą ksolk kolorów, a wierzchołki są oznaczone od do n , czy istnieje rozłączne dopasowanie, które zawiera dokładnie jedną krawędź każdego koloru? Ten problem wydaje się być trudny do rozwiązania (argument jest zarówno pełny, jak i prosty - chyba że czegoś mi brakuje). Redukcja wyrzuca wykres, który jest rozłącznym związkiem klik.1n

Redukcja wynika z Disjoint Factors , problemu NP-zupełnego wprowadzonego w [1]. Przykładem czynników rozłącznych jest ciąg znaków nad alfabetem wielkości , a pytanie brzmi, czy istnieje k czynników rozłącznych, gdzie czynnik jest podłańcuchem, który zaczyna się i kończy tą samą literą; a dwa czynniki są rozłączne, jeśli nie nakładają się na ciąg (zwróć uwagę, że w szczególności „zagnieżdżanie” również jest niedozwolone).kk

Pozwól mi Oznaczmy przez , elementy k -sized alfabetu związanego z rozłącznych Factors instancji.za1,,zakk

Biorąc pod uwagę wystąpienie czynników rozłącznych, to znaczy, powiedzmy, ciąg długości , utwórz wykres, który ma n wierzchołków z etykietami wierzchołków od 1 do n . Dodanie od wierzchołków krawędzi w kształcie U i V , jeżeli odpowiednie pozycje mają taką samą literę (powiedzmy ı ), a także kolor krawędzi ( unn1nuvzaja z kolorem i .(u,v)ja

Dowód zmniejszenia wynika zasadniczo z definicji. Biorąc pod uwagę k rozłącznych czynników, wyraźnie mamy rozłączne kolorowe dopasowanie, wystarczy wybrać krawędzie podane przez rozłączne czynniki i łatwo zauważyć, że wynikowe dopasowanie jest zarówno kolorowe, jak i rozłączne. I odwrotnie, jeśli istnieje k- rozłączne kolorowe dopasowanie, to mamy k czynników rozłącznych, po jednym dla każdej litery, ponieważ dopasowanie jest kolorowe (a zatem wybiera jeden czynnik na literę) i jest rozłączne (więc odpowiednie czynniki nie będą się nakładać ).kk

Aby pozbyć się kolorów i sprawić, by dopasowanie było idealne, aczkolwiek w możliwie większym zakresie , wprowadź następujące modyfikacje do tak utworzonego wykresu:

UzazaUzaZA(ZA-2))Uza

Z grubsza mówiąc, jeśli wykres ma doprowadzić do idealnego dopasowania, nowo wprowadzone wierzchołki muszą zostać dopasowane do wierzchołków Uza

[1] O problemach bez jąder wielomianowych , Hans L. Bodlaender, Rodney G. Downey, Michael R. Fellows i Danny Hermelin, J. Comput. Syst. Sci.

Neeldhara
źródło
3
Jestem zmieszany. Czy (1,2), (3,4), (5,6), ..., (n-1, n) JEDYNIE idealne dopasowanie rozłączne?
Jeffε
Po przejściu do scenariusza „idealnego dopasowania” modyfikuję konstrukcję i dodam wiele nowych wierzchołków (zwróć uwagę, że dodam | U_a | -2 nowe wierzchołki dla każdego znaku alfabetu). Zatem n odpowiednio wysadzi - mniej więcej do 2n-2k, dla alfabetu wielkości k. Mam nadzieję, że wyjaśniłem, że redukcja jest niepełna, ponieważ nie określiłem, jakie liczby są przydzielane nowym wierzchołkom, ale mam nadzieję, że można ją rozszerzyć bez większych trudności. Jednak na pewno muszę się nad tym zastanowić, zanim będę mógł cokolwiek powiedzieć.
Neeldhara,
1
Myślę, że celem komentarza JeffE jest to, że łatwo jest znaleźć idealne dopasowanie, które nie jest zagnieżdżone i nie krzyżuje się (lub zgłasza ich brak), ponieważ istnieje tylko jedna możliwość.
Tsuyoshi Ito
2
Nie mówię o treści twojego pomysłu na dowód, ale mówię o pierwszym zdaniu twojej odpowiedzi: „Mogę wymyślić, dlaczego może być trudno znaleźć idealne dopasowanie, które nie zagnieżdża się i nie krzyżuje”. To zadanie jest łatwe z tego powodu, dla którego napisał JeffE.
Tsuyoshi Ito
2
Bez ograniczenia kolorystycznego narzuconego przez problem czynnika rozłącznego (maksymalnie jedna krawędź każdego koloru), znalezienie maksymalnych dopasowań rozłącznych jest również łatwe.
Jeffε
1

Podejście to nie działa: rozkładanie potasowanego kwadratu przez wyjęcie dwóch pasujących liter nie powoduje przetasowania kwadratów ... Zobacz komentarze Radu poniżej.


Σ

S.(XY)ZA(X,Y)(1)ZA(zaX1,zaX2)Y1Y2))ZA(X1,Y1)ZA(X2),Y2))(2))ZA(ε,ε)ε(3))
zaΣε oznacza pusty.

X1Y1Y1X2)Y2)Y1Y2)X1X2)

zabdozabredore

S.(zabdozabredore)ZA(zabdo,zabredore)(przez 1,X=zabdo,Y=zabredore)ZA(bdo,bredore)ZA(ε,ε)(przez 2),X1=bdo,Y1=bredore,X2)=Y2)=ε)ZA(do,do)ZA(re,re)ZA(ε,ε)(przez 2))ZA(ε,ε)ZA(ε,ε)ZA(re,re)ZA(ε,ε)(przez 2))ZA(ε,ε)ZA(re,re)ZA(ε,ε)(przez 3))ZA(re,re)ZA(ε,ε)(przez 3))ZA(ε,ε)ZA(ε,ε)ZA(ε,ε)(przez 2))3)εtj. sukces

0011

S.(0011)ZA(0,011)ZA(ε,ε)ZA(1,1)ZA(1,1)ε

XY

Sylvain
źródło
ϵ
Nie wydaje mi się
Serge Gaspers
ϵ
Dzięki za zwroty; Trochę zmieniłem gramatykę, a nawet mam małą intuicję, z której to może zadziałać.
Sylvain
3
ϵ
1

Aktualizacja: Jak zauważa Tsuyoshi Ito w komentarzach, algorytm ten ma wykładniczy czas działania.

Oryginalny post:

Oto jak zaprogramowałbym to w świecie rzeczywistym.

Otrzymujemy ciąg S = (S [1], ..., S [n]). Dla każdego prefiksu S_r = (S [1], ..., S [r]) istnieje zestaw {(T_i, U_i)} par ciągów znaków, taki że S_r jest przetasowaniem (T_i, U_i), a T_i jest prefiksem U_i (tj. U_i 'zaczyna się od' T_i). Sam S_r jest kwadratem wtedy i tylko wtedy, gdy ten zestaw zawiera parę (T_i, U_i) z T_i = U_i.

Teraz nie musimy generować wszystkich tych par; musimy tylko wygenerować przyrostek V_i każdego łańcucha U_i uzyskany przez usunięcie jego kopii T_i. Wyeliminuje to (prawdopodobnie wykładniczą) liczbę nieistotnych duplikatów. Teraz S_r jest kwadratem wtedy i tylko wtedy, gdy ten zestaw sufiksów zawiera pusty ciąg. Algorytm staje się:

Initialise: SuffixSet = {<empty string>} ; r = 0
Loop: while (r < n) {
  r = r + 1
  NextSuffixSet = {}
  for each V in SuffixSet {
    if (V[1] == S[r]) Add V[2...] to NextSuffixSet // Remove first character of V
    Add V||S[r] to NextSuffixSet // Append character S[r] to V
    }
  SuffixSet = NextSuffixSet
  }
Now S is a square if and only if SuffixSet contains the empty string.

Na przykład, jeśli S to AABAAB:

r=0: SuffixSet = {<empty string>}
r=1: S[r] = A; SuffixSet = {A}
r=2: S[r] = A; SuffixSet = {<empty string>, AA}
r=3: S[r] = B; SuffixSet = {B, AAB}
r=4: S[r] = A; SuffixSet = {BA, AB, AABA}
r=5: S[r] = A; SuffixSet = {BAA, B, ABA, AABAA}
r=6: S[r] = B; SuffixSet = {AA, BAAB, <empty string>, BB, ABAB, AABAAB}

Możemy odrzucić wszystkie przyrostki o ponad połowę dłuższe niż łańcuch wejściowy, co upraszcza:

r=0: SuffixSet = {<empty string>}
r=1: S[r] = A; SuffixSet = {A}
r=2: S[r] = A; SuffixSet = {<empty string>, AA}
r=3: S[r] = B; SuffixSet = {B, AAB}
r=4: S[r] = A; SuffixSet = {BA, AB}
r=5: S[r] = A; SuffixSet = {BAA, B, ABA}
r=6: S[r] = B; SuffixSet = {AA, <empty string>, BB}

Zaprogramowałem to w C ++ i działa na wszystkich podanych tu przykładach. Mogę opublikować kod, jeśli ktoś jest zainteresowany. Pytanie brzmi: czy rozmiar SuffixSet może rosnąć szybciej niż wielomianowo?

TonyK
źródło
3
Próbowałem tego też, ale eksperymenty pokazują, że rozmiar SuffixSet wydaje się rosnąć wykładniczo w n, jeśli oryginalny ciąg to (AB) ^ n.
Tsuyoshi Ito
1

EDYCJA: To jest niepoprawna odpowiedź.


Sylvain zasugerował RCG, który niestety nie był odpowiedni dla tych „losowych kwadratów”. Myślę jednak, że istnieje jeden (EDYCJA: nie RCG, patrz komentarze Kurta poniżej!) , Który wygląda następująco:

S.(Y)ZA(ϵ,Y)(1)ZA(X,ZY)ZA(XZ,Y)(2))ZA(zaX,zaY)ZA(X,Y) dla każdego zaΣ(3))ZA(ϵ,ϵ)ϵ(4)

zazabbzabzab(1,2))(3))(2))

100110101010

S.(100110101010)ZA(ϵ,100110101010)(1)ZA(1001,10101010)(2))ZA(01,101010)(3))ZA(011,01010)(2))ZA(1,010)(3))ZA(10,10)(2))ZA(ϵ,ϵ)(3))ϵ(4)

Nie opracowałem formalnego dowodu, że ta gramatyka rzeczywiście przechwytuje dokładnie „losowe kwadraty”, ale nie powinno to być zbyt trudne. Sylvain wspomniał już, że problem decyzyjny dla RCG jest wielomianowy.

DaniCL
źródło
ZA(x,ϵ)2)3)
5
@DaniCL, Druga myśl ... Czy parametry w RHS reguł produkcji muszą być ciągłymi zakresami danych wejściowych? Nie widziałem tego wyraźnie w definicji w pracy Boulliera, ale wydaje się, że tak właśnie jest. W analizie czasu działania algorytmu parsowania stwierdza się, że liczba możliwych argumentów klauzul wynosi O (n ^ 2h), gdzie h jest maksymalną liczbą klauzul, a n jest długością wejściową. W twojej gramatyce XZ ogólnie nie będzie ciągły w oryginalnym wprowadzeniu.
Kurt
3
@Kurt, myślę, że znalazłeś wadę. W innym artykule („Liczby chińskie, MIX, Gramatyki i gramatyki konkatenacji zakresów”) Boullier wyraźnie stwierdza: „Oczywiście tylko kolejne kolejne zakresy można łączyć w nowe zakresy. W każdym PRCG terminale, zmienne i argumenty w klauzuli są powinien być związany z zakresami za pomocą mechanizmu substytucji. ” To prawdopodobnie oznacza, że ​​moja gramatyka nie jest prawidłową RCG, że wątpliwości Radu były uzasadnione i że to podejście również nie działa.
DaniCL
2
@Kurt jest poprawny. Bez ograniczenia ciągłości jestem pewien, że mogę stworzyć zestaw reguł produkcji, które rozpoznają język NP-complete UNARY 3PARTITION. Dowolny zestaw nieujemnych liczb całkowitych może być zakodowany w unarnym ciągu znaków w języku (1 * 0) ^ *. UNARY 3PARTITION jest zbiorem wszystkich takich ciągów, których zakodowany zestaw można podzielić na 3-elementowe podzbiory, wszystkie o tej samej sumie. (Patrz en.wikipedia.org/wiki/3-partition_problem .)
Jeffε
1
Gramatyka dla UNARY 3PARTITION: S (X0Y0Z) -> A (e, X0, Y0, Z); A (W, 1X, Y, Z), A (W, X, 1Y, Z), A (W, X, Y, 1Z) -> A (W1, X, Y, Z); A (W, 0X, 0Y, 0Z) -> B (W, XYZ); B (W, e) -> e; B (W, X0Y0Z) -> C (W, W, X0, Y0, Z); C (W, 1V, 1X, Y, Z), C (W, 1V, X, 1Y, Z), C (W, 1V, X, Y, 1Z) -> C (W, V, X, Y, Z); C (W, e, X, Y, Z) -> B (W, XYZ)
Radu GRIGore