素数を使ったアナグラムの比較

Question

2つのユニークな文字列が互いのアナグラムであるかどうかを調べるという問題があります。私が考えていた最初の解決策は、両方のストリングをソートし、それらがお互いに等しいかどうかを確認することでした。

私は別の解決策を検討しており、同じことが実現可能かどうかについて議論したいと思います。

考えられるのは、各文字に数値を割り当てて、一意の文字セットが一意の値を生成するようにすることです。アナグラムをテストしているとき、 "asdf"と "adsf"のチェックサムが同じかどうかは気にしません。実際には、そのようにする必要があります。ただし、文字列 "aa"と "b"のチェックサムは同じであってはなりません。

最初の52個の素数をアルファベット「a」〜「z」に割り当て、次に「A」〜「Z」（アルファベットのみを想定）に割り当てることを検討していました。

上記のスキームは、52個の素数のセット内の任意の2つ以上の素数の合計が、そのセット内に存在する別の素数をもたらす可能性がある場合には破損する。

私の疑問は、次のとおりです。 - 私の要件をsatifyする任意の番号付けスキームは

1. ありますか？
2. 私は関係する数学について確信しています。最初の52個の素数集合の2つ以上の素数の和が同じ集合に存在する少なくとも1つの値を持つことを示唆する証拠があるかどうかを証明することは可能ですか？

ありがとうございます。

Answer 1

加算の代わりに乗算を使用します。プライムは「乗法的にユニーク」であるが、「付加的にユニーク」ではない。

Answer 2

素数を使用しないでください - 素数プロパティは、合計ではなく除算に関連しています。 しかし、アイデアは良いです、あなたはビットセットを使用することができますが、別の問題を打つだろう - 文字の重複（素数と同じ問題、1 + 1 + 1 = 3）。 したがって、文字の頻度の配列1〜26の整数セットを使用できます。

Answer 3

ちょっと厄介なのは、最も長い文字列の長さmax_len（またはパフォーマンスが少し向上するためには、特定の文字の最大数）が必要です。あなたは素数を使用することが好ましい場合ことを考えると、あなたのハッシュは

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

ようになり、乗算は、前述のように、良い仕事します。

もちろん、52の値の配列を持つことで同じ効果を得ることができます。

Answer 4

ソートされた2つの文字列を比較するときに、2つのnビットの数値が等しいかどうかを比較して比較します。あなたの文字列が2^n以上の可能なソートされた文字列があるように十分長くなると、同じnビット数を生成する2つの異なるソートされた文字列が間違いなくあります。 http://en.wikipedia.org/wiki/Birthday_problemでは、（素数の乗算と同じように）同じ数から2つの異なる文字列を持つことができないという定理がない限り、これ以前に問題が発生する可能性があります。

場合によっては、このアイデアを簡単な最初のチェックとして使用することで時間を節約することができます。その場合、ソートされた文字列が一致する場合にのみソートされた文字列を比較する必要があります。ここで

Answer 5

は素数の方法を使用してC＃で実装したものです：

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(); 

     } 
    } 
    }