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

13

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.

Anonimowy
źródło
3
Co myślisz? Co próbowałeś i gdzie utknąłeś? Czy ciągi znaków mają stały alfabet? Czy próbowałeś obliczyć ich histogramy?
Yuval Filmus
@YuvalFilmus powinno być odstęp O (1) zarówno do długości łańcucha, jak i wielkości alfabetu
Anonimowy
Wydaje się to wyraźnie niemożliwe. Każdy algorytm będzie wymagał dodatkowej przestrzeni do przechowywania co najmniej pozycji w jednym ciągu lub pojedynczym znaku. Żadna z tych rzeczy nie jest O (1).
David Schwartz
@DavidSchwartz - jak? O (1) oznacza stałą, a nie jedną stopkę. Nie ma znaczenia, jak długi jest łańcuch, pozycja w nim to jedna liczba.
Davor
Zależy to od modelu maszyny, co oczywiście nie stanowi problemu w modelach jednolitych. W modelu kosztów logarytmicznych przechowującym indeks dotyczy O(log n)ciągów o długości n, która nie jest stała ani za pomocą długości, ani wielkości alfabetu. Kiedy łańcuchy mogą być tymczasowo modyfikowane, myślę, że istnieje rozwiązanie ze zwiększonym alfabetem, który jest liniowy w rozmiarze alfabetu, ale stały w długości łańcucha w modelu logarytmicznym.
kap

Odpowiedzi:

7

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.

Bergi
źródło
Jako optymalizację możesz przejść przez jedną tablicę i obliczyć tylko histogramy napotkanych liter. W ten sposób złożoność staje się niezależna od wielkości alfabetu.
Yuval Filmus
Aby rozwinąć komentarz @YuvalFilmus, musisz również 1) sprawdzić, czy długości ciągów są takie same lub 2) powtórzyć oba ciągi wejściowe. Potrzebujesz jednej z nich, ponieważ możliwe jest, że niektórych liter w jednej nie ma w drugiej. Opcja 1 powinna zawierać mniej obliczeń.
BurnsBA
@YuvalFilmus Chciałem tego uniknąć, ponieważ oznaczałoby to kwadratową złożoność czasu, oczekiwałbym, że alfabet będzie mniejszy niż średni rozmiar łańcucha. W przypadku małych ciągów znaków i uporządkowanego alfabetu rozważę obliczenie następnego najmniejszego obecnego symbolu wraz z liczbą w wewnętrznej pętli, aby można było pominąć kilka iteracji w pętli alfabetu - ze złożonością O(n * min(n, |Σ|)). Hm, teraz, kiedy o tym myślę, brzmi to jak rozwiązanie „dozwolone do powtórzenia” z twojej odpowiedzi, prawda?
Bergi,
countnie jest O(1)(tzn. może się przepełnić)
reinierpost
1
@Eternalcode nigdy nie powiedziałem, że countbył int:-) Tak, to nie praca, ale w Javie , że nie może się zdarzyć w każdym razie
BERGI
12

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

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.mA,1,mB,1mA,1=mB,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.mA,2,mB,2mA,1,mB,1mA,2=mB,2

  3. I tak dalej.

Yuval Filmus
źródło
1
Czy takie podejście byłoby ponieważ wydaje się, że jedynym sposobem na znalezienie elementu min w przestrzeni O ( 1 ) i dostęp do tablicy tylko do odczytu jest iteracja po wszystkich elementach? O(n2)O(1)
ryan
4
Wymaga to uporządkowania alfabetu, chociaż łatwo jest zmienić algorytm, aby tego nie wymagać. Jednak w przypadku „ma duplikaty” wymaga to przestrzeni , a nie O ( 1 ) . Liczenie zajmuje miejsce. O(lgn)O(1)
Derek Elkins opuścił SE
7
Liczenie wymaga przestrzeni (logarytmicznej), ale - zgodnie z tą definicją wykorzystania przestrzeni - nawet iteracja po tablicy. Zatem, pod ścisłym znaczeniem użycia przestrzeni, nie można tego zrobić w stałej przestrzeni.
Daniel Jour
4
@DanielJour, zależy to od używanego modelu kosztu . Przy jednolitym koszcie jest to możliwe na stałej przestrzeni.
ryan
7
Jeśli masz tylko stałą liczbę bitów, możesz obsługiwać tylko alfabety o stałym rozmiarze (wynika to z teorii zwykłych języków).
Yuval Filmus
2

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

O(1)

Alex Stasse
źródło
f(c)O(1)O(1)
Innym problemem, który zdałem sobie sprawę po opublikowaniu, jest to, że suma kontrolna będzie gigantyczną liczbą dla dużych ciągów znaków, o ile sama w sobie mogłaby naruszać wymagania dotyczące miejsca O (1). Można to rozwiązać za pomocą liczb zmiennoprzecinkowych i mutliplingu przez znak na jednym łańcuchu, a następnie dzieląc na drugi, a następnie mówiąc, że suma kontrolna musi być bliska 1. Łańcuchy musiałyby być naprawdę gigantyczne, aby błąd zmiennoprzecinkowy stanowił problem.
Alex Stasse
4
O(logn)
4
Θ(n)n
0

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.

Indo Ubt
źródło
1
Nie można sortować ciągów, ponieważ nie można ich modyfikować. Jeśli chodzi o haszowanie, jest to algorytm losowy, który może dać złą odpowiedź.
Yuval Filmus
0

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.

MurksVomOrk
źródło
3
Modyfikowanie ciągów nie jest w żaden sposób dozwolone.
Bergi,
0

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

n2

MotiN
źródło
Czy możesz przekonwertować kod C na pseudokod? To nie jest strona programistyczna.
Yuval Filmus
To wydaje się być kolejnym wariantem odpowiedzi Bergiego (z pewnymi nieistotnymi różnicami).
Yuval Filmus
O(nm)O(n2)
0

O(n3n

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)

stringstring1string2charchar1char2O(logn)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

cud173
źródło
Jest to to samo, co rozwiązanie Bergi poniżej.
Yuval Filmus
@YuvalFilmus Nie, nie iteruje całego alfabetu, dlatego jego środowisko wykonawcze nie zależy od wielkości alfabetu. Używa tylko dwóch ciągów, które powinny zostać przetestowane. Również drugi program unika liczenia.
miracle173
@YuvalFilmus Widzę teraz, że twoje i inne komentarze wskazują kierunek, w którym użyłem w moim programie.
miracle173