3

对于任何两个序列 a, b, 其中 a = [a1,a2,...,an] 和 b = [b1,b2,...,bn] (0<=ai, bi<=m)，我想要找到一个整数函数 f，它 f(a) = f(b) 当且仅当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 ，使用十进制转换，我们最终会得到 f(a) = f(b) = 1123 ≠ f(c) = 1233。但这将花费 O(nlog(n)) 时间使用某种排序算法（不要使用非比较排序算法）。

有更好的方法吗？哈希之类的东西？O(n) 算法？

请注意，我还需要易于反转的函数，这意味着我们可以将整数映射回序列（或更简洁的集合）。

更新：原谅我糟糕的描述。这里 m 和 n 都可以非常大（100 万或更大）。而且我还希望 f 的上限非常小，最好是 O(m^n)。

4

2 回答 2

4

这适用于足够小的 值m和足够小的数组大小：

#include <stdio.h>

unsigned primes [] = { 2,3,5,7,11,13,17, 19, 23, 29};
unsigned value(unsigned array[], unsigned count);

int main(void)
{
unsigned one[] = { 1,2,2,3,5};
unsigned two[] = { 2,3,1,5,2};
unsigned val1, val2;

val1 = value(one, 5);
val2 = value(two, 5);
fprintf(stdout, "Val1=%u, Val2=%u\n", val1, val2 );

return 0;
}

unsigned value(unsigned array[], unsigned count)
{
unsigned val, idx;

val = 1;
for (idx = 0; idx < count; idx++) {
        val *= primes [ array[idx]];
        }

return val;
}

有关解释，请参阅我的描述here。

于 2013-11-06T14:06:53.500 回答
3

哇，@wildplasser 的答案实际上非常聪明。稍微扩展一下：

任何数字都可以以独特的方式分解为素数（这被称为算术基本定理）。他的答案依赖于此，通过构建一个数字，输入数组是素因子分解的表示。由于乘法是可交换的，因此数组中元素的确切顺序并不重要，但给定的数字与一个（且只有一个）元素序列相关联。

他的解决方案可以扩展为任意大小，例如在 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-indexed), 5'2', 等等...

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

构建数字本身就是 O(n) 乘法，只要最终结果保持在int您正在使用的域中（不幸的是，我怀疑它可能很快就会失控）。像我一样用 Eratosthenes Sieve 构建素数系列是渐近 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，因为有两个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 回答