寻求一个双射函数映射套整数 [英] Seek for a bijective function maps sets to integers

问题描述

有关的任​​何两个序列a，b，其中a = [A1，A2，...，一个]和b = [B1，B2，......，BN（0℃= AI，BI＆其中; = m）个，我想找到一个整数的函数f使得f（A）= F（B），当且仅当 A，B 有相同的元素，而没有任何关于他们的订单。例如，如果一个= [1,1,2,3]，B = [2,1,3,1]，C = [3,2,1,3]，则f（A）= F（二）中，f（一）≠F（b）中。

For any two sequences a, b, where a = [a1,a2,...,an] and b = [b1,b2,...,bn] (0<=ai, bi<=m), I want to find an integer function f that f(a) = f(b) if and only if a, b have the same elements, without concerning about their orders.For example, if a = [1,1,2,3], b = [2,1,3,1], c = [3,2,1,3], then f(a) = f(b), f(a) ≠ f(b).

我知道有一个天真的算法，第一次排序的序列，然后将其映射到一个整数。 例如，整理后，我们有= [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（n日志（n））的时间使用排序算法的某种（不要使用非比较排序算法）。

I know there is a naive algorithm which first sort the sequence and then map it to an integer. For example, after sorting, we have a = [1,1,2,3], b = [1,1,2,3], c = [1,2,3,3], and suppose that m = 9, using decimal conversion, we will finally have f(a) = f(b) = 1123 ≠ f(c) = 1233. But this will take O(nlog(n)) time using some kind of sorting algorithm (Don't use non comparison sorting algorithms).

有没有更好的方法？像哈希？一个O（n）的算法？

Is there a better approach ? Something like hash? An O(n) algorithm?

请注意，我还需要功能容易被反转，这意味着我们可以映射的整数回一个序列（或一组，更简明）。

Note that I also need the function easy to be inversed, which means that we can map an integer back to a sequence (or a set, more concisely).

更新：原谅我那可怜的说明。这里既有M，N可以是非常大的（100万美元或以上）。我也想上界的F相当小，preferably 0（M ^ N）。

Update: Forgive my poor description. Here both m, n can be very large (1 million or larger). And I also want the upper bound of f to be quite small, preferably O(m^n).

推荐答案

这适用于 M 的足够小的值，并且足够小的数组大小：

This works for sufficiently small values of m, and sufficiently small array sizes:

#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;
}

有关解释，看到这里我的描述。

这篇关于寻求一个双射函数映射套整数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！