3

a = [a1,a2,...,an] および b = [b1,b2,...,bn] (0<=ai, bi<=m) である任意の 2 つのシーケンス a, b について、 f(a) = f(b) である整数関数 f を見つけるにはa, b、次数を気にせずに同じ要素を持つ必要があります。たとえば、a = [1,1,2,3] の場合、b = [ 2,1,3,1]、c = [3,2,1,3] の場合、f(a) = f(b)、f(a) ≠ f(b)。

最初にシーケンスをソートしてから整数にマップする単純なアルゴリズムがあることを私は知っています。たとえば、並べ替え後、a = [1,1,2,3]、b = [1,1,2,3]、c = [1,2,3,3] となり、m = 9 とします。 、10 進変換を使用すると、最終的に f(a) = f(b) = 1123 ≠ f(c) = 1233 になります。非比較ソートアルゴリズムを使用します)。

より良いアプローチはありますか？ハッシュみたいな​​もの？O(n) アルゴリズム?

関数 easy to be inversed も必要であることに注意してください。つまり、整数をシーケンス (または、より簡潔に言うとセット) にマップし直すことができます。

更新: 私の貧弱な説明を許してください. ここで、m と n の両方が非常に大きくなる可能性があります (100 万以上)。また、f の上限を非常に小さく、できれば O(m^n) にしたいと考えています。

4

2 に答える 2

3

うわー、@wildplasserの答えは実際には非常にスマートです。少し拡張するには：

任意の数は、一意の方法で素数に分解できます(これは算術の基本定理として知られています)。彼の答えは、入力配列が素因数分解の表現である数値を構築することによって、それに依存しています。乗算は交換可能であるため、配列内の要素の正確な順序は重要ではありませんが、指定された数は要素の 1 つの (そして 1 つのみの) シーケンスに関連付けられます。

彼のソリューションは、Python などで任意のサイズに拡張できます。

import operator
import itertools
import math

class primes(object):
    def __init__(self):
        self.primes = [2,3,5,7,11]
        self.stream = itertools.count(13, 2)

    def __getitem__(self, i):
        sq = int(math.sqrt(i))
        while i >= len(self.primes):
            n = self.stream.next()
            while any(n % p == 0 for p in self.primes if p <= sq):
                n = self.stream.next()
            self.primes.append(n)
        return self.primes[i]

def prod(itr):
    return reduce(operator.mul, itr, 1)

p = primes()

def hash(array):
    return prod(p[i] for i in array)

期待される結果:

>>> hash([1,2,2,3,5])
6825
>>> hash([5,3,2,2,1])
6825

ここで6825 = 3^1 x 5^2 x 7^1 x 13^1は3、'1' 素数 (0 インデックス)、5'2' など...

>>> 3**1 * 5**2 * 7**1 * 13**1
6825

最終結果が使用しているドメイン内にある限り、数値自体の構築は O(n) 乗算intです (残念ながら、すぐに手に負えなくなる可能性があると思います)。私が行ったように、エラトステネスのふるいで一連の素数を構築すると、漸近的に O(N * log log N) になります。ここで、N は m 番目に大きい素数です。漸近的に、N ~ m log m、これは O(n + m * log m * loglog (m * log m)) の全体的な複雑さを与えます。

同様のアプローチを使用して、素数の分解を行う代わりに、配列を基数の分解の表現と見なすこともできます。一貫性を保つために、このベースは多数の同様の要素よりも大きくなければなりません (たとえば、 の場合[5, 3, 3, 2, 1]、 が 2 つあるため、ベースは > 2 でなければなりません3)。安全のために、次のように書くことができます。

def hash2(array):
    n = len(array)
    return sum(n**i for i in array)

>>> hash2([1,5,3,2,2])
8070
>>> hash2([2,1,5,2,3])
8070

最初に配列内の類似要素の最大数を計算することでこれを改善できますが、関数は同じ基底hash2で使用された場合にのみ実数ハッシュになるため、可変長の配列を使用して作業する場合、素数分解はおそらく安全です。数字のバッグごとに常に同じ一意の整数を返すためです。

于 2013-11-06T15:15:31.720 に答える