Jak znaleźć leksykograficznie najmniejszy ciąg przez odwrócenie podciągu?

Question

Mam ciąg S, który składa się z a i b. Wykonaj poniższą operację jeden raz. Celem jest uzyskanie leksykograficznie najmniejszego ciągu znaków.

pracy: tyłu dokładnie jeden podciąg S

np

1. jeśli S = abab następnie Output = aabb (reverse ba sznurka S)
2. jeśli S = abba następnie Output = aabb (reverse bba sznurka S)

moje podejście

Przypadek 1: Jeśli wszystko znaki ciągu wejściowego są takie same jak wtedy utput będzie samym ciągiem znaków.

Przypadek 2: jeśli S ma postać aaaaaaa....bbbbbb.... wtedy odpowiedź będzie sama S.

inaczej: Znajdź pierwszego wystąpienia b w S powiedzieć, że pozycja jest i. String S będzie wyglądać

aa...bbb...aaaa...bbbb....aaaa....bbbb....aaaaa... 
    | 
    i 

W celu uzyskania leksykograficznie najmniejszemu String podciąg że ulegną odwróceniu rozpoczyna się od indeksu i. Zobacz poniżej, aby zobaczyć możliwe zakończenie j.

Odwróć podciąć S[i:j] dla każdego j i znajdź najmniejszy ciąg. Złożoność algorytmu będzie O(|S|*|S|), gdzie |S| jest długość ciągu.

Czy jest lepszy sposób na rozwiązanie tego problemu? Prawdopodobnie rozwiązanie O(|S|).

Co mam na myśli, jeśli możemy wybrać prawidłowy j w czasie liniowym, a my skończymy. Wybierzemy j, gdzie liczba a jest maksymalna. Jeśli jest jeden maksimum, rozwiązaliśmy problem, ale co, jeśli tak nie jest? Wiele próbowałem. Proszę pomóż.

Answer 1

Tak, wymyśliłem algorytm, który wydaje się być bardziej efektywny niż O (| S |^2), ale nie jestem całkiem pewien jego złożoności. Oto ogólnym zarysie:

1. Strip z wiodących a's, przechowywanie w zmiennej start.
2. Połóż resztę ciągu na fragmenty liter.
3. Znajdź indeksy grup o najdłuższych sekwencjach a's.
4. Jeśli pozostanie tylko jeden index, przejdź do 10.
5. Filtruj te indeksy, aby długość [pierwszej] grupy b's po odwróceniu była minimalna.
6. Jeśli tylko jeden index pozostałości, przejdź do 10.
7. Filtr tych wskaźników, tak że długość pierwszego] [grupie a's (bez czołowego a's) po odwróceniu się na minimalnym poziomie.
8. Jeśli tylko jeden index szczątki, przejdź do 10.
9. Wróć do 5, z wyjątkiem sprawdzenia [drugi/trzeci/...] grupy a's i b's tym czasie.
10. Powrót start plus odwrócone grupy do index plus pozostałe grupy.

Ponieważ dowolny fragment, który jest odwrócony rozpoczyna się b i kończy się a żadne dwa hipotezę odwrócenie są palindromów, a tym samym dwa odwrócenie nie spowoduje samej wydajności, co gwarantuje, że nie jest unikalne rozwiązanie optymalne i że algorytm się zakończy.

Moja intuicja podpowiada to podejście prawdopodobnie O (log (| S |) * | S |), ale nie jestem zbyt pewny. Poniżej znajduje się przykładowa implementacja (nie bardzo dobra) w Pythonie.

from itertools import groupby 

def get_next_bs(i, groups, off): 
    d = 1 + 2*off 
    before_bs = len(groups[i-d]) if i >= d else 0 
    after_bs = len(groups[i+d]) if i <= d and len(groups) > i + d else 0 
    return before_bs + after_bs 

def get_next_as(i, groups, off): 
    d = 2*(off + 1) 
    return len(groups[d+1]) if i < d else len(groups[i-d]) 

def maximal_reversal(s): 
    # example input: 'aabaababbaababbaabbbaa' 

    first_b = s.find('b') 
    start, rest = s[:first_b], s[first_b:] 
    # 'aa', 'baababbaababbaabbbaa' 

    groups = [''.join(g) for _, g in groupby(rest)] 
    # ['b', 'aa', 'b', 'a', 'bb', 'aa', 'b', 'a', 'bb', 'aa', 'bbb', 'aa'] 

    try: 
     max_length = max(len(g) for g in groups if g[0] == 'a') 
    except ValueError: 
     return s # no a's after the start, no reversal needed 

    indices = [i for i, g in enumerate(groups) if g[0] == 'a' and len(g) == max_length] 
    # [1, 5, 9, 11] 

    off = 0 
    while len(indices) > 1: 
     min_bs = min(get_next_bs(i, groups, off) for i in indices) 
     indices = [i for i in indices if get_next_bs(i, groups, off) == min_bs] 
     # off 0: [1, 5, 9], off 1: [5, 9], off 2: [9] 

     if len(indices) == 1: 
      break 

     max_as = max(get_next_as(i, groups, off) for i in indices) 
     indices = [i for i in indices if get_next_as(i, groups, off) == max_as] 
     # off 0: [1, 5, 9], off 1: [5, 9] 

     off += 1 

    i = indices[0] 
    groups[:i+1] = groups[:i+1][::-1] 

    return start + ''.join(groups) 
    # 'aaaabbabaabbabaabbbbaa' 

Answer 2

TL; DR: Oto algorytm, który tylko iteruje ciąg raz (z O (| S |) -ish złożoność ograniczonych długościach smyczkowych). Przykład z którym wyjaśnię to poniżej jest nieco rozwlekły, ale algorytm jest naprawdę bardzo proste:

• iteracyjne nad ciąg, i aktualizuje jego wartość interpretowana jako odwrotność (LSB-to-MSB) Liczba binarna.
• Jeśli znajdziesz ostatnie zero w sekwencji zer dłuższej niż bieżące maksimum, zapisz bieżącą pozycję i bieżącą wartość odwrotną. Od tego momentu zaktualizuj tę wartość, interpretując resztę ciągu jako liczbę binarną do przodu (msb-to-lsb).
• Jeśli znajdziesz ostatnie zero w sekwencji zer, która jest tak długa, jak bieżące maksimum, porównaj bieżącą wartość odwrotną z bieżącą wartością zapisanego punktu końcowego; jeśli jest mniejszy, zastąp punkt końcowy aktualną pozycją.

Więc w zasadzie porównywania wartości ciąg jakby były odwrócone do aktualnego punktu, o wartości łańcucha gdyby tylko odwrócić się do (tak daleko) optymalnym punkcie i aktualizowanie tego optymalnego punktu w locie.

Oto przykład szybkiego kodu; może to niewątpliwie być kodowane bardziej eleganckie:

function reverseSubsequence(str) { 
 
    var reverse = 0, max = 0, first, last, value, len = 0, unit = 1; 
 
    
 
    for (var pos = 0; pos < str.length; pos++) { 
 
     var digit = str.charCodeAt(pos) - 97;     // read next digit 
 
     if (digit == 0) { 
 
      if (first == undefined) continue;     // skip leading zeros 
 
      if (++len > max || len == max && reverse < value) { // better endpoint found 
 
       max = len; 
 
       last = pos; 
 
       value = reverse; 
 
      } 
 
     } else { 
 
      if (first == undefined) first = pos;    // end of leading zeros 
 
      len = 0; 
 
     } 
 
     reverse += unit * digit;        // update reverse value 
 
     unit <<= 1; 
 
     value = value * 2 + digit;        // update endpoint value 
 
    } 
 
    return {from: first || 0, to: last || 0}; 
 
} 
 
var result = reverseSubsequence("aaabbaabaaabbabaaabaaab"); 
 
document.write(result.from + "&rarr;" + result.to);

(kod może być uproszczona przez porównanie reverse i value gdy zera występuje, a nie tylko wtedy, gdy koniec maksymalnie długa sekwencja zera napotkano.)

---

można stworzyć algorytm, który tylko iteracje nad wejściem raz, a może przetwarzać przychodzącego strumienia o nieznanej długości, poprzez śledzenie dwóch wartości: wartość całego łańcucha interpretowany jako odwrotność (LSB -to-msb) liczba binarna i wartość ciągu z jedną częścią odwróconą. Za każdym razem, gdy wartość odwrotna spada poniżej wartości zapisanego najlepszego punktu końcowego, znaleziono lepszy punkt końcowy.

Rozważmy następujący ciąg jako przykład:

aaabbaabaaabbabaaabaaab 

lub, napisany z zer i jedynek dla uproszczenia:

00011001000110100010001 

Mamy iteracyjne nad zerem na początku, dopóki nie znajdziemy pierwszy:

0001 
^

To jest początek sekwencji, którą chcemy cofnąć. Zaczniemy interpretacji strumień zer i jedynek jako odwrócone (LSB do MSB) liczby binarnej i aktualizować ten numer po każdym kroku:

reverse = 1, unit = 1 

Następnie na każdym kroku, podwoimy urządzenie i aktualizować odwrotnie numer:

0001  reverse = 1 
00011  unit = 2; reverse = 1 + 1 * 2 = 3 
000110  unit = 4; reverse = 3 + 0 * 4 = 3 
0001100  unit = 8; reverse = 3 + 0 * 8 = 3 

W tym miejscu znajdujemy jeden, a ciąg zera dobiega końca.Zawiera 2 zer, która obecnie jest maksymalna, więc zapisać bieżącą pozycję jako możliwego punktu końcowego, a także przechowywać aktualną wartość wstecznych:

endpoint = {position = 6, value = 3} 

Potem idziemy na iteracji nad ciągiem, ale na każdy krok, musimy zaktualizować wartość możliwego punktu końcowego, ale teraz jako normalny (MSB do LSB) liczbę binarną:

00011001  unit = 16; reverse = 3 + 1 * 16 = 19 
       endpoint.value *= 2 + 1 = 7 
000110010  unit = 32; reverse = 19 + 0 * 32 = 19 
       endpoint.value *= 2 + 0 = 14 
0001100100 unit = 64; reverse = 19 + 0 * 64 = 19 
       endpoint.value *= 2 + 0 = 28 
00011001000 unit = 128; reverse = 19 + 0 * 128 = 19 
       endpoint.value *= 2 + 0 = 56 

w tym momencie okazuje się, że mamy sekwencję 3 zer, który jest dłużej niż obecne maksimum 2, więc odrzucamy dotychczasowy punkt końcowy i zastępujemy go bieżącą pozycją i wartością odwrotną:

endpoint = {position = 10, value = 19} 

A potem idziemy na iteracji przez wyrażenie:

000110010001   unit = 256; reverse = 19 + 1 * 256 = 275 
        endpoint.value *= 2 + 1 = 39 
0001100100011  unit = 512; reverse = 275 + 1 * 512 = 778 
        endpoint.value *= 2 + 1 = 79 
00011001000110  unit = 1024; reverse = 778 + 0 * 1024 = 778 
        endpoint.value *= 2 + 0 = 158 
000110010001101  unit = 2048; reverse = 778 + 1 * 2048 = 2826 
        endpoint.value *= 2 + 1 = 317 
0001100100011010  unit = 4096; reverse = 2826 + 0 * 4096 = 2826 
        endpoint.value *= 2 + 0 = 634 
00011001000110100 unit = 8192; reverse = 2826 + 0 * 8192 = 2826 
        endpoint.value *= 2 + 0 = 1268 
000110010001101000 unit = 16384; reverse = 2826 + 0 * 16384 = 2826 
        endpoint.value *= 2 + 0 = 2536 

Tutaj okazuje się, że mamy kolejną sekwencję z 3 zerami, więc mamy porównanie bieżącej wartości odwróconych wartości punktu końcowego, a okaże się, że przechowywane końcowy ma niższą wartość:

endpoint.value = 2536 < reverse = 2826 

więc utrzymać zestaw końcowy do pozycji 10 i idziemy na iteracji przez wyrażenie:

0001100100011010001  unit = 32768; reverse = 2826 + 1 * 32768 = 35594 
         endpoint.value *= 2 + 1 = 5073 
00011001000110100010  unit = 65536; reverse = 35594 + 0 * 65536 = 35594 
         endpoint.value *= 2 + 0 = 10146 
000110010001101000100 unit = 131072; reverse = 35594 + 0 * 131072 = 35594 
         endpoint.value *= 2 + 0 = 20292 
0001100100011010001000 unit = 262144; reverse = 35594 + 0 * 262144 = 35594 
         endpoint.value *= 2 + 0 = 40584 

I znaleźć inną sekwencję 3 zerami, więc porównać tę pozycję do zapamiętanej punktu końcowego:

endpoint.value = 40584 > reverse = 35594 

i uważamy, że ma mniejszą wartość, więc zastąpić możliwego punktu końcowego z aktualna pozycja:

endpoint = {position = 21, value = 35594} 

A potem iteracyjne nad ostatecznym cyfry:

00011001000110100010001 unit = 524288; reverse = 35594 + 1 * 524288 = 559882 
          endpoint.value *= 2 + 1 = 71189 

Więc u koniec okazuje się, że pozycja 21 daje nam najniższą wartość, więc jest to optymalne rozwiązanie:

00011001000110100010001 -> 00000010001011000100111 
^    ^
start = 3   end = 21 

---

Oto wersja C++, który wykorzystuje wektor bool zamiast liczb całkowitych. Może on parsować ciągi dłuższe niż 64 znaki, ale złożoność jest prawdopodobnie kwadratowa.

#include <vector> 

struct range {unsigned int first; unsigned int last;}; 

range lexiLeastRev(std::string const &str) { 
    unsigned int len = str.length(), first = 0, last = 0, run = 0, max_run = 0; 
    std::vector<bool> forward(0), reverse(0); 
    bool leading_zeros = true; 

    for (unsigned int pos = 0; pos < len; pos++) { 
     bool digit = str[pos] - 'a'; 
     if (!digit) { 
      if (leading_zeros) continue; 
      if (++run > max_run || run == max_run && reverse < forward) { 
       max_run = run; 
       last = pos; 
       forward = reverse; 
      } 
     } 
     else { 
      if (leading_zeros) { 
       leading_zeros = false; 
       first = pos; 
      } 
      run = 0; 
     } 
     forward.push_back(digit); 
     reverse.insert(reverse.begin(), digit); 
    } 
    return range {first, last}; 
}