Bagaimana cara memeriksa apakah dua string adalah permutasi satu sama lain menggunakan O (1) ruang tambahan?

Diberikan dua string bagaimana Anda bisa memeriksa apakah mereka permutasi satu sama lain menggunakan ruang O (1)? Memodifikasi string tidak diizinkan dengan cara apa pun.
Catatan: O (1) spasi dalam kaitannya dengan panjang string DAN ukuran alfabet.

Pendekatan naif akan membangun histogram dari kedua string dan memeriksa apakah mereka sama. Karena kami tidak diperbolehkan menyimpan struktur data seperti itu (yang ukurannya akan linier dengan ukuran alfabet) yang dapat dihitung dalam satu lintasan, kami perlu menghitung kemunculan setiap simbol yang mungkin setelah yang lainnya:

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

Ini tentu saja mengasumsikan bahwa jumlah dan indeks iterator adalah bilangan bulat dari ukuran konstan, bukannya tergantung pada panjang string.

Nyatakan array oleh , dan anggap panjangnya n .$A,B$$n$

Anggaplah pertama bahwa nilai-nilai dalam setiap array berbeda. Berikut ini adalah algoritma yang digunakan :$O(1)$

1. Hitung nilai minimum kedua array, dan periksa apakah keduanya sama.

2. Hitung nilai minimum kedua dari kedua array, dan periksa apakah keduanya sama.

3. Dan seterusnya.

Menghitung nilai minimum array jelas menggunakan ruang . Dengan elemen terkecil ke k , kita dapat menemukan ( k + $O(1)$$k$ dengan menemukan nilai minimal lebih besar darielemen terkecil ke- k (di sini kita menggunakan fakta bahwa semua elemen berbeda).$(k+1)$$k$

Saat elemen diizinkan untuk diulang, kami memodifikasi algoritme sebagai berikut:

1. Hitung nilai minimum dari kedua array, hitung berapa kali masing-masing muncul, dan verifikasi m A , 1 = m $m_{A,1},m_{B,1}$ dan hitungnya sama.$m_{A,1} = m_{B,1}$

2. Hitung nilai minimum lebih besar dari m A , 1 , m B , 1 dalam dua array (masing-masing), dan hitung berapa kali masing-masing muncul. Verifikasi bahwa m A , 2 = m B $m_{A,2},m_{B,2}$$m_{A,1},m_{B,1}$ , dan bahwa penghitungannya identik.$m_{A,2} = m_{B,2}$

3. Dan seterusnya.

Tentukan beberapa fungsi f (c) yang memetakan beberapa karakter c ke bilangan prima unik (a = 2, b = 3, c = 5, dll).

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

Hanya menyatakan bahwa Anda dapat menggunakan fungsi pemetaan bilangan prima agak mudah, dan kemungkinan besar di mana masalah akan muncul menjaga ruang.$\textit{O}\textbf{(1)}$

Anda bisa melakukan ini O(nlogn) . Sortir kedua string, dan bandingkan indeksnya dengan indeks. Jika mereka berbeda di mana saja, mereka tidak permutasi satu sama lain.

Untuk O(n)solusi, hashing dapat digunakan. Fungsi hashing ini akan bekerja, dan e untuk huruf apa pun akan menjadi nilai ascii-nya. Jika dua hash string berbeda, mereka tidak permutasi satu sama lain.

Fungsi hashing dalam tautan:

Satu kandidat potensial mungkin adalah ini. Memperbaiki bilangan bulat ganjil R. Untuk setiap elemen e Anda ingin hash menghitung faktor (R + 2 * e). Kemudian hitung produk dari semua faktor ini. Akhirnya bagi produk dengan 2 untuk mendapatkan hash.

Faktor 2 dalam (R + 2e) menjamin bahwa semua faktor aneh, maka menghindari bahwa produk akan menjadi 0. Pembagian dengan 2 pada akhirnya adalah karena produk akan selalu aneh, maka pembagian hanya menghilangkan sedikit konstan .

Misalnya saya memilih R = 1779033703. Ini adalah pilihan sewenang-wenang, melakukan beberapa percobaan harus menunjukkan apakah R yang diberikan baik atau buruk. Asumsikan nilainya adalah [1, 10, 3, 18]. Produk (dihitung menggunakan int 32-bit) adalah

(R + 2) * (R + 20) * (R + 6) * (R + 36) = 3376724311 Maka hash akan

3376724311/2 = 1688362155.

Menggunakan hashing ganda (atau untuk lebih banyak lagi) dengan mengubah nilai R akan berhasil mengidentifikasi mereka sebagai permutasi dengan probabilitas yang sangat tinggi .

Katakanlah Anda memiliki dua string yang disebut s dan t.

Anda dapat menggunakan heuristik untuk memastikan bahwa mereka tidak sama.

1. s.length == t.length
2. jumlah karakter s == jumlah karakter dalam t
3. [sama seperti pada 2. tetapi dengan xor, bukan jumlah]

Setelah ini, Anda dapat dengan mudah menjalankan algoritma untuk membuktikan bahwa stringnya sama.

1. urutkan satu string agar sama dengan yang lain dan bandingkan (O (n ^ 2))
2. urutkan keduanya dan bandingkan (O (2n log (n))
3. periksa setiap karakter dalam s jika ada jumlah yang sama di kedua string (O (n ^ 2))

Tentu saja Anda tidak dapat mengurutkan secepat itu jika Anda tidak diizinkan untuk menggunakan ruang tambahan. Jadi tidak masalah algoritma mana yang Anda pilih - setiap algoritma akan membutuhkan akan berjalan dalam waktu O (n ^ 2) ketika hanya ada O (1) ruang dan jika heuristik tidak dapat membuktikan bahwa mereka tidak bisa sama.

Dalam kode C-style untuk seluruh rutin:

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; 

Atau dalam kode pseudo yang sangat verbose (menggunakan pengindeksan berbasis 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

di mana fungsi checkLetters (A, B, i) memeriksa bahwa jika ada salinan M dari A [i] di A [1] .. A [i], maka setidaknya ada M salinan A [i] di 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

dan fungsi findNextValue mencari dalam B untuk nilai yang dimulai dari indeks, dan mengembalikan indeks yang ditemukannya (atau n +1 jika tidak ditemukan).

$n^2$

$O(n^3$$n$

Loop through string1dan string2, untuk setiap karakter, periksa seberapa sering dapat ditemukan di string1dan string2. Saya seorang karakter lebih sering dalam satu string daripada yang lain, itu bukan permutasi. Jika frekuensi semua karakter sama maka string adalah permutasi satu sama lain.

Berikut adalah sepotong python untuk membuat ini tepat

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

Tentu saja Anda bahkan tidak perlu variabel jumlah tetapi dapat menggunakan pointer.

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))$ variabel untuk memegang nilai-nilai hitung.

$n$