寻找一个双射函数将集合映射到整数

Question

寻找一个双射函数将集合映射到整数

3

对于任意两个序列a、b（其中a = [a1,a2,...,an]，b = [b1,b2,...,bn]，0 <= ai，bi <= m），我想找到一个整数函数f，当且仅当a、b具有相同的元素时，f(a) = f(b)，而不考虑它们的顺序。例如，如果a = [1,1,2,3]，b = [2,1,3,1]，c = [3,2,1,3]，则f(a) = f(b)，f(a) ≠ f(c)。

我知道有一种朴素算法，先对序列进行排序，然后将其映射到一个整数。例如，在排序后，我们有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)。

- akirast

1

可能是检查数组B是否为A的排列的重复问题。 - Bernhard Barker

或者检查两个数组是否相似，无需哈希或排序。 - Bernhard Barker

哈希和链表可能会有所帮助。但是，除非您的集合在某种程度上受到限制，否则将无法使此函数可逆。例如，您的天真算法失败是因为 f([1,1,2,3]) ≡ f([11,23])。 - r3mainer

@wildplasser 的 m 可能非常大。 - akirast

@Dukeling 我认为这些问题不是重复的，因为我需要将数组转换为整数。 - akirast

2个回答

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开始计数），5是第'2'个，以此类推...

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

建立数字本身需要O(n)次乘法，只要最终结果保持在使用的int域内（不幸的是，我怀疑它可能很快就会失控）。像我一样使用Eratosthenes筛法构建素数序列是渐进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函数才是真正的哈希函数，因此如果你处理长度和组成不同的数组，则质数分解可能是安全的选择，因为它将始终针对每组数字返回相同的唯一整数。

- val

1

我相信埃拉托斯特尼筛法算法是O(n log log n)，用于查找小于等于 n 的质数。由于第k个质数渐近地为k log k，因此找到前n个质数的复杂度应该是类似于O(n log n log log n)的东西。 - rici

@rici：您说得完全正确，我在这里混淆了。已经更正了。 - val

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- wildplasser · Accepted Answer

这适用于足够小的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;
}

需要解释的话，请点击这里查看。