Confronto tra gli anagrammi usando i numeri primi

Question

C'è il problema di provare a vedere se due stringhe univoche sono anagrammi l'una dell'altra. La prima soluzione che ho considerato sarebbe quella di ordinare entrambe le stringhe e vedere se erano uguali tra loro.

Ho preso in considerazione un'altra soluzione e vorrei discutere se lo stesso sarebbe fattibile.

L'idea sarebbe quella di assegnare un valore numerico a ciascun carattere e riassumerlo in modo tale che un insieme unico di caratteri produrrebbe un valore univoco. Come stiamo testando per gli anagrammi, non ci importa se il checksum di "asdf" e "adsf" sono gli stessi - infatti, lo richiediamo in questo modo. Tuttavia il checksum delle stringhe "aa" e "b" non dovrebbe essere uguale.

Stavo considerando di assegnare i primi 52 numeri primi agli alfabeti da "a" a "z" e quindi da "A" a "Z" (supponiamo di avere solo alfabeti).

Lo schema precedente si interromperebbe se la somma di due o più numeri primi nell'insieme di 52 numeri primi potrebbe generare un altro numero primo esistente nell'insieme.

I miei dubbi sono: -

1. C'è qualche schema di numerazione che satify mie esigenze?
2. Non sono sicuro della matematica in questione; è possibile provare/c'è qualche prova che suggerisce che la somma di due o più numeri primi nell'insieme dei primi 52 primi abbia almeno un valore che esiste nello stesso insieme?

Grazie.

Answer 1

Utilizzare la moltiplicazione anziché l'aggiunta. I numeri sono "moltiplicativamente unici", ma non "additivamente unici".

Answer 2

Non utilizzare numeri primi: le proprietà dei numeri primi sono correlate alla divisione, non alle somme. Tuttavia, l'idea è buona, è possibile utilizzare i set di bit, ma si verificherebbe un altro problema: lettere duplicate (lo stesso problema con i numeri primi, 1 + 1 + 1 = 3). Quindi, è possibile utilizzare un set intero, un array 1 ... 26 di frequenza di lettere.

Answer 3

Un modo leggermente più goffo per farlo richiederebbe la lunghezza della stringa più lunga max_len (o il numero più grande di qualsiasi carattere specifico per prestazioni leggermente migliori). Dato che, il vostro hash potrebbe assomigliare

number_of_a*max_len^51 + number_of_b*max_len^50 + ... + number_of_Z*max_len^0 

Se si preferisce utilizzare numeri primi, la moltiplicazione funzionerà meglio, come accennato in precedenza.

Ovviamente, è possibile ottenere lo stesso effetto disponendo invece di un array di 52 valori.

Answer 4

Si sta tentando di confrontare due stringhe ordinate per l'uguaglianza confrontando due numeri di n bit per l'uguaglianza. Non appena le tue stringhe sono abbastanza lunghe da avere più di 2^n stringhe ordinate, avrai sicuramente due stringhe ordinate diverse che producono lo stesso numero n-bit. È probabile, dal http://en.wikipedia.org/wiki/Birthday_problem, che si verificheranno problemi prima di questo, a meno che (come con la moltiplicazione dei numeri primi) ci sia un teorema che dice che non si possono avere due stringhe diverse dallo stesso numero.

In alcuni casi è possibile risparmiare tempo utilizzando questa idea come prima verifica rapida dell'uguaglianza, in modo che sia necessario confrontare solo le stringhe ordinate se i loro numeri corrispondono.

Answer 5

Ecco un'implementazione in C# utilizzando il modo numeri primi:

using System; 
    using System.Collections.Generic; 
    using System.Linq; 
    using System.Text; 

namespace Anag 
{ 
    class Program 
    { 
     private static int[] primes100 = new int[] 
              { 
               3, 7, 11, 17, 23, 29, 37, 
               47, 59, 71, 89, 107, 131, 
               163, 197, 239, 293, 353, 
               431, 521, 631, 761, 919, 
               1103, 1327, 1597, 1931, 
               2333, 2801, 3371, 4049, 
               4861, 5839, 7013, 8419, 
               10103, 12143, 14591, 17519, 
               21023, 25229, 30293, 36353, 
               43627, 52361, 62851, 75431, 
               90523, 108631, 130363, 
               156437, 187751, 225307, 
               270371, 324449, 389357, 
               467237, 560689, 672827, 
               807403, 968897, 1162687, 
               1395263, 1674319, 2009191, 
               2411033, 2893249, 3471899, 
               4166287, 4999559, 5999471, 
               7199369 
              }; 

     private static int[] getNPrimes(int _n) 
     { 
      int[] _primes; 

      if (_n <= 100) 
       _primes = primes100.Take(_n).ToArray(); 
      else 
      { 
       _primes = new int[_n]; 

       int number = 0; 
       int i = 2; 

       while (number < _n) 
       { 

        var isPrime = true; 
        for (int j = 2; j <= Math.Sqrt(i); j++) 
        { 
         if (i % j == 0 && i != 2) 
          isPrime = false; 
        } 
        if (isPrime) 
        { 
         _primes[number] = i; 
         number++; 
        } 
        i++; 
       } 

      } 

      return _primes; 
     } 

     private static bool anaStrStr(string needle, string haystack) 
     { 
      bool _output = false; 

      var needleDistinct = needle.ToCharArray().Distinct(); 

      int[] arrayOfPrimes = getNPrimes(needleDistinct.Count()); 

      Dictionary<char, int> primeByChar = new Dictionary<char, int>(); 
      int i = 0; 
      int needlePrimeSignature = 1; 

      foreach (var c in needleDistinct) 
      { 
       if (!primeByChar.ContainsKey(c)) 
       { 
        primeByChar.Add(c, arrayOfPrimes[i]); 

        i++; 
       } 
      } 

      foreach (var c in needle) 
      { 
       needlePrimeSignature *= primeByChar[c]; 
      } 

      for (int j = 0; j <= (haystack.Length - needle.Length); j++) 
      { 
       var result = 1; 
       for (int k = j; k < needle.Length + j; k++) 
       { 
        var letter = haystack[k]; 
        result *= primeByChar.ContainsKey(letter) ? primeByChar[haystack[k]] : 0; 
       } 

       _output = (result == needlePrimeSignature); 
       if (_output) 
        break; 
      } 

      return _output; 
     } 


     static void Main(string[] args) 
     { 
      Console.WriteLine("Enter needle"); 
      var _needle = Console.ReadLine(); ; 
      Console.WriteLine("Enter haystack"); 
      var _haystack = Console.ReadLine(); 

      Console.WriteLine(anaStrStr(_needle, _haystack)); 
      Console.ReadLine(); 

     } 
    } 
    }