Jak sprawdzić, czy dwa łańcuchy są wzajemnie permutacjami, używając dodatkowej spacji O (1)?

Biorąc pod uwagę dwa ciągi, jak możesz sprawdzić, czy są one wzajemną permutacją za pomocą spacji O (1)? Modyfikowanie ciągów znaków nie jest w żaden sposób dozwolone.
Uwaga: odstęp O (1) w stosunku do długości łańcucha ORAZ wielkości alfabetu.

Naiwnym podejściem byłoby budowanie histogramów obu ciągów i sprawdzanie, czy są one takie same. Ponieważ nie wolno nam przechowywać takiej struktury danych (której rozmiar byłby liniowy do wielkości alfabetu), którą można by obliczyć w jednym przebiegu, musimy policzyć wystąpienia każdego możliwego symbolu po drugim:

function count(letter, string)
    var count := 0
    foreach element in string
        if letter = element
            count++
    return count

function samePermutation(stringA, stringB)
    foreach s in alphabet
        if count(s, stringA) != count(s, stringB)
            return false
    return true

Zakłada się oczywiście, że liczby i wskaźniki iteratora są liczbami całkowitymi o stałym rozmiarze, a nie zależą od długości łańcuchów.

Oznacz tablice i załóżmy, że mają długość n .$A,B$$n$

Załóżmy najpierw, że wartości w każdej tablicy są różne. Oto algorytm, który wykorzystuje przestrzeń :$O(1)$

1. Oblicz minimalne wartości obu tablic i sprawdź, czy są one identyczne.

2. Oblicz drugie minimalne wartości obu tablic i sprawdź, czy są one identyczne.

3. I tak dalej.

Obliczenie minimalnej wartości tablicy wyraźnie wykorzystuje przestrzeń . Biorąc pod uwagę k- najmniejszy element, możemy znaleźć ( k + 1 ) st najmniejszy element, znajdując minimalną wartość większą niż k- ty najmniejszy element (tutaj wykorzystujemy fakt, że wszystkie elementy są odrębne).$O(1)$$k$$(k+1)$$k$

Gdy elementy mogą się powtarzać, modyfikujemy algorytm w następujący sposób:

1. Oblicz minimalne wartości obu tablic, policz, ile razy każde z nich się pojawi, i sprawdź m A , 1 = m B , 1 i czy liczby są identyczne.$m_{A,1},m_{B,1}$$m_{A,1} = m_{B,1}$

2. Obliczyć minimalne wartości większe niż m A , 1 , m B , 1 w dwóch tablicach (odpowiednio) i policzyć, ile razy się pojawiają. Sprawdź, czy m A , 2 = m B , 2 i czy liczby są identyczne.$m_{A,2},m_{B,2}$$m_{A,1},m_{B,1}$$m_{A,2} = m_{B,2}$

3. I tak dalej.

Zdefiniuj funkcję f (c), która odwzorowuje znak c na unikalną liczbę pierwszą (a = 2, b = 3, c = 5 itd.).

set checksum = 1
set count = 0 <-- this is probably not even necessary, but it's another level of check
for character c in string 1
    checksum = checksum * f(c)
    count = count + 1
for character c in string 2
    checksum = checksum / f(c)
    count = count = 1

permutation = count == 0 and checksum == 1

$\textit{O}\textbf{(1)}$

Możesz to zrobić O(nlogn). Posortuj dwa ciągi i porównaj je indeks po indeksie. Jeśli różnią się gdziekolwiek, to nie są wzajemnymi permutacjami.

Dla O(n)rozwiązania można zastosować skrót. Ta funkcja mieszająca działałaby i edla każdej litery byłaby jej wartość ascii. Jeśli dwa skróty ciągów różnią się, nie są one wzajemnymi permutacjami.

Funkcja skrótu w łączu:

Może to być jeden potencjalny kandydat. Napraw nieparzystą liczbę całkowitą R. Dla każdego elementu e, który chcesz mieszać, oblicz współczynnik (R + 2 * e). Następnie oblicz iloczyn wszystkich tych czynników. Na koniec podziel produkt przez 2, aby uzyskać skrót.

Współczynnik 2 w (R + 2e) gwarantuje, że wszystkie czynniki są nieparzyste, dlatego unika się, że iloczyn zawsze będzie wynosił 0. Podział na 2 na końcu jest taki, że iloczyn zawsze będzie nieparzysty, dlatego podział po prostu usuwa stały bit .

Np. Wybieram R = 1779033703. Jest to arbitralny wybór, wykonywanie niektórych eksperymentów powinno pokazać, czy dane R jest dobre czy złe. Załóżmy, że twoje wartości to [1, 10, 3, 18]. Produkt (obliczony przy użyciu 32-bitowych liczb całkowitych) to

(R + 2) * (R + 20) * (R + 6) * (R + 36) = 3376724311 Stąd skrót byłby

3376724311/2 = 1688362155.

Użycie podwójnego haszowania (lub jeszcze większej przepełnienia) poprzez zmianę wartości R z powodzeniem zidentyfikowałoby je jako permutacje z bardzo dużym prawdopodobieństwem.

Powiedzmy, że masz dwa ciągi zwane s i t.

Możesz użyć heurystyki, aby upewnić się, że nie są one nierówne.

1. s.length == t. długość
2. suma znaków s == suma znaków wt
3. [to samo co w 2., ale z xor zamiast sumy]

Następnie możesz łatwo uruchomić algorytm, aby udowodnić, że ciąg znaków jest równy.

1. posortuj jeden ciąg znaków, aby był równy drugiemu i porównaj (O (n ^ 2))
2. posortuj oba i porównaj (O (log 2n (n))
3. sprawdź, czy dla każdego znaku w tych ciągach są takie same kwoty (O (n ^ 2))

Oczywiście nie możesz posortować tak szybko, jeśli nie możesz użyć dodatkowej przestrzeni. Nie ma więc znaczenia, który algorytm wybierzesz - każdy algorytm będzie działał w czasie O (n ^ 2), gdy będzie tylko przestrzeń O (1) i jeśli heurystyka nie będzie w stanie udowodnić, że nie mogą być równe.

W kodzie w stylu C dla całej procedury:

for (int i = 0; i < n; i++) {
   int k = -1;
   next: for (int j = 0; j <= i; j++)
       if (A[j] == A[i]) {
          while (++k < n)
              if (B[k] == A[i])
                  continue next;
          return false; // note at this point j == i
       }
}
return true; 

Lub bardzo pseudo-kodem (przy użyciu indeksowania 1)

// our loop invariant is that B contains a permutation of the letters
// in A[1]..A[i-1]
for i=1..n
   if !checkLetters(A, B, i)
      return false
return true

gdzie funkcja checkLetters (A, B, i) sprawdza, czy jeśli istnieje M kopii A [i] w A [1] .. A [i], to jest co najmniej M kopii A [i] w B:

checkLetters(A,B,i)
    k = 0 // scan index into B
    for j=1..i
      if A[j] = A[i]
         k = findNextValue(B, k+1, A[i])
         if k > n
            return false
    return true

i funkcja findNextValue wyszukuje w B wartość rozpoczynającą się od indeksu i zwraca indeks, w którym został znaleziony (lub n + 1, jeśli nie został znaleziony).

$n^2$

$O(n^3$$n$

Pętla string1i string2dla każdej postaci sprawdź, jak często można ją znaleźć w string1i string2. Jeśli znak jest częściej w jednym ciągu niż w drugim, nie jest to permutacja. Jeśli częstotliwości wszystkich znaków są równe, to łańcuchy są wzajemnymi permutacjami.

Oto fragment pytona, aby to precyzyjnie określić

s1="abcaba"
s2="aadbba"

def check_if_permutations(string1, string2):
  for string in [string1, string2]:
    # string references string1 
    #  string2, it is not a copy
    for char in string:
      count1=0
      for char1 in string1:
        if  char==char1:
          count1+=1
      count2=0
      for char2 in string2:
        if  char==char2:
          count2+=1
      if count1!=count2:
        print('unbalanced character',char)
        return()
  print ("permutations")
  return()

check_if_permutations(s1,s2)

stringstring1string2charchar1char2$O(\log n)$count1count2string[string1, string2]

Oczywiście nie potrzebujesz nawet zmiennych count, ale możesz używać wskaźników.

s1="abcaba"
s2="aadbba"

def check_if_permutations(string1, string2):
  for string in [string1, string2]:
    # string references one of string1 
    # or string2, it is not a copy
    for char in string:
      # p1 and p2 should be views as pointers
      p1=0
      p2=0
      while (p1<len(string1)) and (p2<len(string2)):
        # p1>=len(string1): p1 points to beyond end of string
        while (p1<len(string1)) and (string1[p1]!=char) :
          p1+=1
        while(p2<len(string2)) and (string2[p2]!=char):
          p2+=1
        if (p1<len(string1)) != (p2<len(string2)):
          print('unbalanced character',char)
          return()
        p1+=1
        p2+=1
  print ("permutations")
  return()

check_if_permutations(s1,s2)

$O(\log(n))$

$n$