algorithm - 素数を使用したアナグラムの比較

Question

2つの一意の文字列が互いにアナグラムであるかどうかを確認しようとする問題があります。私が考えた最初の解決策は、両方の文字列を並べ替えて、それらが互いに等しいかどうかを確認することでした。

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

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

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

上記のスキームは、52個の素数のセット内の2つ以上の素数の合計が、セット内に別の素数が存在する結果になる可能性がある場合に機能しなくなります。

私の疑問は：-

1. 要件を満たす番号付けスキームはありますか？
2. 関係する数学についてはよくわかりません; 最初の52個の素数のセット内の2つ以上の素数の合計が、同じセット内に少なくとも1つの値を持っていることを証明することは可能ですか？

ありがとう。

Answer 1

加算の代わりに乗算を使用します。素数は「乗法的に一意」ですが、「加法的に一意」ではありません。

Answer 2

これを行うには少し不格好な方法で、最長の文字列max_lenの長さ（またはパフォーマンスをわずかに向上させるための特定の文字の最大数）が必要になります。それを考えると、あなたのハッシュは次のようになります

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

素数を使用したい場合は、前述のように、乗算の方がうまく機能します。

もちろん、代わりに52個の値の配列を使用することで、同じ効果を得ることができます。

Answer 3

2つのnビット数が等しいかどうかを比較することにより、2つのソートされた文字列が等しいかどうかを比較しようとしています。文字列が十分に長くなり、2 ^ nを超える可能な並べ替えられた文字列が存在するようになるとすぐに、同じnビット数を生成する2つの異なる並べ替えられた文字列が確実に作成されます。http://en.wikipedia.org/wiki/Birthday_problemによると、（素数の乗算の場合のように）2つの異なる文字列を使用できないという定理がない限り、この前に問題が発生する可能性があります。同じ番号。

場合によっては、このアイデアを最初に等しいかどうかをすばやくチェックすることで時間を節約できるため、ソートされた文字列の数が一致する場合にのみ比較する必要があります。

Answer 4

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

Answer 5

def primes(n):
    array = [i for i in range(2,n+1)]
    p = 2

    while p <= n:
        i = 2*p
        while i <= n:
            array[i-2] = 0
            i += p
        p += 1

    return [num for num in array if num > 0]

def anagram(a):
    # initialize a list
    anagram_list = []
    for i in a: 
        for j in a: 
            if i != j and (sorted(str(i))==sorted(str(j))):
                anagram_list.append(i)
    return anagram_list

if __name__ == '__main__':
    print("The Prime Numbers are:\n",primes(1000),"\n")
    a = primes(1000)
    print("Prime Numbers between 0 to 100:")
    T100 = a[:25]
    print(T100,"\n")
    print("The Anagram elements from 0 to 100 are listed :", anagram(T100),"\n")
    print("Prime Numbers between 101 to 200:")
    T200 = a[25:46]
    print(T200,"\n")
    print("The Anagram elements from 101 to 200 are listed :",anagram(T200),"\n")
    print("Prime Numbers between 201 to 300:")
    T300 = a[46:62]
    print(T300,"\n")
    print("The Anagram elements from 201 to 300 are listed :",anagram(T300),"\n")
    print("Prime Numbers between 301 to 400:")
    T400 = a[62:78]
    print(T400,"\n")
    print("The Anagram elements from 301 to 400 are listed :",anagram(T400),"\n")
    print("Prime Numbers between 401 to 500:")
    T500 = a[78:95]
    print(T500,"\n")
    print("The Anagram elements from 401 to 500 are listed :",anagram(T500),"\n")
    print()
    print("Prime Numbers between 501 to 600:")
    T600 = a[95:109]
    print(T600,"\n")
    print("The Anagram elements from 501 to 600 are listed :",anagram(T600),"\n")
    print("Prime Numbers between 601 to 700:")
    T700 = a[109:125]
    print(T700,"\n")
    print("The Anagram elements from 601 to 700 are listed :",anagram(T700),"\n")
    print("Prime Numbers between 701 to 800:")
    T800 = a[125:139]
    print(T800,"\n")
    print("The Anagram elements from 701 to 800 are listed :",anagram(T800),"\n")
    print()
    print("Prime Numbers between 801 to 900:")
    T900 = a[139:154]
    print(T900,"\n")
    print("The Anagram elements from 801 to 900 are listed :",anagram(T900),"\n")
    print("Prime Numbers between 901 to 1000:")
    T1000 = a[154:168]
    print(T1000,"\n")
    print("The Anagram elements from 901 to 1000 are listed :",anagram(T1000),"\n")

出力：

The Prime Numbers are:
 [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997] 

Prime Numbers between 0 to 100:
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97] 

The Anagram elements from 0 to 100 are listed : [13, 17, 31, 37, 71, 73, 79, 97] 

Prime Numbers between 101 to 200:
[101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199] 

The Anagram elements from 101 to 200 are listed : [113, 131, 137, 139, 173, 179, 193, 197] 

Prime Numbers between 201 to 300:
[211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293] 

The Anagram elements from 201 to 300 are listed : [239, 293] 

Prime Numbers between 301 to 400:
[307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397] 

The Anagram elements from 301 to 400 are listed : [313, 331, 337, 373, 379, 397] 

Prime Numbers between 401 to 500:
[401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499] 

The Anagram elements from 401 to 500 are listed : [419, 491] 


Prime Numbers between 501 to 600:
[503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599] 

The Anagram elements from 501 to 600 are listed : [] 

Prime Numbers between 601 to 700:
[601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691] 

The Anagram elements from 601 to 700 are listed : [613, 619, 631, 691] 

Prime Numbers between 701 to 800:
[701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797] 

The Anagram elements from 701 to 800 are listed : [] 


Prime Numbers between 801 to 900:
[809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887] 

The Anagram elements from 801 to 900 are listed : [] 

Prime Numbers between 901 to 1000:
[907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997] 

The Anagram elements from 901 to 1000 are listed : [919, 991] 

Python開発者であれば、好きなようにリフレームすることもできます。Pythonの初心者の場合は、リストの概念を学んでください。

Answer 6

これまでに試みた例の複雑さを理解していないので、簡単なPython3の例を作成しました。

from operator import mul
from functools import reduce

TO_PRIME = dict( \
    a=2, b=3, c=5, d=7, e=11, \
    f=13, g=17, h=19, i=23, j=29, \
    k=31, l=37, m=41, n=43, o=47, \
    p=53, q=59, r=61, s=67, t=71, \
    u=73, v=79, w=83, x=89, y=97, z=101 \
    )

def anagram_product(string):
    return reduce(mul, (TO_PRIME[char.lower()] for char in string if char.isalpha()), 1)

def anagram_check(string_1, string_2):
    return anagram_product(string_1) == anagram_product(string_2)

# True examples

print(repr('Astronomer'), repr('Moon starer'), anagram_check('Astronomer', 'Moon starer'))

print(repr('The Morse code'), repr('Here come dots'), anagram_check('The Morse code', 'Here come dots'))

# False examples (near misses)

print(repr('considerate'), repr('cure is noted'), anagram_check('considerate', 'cure is noted'))

print(repr('debit card'), repr('bed credit'), anagram_check('debit card', 'bed credit'))

出力

> python3 test.py
'Astronomer' 'Moon starer' True
'The Morse code' 'Here come dots' True
'considerate' 'cure is noted' False
'debit card' 'bed credit' False
> 

次のステップは、これを製品から合計に変換することです。私が想像する1つのアプローチは、文字を素数ではなく無理数にマッピングすることです。これらの無理数は、いかなる種類の加算によっても合理的にならないタイプである必要があります。大まかな例を次に示します。

from math import pi

ROUND = 4

TO_IRRATIONAL = {letter: pi ** n for n, letter in enumerate('abcdefghijklmnopqrstuvwxyz')}

def anagram_sum(string):
    return round(sum(TO_IRRATIONAL[char.lower()] for char in string if char.isalpha()), ROUND)

def anagram_check(string_1, string_2):
    return anagram_sum(string_1) == anagram_sum(string_2)

# True examples

print(repr('Astronomer'), repr('Moon starer'), anagram_check('Astronomer', 'Moon starer'))

print(repr('The Morse code'), repr('Here come dots'), anagram_check('The Morse code', 'Here come dots'))

# False examples (near misses)

print(repr('considerate'), repr('cure is noted'), anagram_check('considerate', 'cure is noted'))

print(repr('debit card'), repr('bed credit'), anagram_check('debit card', 'bed credit'))

出力

> python3 test2.py
'Astronomer' 'Moon starer' True
'The Morse code' 'Here come dots' True
'considerate' 'cure is noted' False
'debit card' 'bed credit' False
> 

これが無理数の最適なセットであると言っているのではなく、概念の大まかなデモンストレーションにすぎません。（round()この作業を行うために使用する必要があることに注意してください。これは、1つの設計上の欠陥（無理数の有限表現）を示しています。）

Answer 7

素数の方法を使用した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();

        }
    }
    }